umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
The Minimum Perfect Matching in Pseudo-dimension 0<q<1
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
(English)Manuscript (preprint) (Other academic)
Abstract [en]

It is known that for Kn,n equipped with i.i.d. exp(1) edge costs, the minimum total cost of a perfect matching converges to π2/6 in probability. Similar convergence has been established for all edge cost distributions of pseudo-dimension q≥1, such as Weibull(1,q) costs. In this paper we extend those results all q>0, confirming the Mézard-Parisi conjecture in the last remaining applicable case.

Keywords [en]
matching, mean field, replica symmetry, random graph, pseudo-dimention
National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-121414OAI: oai:DiVA.org:umu-121414DiVA, id: diva2:932744
Available from: 2016-06-02 Created: 2016-06-02 Last updated: 2018-06-07Bibliographically approved
In thesis
1. On random cover and matching problems
Open this publication in new window or tab >>On random cover and matching problems
2016 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

This thesis consists of the following papers.

  1. I  J. Larsson, The Minimum Matching in Pseudo-dimension 0 < q < 1, submitted

  2. II  V. Falgas-Ravry, J. Larsson, K. Markström, Speed and concentration of the covering time for structured coupon collectors, submitted

  3. III  J. Larsson, K. Markström, Biased random k-SAT problems, manuscript

These papers can all be seen as variations on the same question: Given a large set V and a family F of subsets of V, each assigned a (random) weight, we assign each subfamily G ⊆ F a cost based on the weights of sets that occur in it. What will the minimal cost of a subfamiliy G that covers V be?

In the first paper, we search for a disjoint cover of the ground set V = {u_1,u_2,...u_n,v_1,v_2,...v_n}, using random 2-sets of the form {u_i, v_j}. In other words, we search for matchings in a bipartite graph. Each edge receives a random weight distributed uniformly in [0, 1], and the cost of a perfect matching using edges with weights l_1,l_2,...l_n is Σ_{i=1}^n l_i^{1/q} for some q > 0.

The second paper lives in a more general setting. There we search for any cover of the ground set V, for general families F. Each set f ∈ F receives weight w(f) uniformly at random from [0,1]. The cost of a cover f_1,f_2,...f_m is then taken to be max_i w(f_i). This is equivalent (after a rescaling) to drawing sets from F at Poisson times, and the cost of a cover is the first time V is covered. This problem is known under a number of names, perhaps most famously the coupon collector problem. In the classical formulation, single elements of V are drawn, not sets. The classical coupon collector thus corresponds to the family F consisting of singleton sets, and we call the version allowing larger sets structured coupon collector problems. The main concern of this paper is to identify relevant properties of F that affect the covering time (i.e. minimal cost of a cover), and to provide (easily checkable) sufficient conditions for concentration of the covering time.

For the third paper we narrow the scopes once more, and study the biased random k-SAT problem. The random k-SAT problem can be seen as a special case of the structured coupon collector, but a special case that has far richer structure than the generic case. The ground set is the hypercube Σ_n = {0, 1}^n, and the coupons are all the k-codimensional subcubes of Σ_n. We study a slight variation on this problem: subcubes are drawn with a constant bias towards 0, so that vertices in Σ_n with fewer 1's and more 0's are easier to cover.

Abstract [sv]

Denna licentiatsavhandling består av följande artiklar.

  • I  J. Larsson, The Minimum Matching in Pseudo-dimension 0 < q < 1, submitted

  • II  V. Falgas-Ravry, J. Larsson, K. Markström, Speed and concentration of the covering time for structured coupon collectors, submitted

  • III  J. Larsson, K. Markström, Biased random k-SAT problems, manuscript

De tre artiklarna kan ses som variationer på samma fråga: Givet en basmängd V och en familj F av delmängder av V som alla tilldelas en (slumpmässig) vikt, tilldelar vi varje delfamilj G ⊆ F en kostnad baserad på vikterna av mängderna som ingår i G.

Vad kommer den minimala kostnaden av en delfamilj G som täcker V vara?

I den första artikeln söker vi efter en disjunkt övertäckning av mängden V = {u_1,u_2,... u_n,v_1,v_2,... v_n}, med 2-mängder av formen {u_i, v_j}. Med andra ord söker vi efter en matchning i en bipartit graf. Varje 2-mängd (kant) tilldelas en slumpmässig vikt uniformt från [0,1], och kostnaden för en matchning som använder kanter med vikter l_1, l_2,... l_n är Σ_{i=1}^n l_i^{1/q}$ för något q>0.

