On random cover and matching problems

• This thesis consists of the following papers.I  J. Larsson, The Minimum Matching in Pseudo-dimension 0 < q < 1, submittedII  V. Falgas-Ravry, J. Larsson, K. Markström, Speed and concentration of the covering time for structured coupon collectors, submittedIII  J. Larsson, K. Markström, Biased random k-SAT problems, manuscriptThese 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.

• Denna licentiatsavhandling består av följande artiklar.I  J. Larsson, The Minimum Matching in Pseudo-dimension 0 < q < 1, submittedII  V. Falgas-Ravry, J. Larsson, K. Markström, Speed and concentration of the covering time for structured coupon collectors, submittedIII  J. Larsson, K. Markström, Biased random k-SAT problems, manuscriptDe 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.

Ämnesord

NATURVETENSKAP  -- Matematik -- Diskret matematik (hsv//swe)

NATURAL SCIENCES  -- Mathematics -- Discrete Mathematics (hsv//eng)

Nyckelord

Mathematics

matematik

Publikations- och innehållstyp

vet (ämneskategori)

lic (ämneskategori)