Den andra artikeln utspelar sig i en mer generell miljö. Där söker vi efter en övertäckning (inte nödvändigtvis disjunkt) av V, för generella familjer F. Varje mängd f ⊆ F tilldelas vikt w(f) enligt en likformig fördelning på [0,1]. Kostnaden av en övertäckning f_1, f_2,...f_m ges av max_i w(f_i).

Detta är ekvivalent (efter omskalning) med att mängder ur F dras som en Poisson-process, och kostnaden för en övertäckning ges av tidpunkten då V först har täckts.

Detta problem är känt under många olika namn, varav det kanske mest vanligt förekommande är kupongsamlarproblemet. I den klassiska formulering dras inte mängder utan enstaka element, vilket är ekvivalent med att F består av enbart singleton-mängder. När F även innehåller större mängder än så kallar vi det för det strukturerade kupongsamlarproblemet.

Huvudmålsättningen med denna artikel är att identifiera relevanta egenskaper hos F som påverkar täckningstiden, och att ge (lätt tillämpbara) tillräckliga kriterier för att täckningstiden ska vara skarpt koncentrerad.

Till den tredje artikeln smalnar vi ner fokus igen, och studerar det skeva slumpade k-SAT-problemet. Det slumpade k-SAT-problemet kan ses som ett specialfall av det strukturerade kupongsamlarproblemet, men ett specialfall med mycket rikare struktur än det generiska fallet. Basmängden är hyperkuben Σ_n={0,1}^n, och kupongerna är alla k-kodimensionella delkuber av Σ_n. Vi studerar en variant av detta problem där sannolikhetsfördelningen är något skev, så att delkuber närmre hörnet (0,0,...0) dras med högre sannolikhet, vilket i sin tur medför att hörn med fler nollor än ettor är lättare att täcka.

Place, publisher, year, edition, pages
Umeå: Umeå Universitet, 2016. p. 6
National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:umu:diva-121418 (URN)978-91-7601-466-0 (ISBN)
Presentation
2016-04-22, MA121, MIT-huset, Matematik och matematisk statistik, 901 87 Umeå, Umeå, 13:00 (English)
Opponent
Supervisors
Available from: 2016-11-28 Created: 2016-06-02 Last updated: 2018-06-07Bibliographically approved
2. On random satisfiability and optimization problems
Open this publication in new window or tab >>On random satisfiability and optimization problems
2018 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

In Paper I, we study the following optimization problem: in the complete bipartite graph where edges are given i.i.d. weights of pseudo-dimension q>0, find a perfect matching with minimal total weight. The generalized Mézard-Parisi conjecture states that the limit of this minimum exists and is given by the solution to a certain functional equation. This conjecture has been confirmed for q=1 and for q>1. We prove it for the last remaining case 0<q<1.

In Paper II, we study generalizations of the coupon collector problem. Versions of this problem shows up naturally in various context and has been studied since the 18th century. Our focus is on using existing methods in greater generality in a unified way, so that others can avoid ad-hoc solutions.

Papers III & IV concerns the satisfiability of random Boolean formulas. The classic model is to pick a k-CNF with m clauses on n variables uniformly at random from all such formulas. As the ratio m/n increases, the formulas undergo a sharp transition from satisfiable (w.h.p.) to unsatisfiable (w.h.p.). The critical ratio for which this occurs is called the satisfiability threshold.

We study two variations where the signs of variables in clauses are not chosen uniformly. In paper III, variables are biased towards occuring pure rather than negated. In paper IV, there are two types of clauses, with variables in them biased in opposite directions. We relate the thresholds of these models to the threshold of the classical model.

Place, publisher, year, edition, pages
Umeå: Umeå Universitet, 2018. p. 10
Series
Research report in mathematics, ISSN 1653-0810
Keywords
Random graphs, k-SAT, satisfiability, coupon collector, random cover time, threshold phenomenon, concentration of measure, combinatorial probability, perfect matching, assignment problem, local graph limit, mean-field
National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:umu:diva-147519 (URN)978-91-7601-875-0 (ISBN)
Public defence
2018-06-01, MA121, MIT-huset, Umeå, 13:15 (English)
Opponent
Supervisors
Available from: 2018-05-09 Created: 2018-05-04 Last updated: 2018-06-09Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

arXiv

Authority records BETA

Larsson, Joel

Search in DiVA

By author/editor
Larsson, Joel
By organisation
Department of Mathematics and Mathematical Statistics
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 61 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf