Badges and rainbow matchings Aharoni, Ron; Briggs, Joseph; Kim, Jinha ...
Discrete mathematics,
June 2021, 2021-06-00, Letnik:
344, Številka:
6
Journal Article
Recenzirano
Odprti dostop
Drisko proved that 2n−1 matchings of size n in a bipartite graph have a rainbow matching of size n. For general graphs it is conjectured that 2n matchings suffice for this purpose (and that 2n−1 ...matchings suffice when n is even). The known graphs showing sharpness of this conjecture for n even are called badges. We improve the previously best known bound from 3n−2 to 3n−3, using a new line of proof that involves analysis of the appearance of badges. We also prove a “cooperative” generalization: for t>0 and n≥3, any 3n−4+t sets of edges, the union of every t of which contains a matching of size n, have a rainbow matching of size n.
We prove that the ‘Upper Matching Conjecture’ of Friedland, Krop, and Markström and the analogous conjecture of Kahn for independent sets in regular graphs hold for all large enough graphs as a ...function of the degree. That is, for every d and every large enough n divisible by 2d, a union of n/(2d) copies of the complete d-regular bipartite graph maximizes the number of independent sets and matchings of size k for each k over all d-regular graphs on n vertices. To prove this we utilize the cluster expansion for the canonical ensemble of a statistical physics spin model, and we give some further applications of this method to maximizing and minimizing the number of independent sets and matchings of a given size in regular graphs of a given minimum girth.
More than 50 years ago, Erdős asked the following question: what is the maximum size of family F of k-element subsets of an n-element set if it has no s+1 pairwise disjoint sets? This question ...attracted a lot of attention recently, in particular due to its connection to various combinatorial, probabilistic and theoretical computer science problems. Improving the previous best bound due to the first author, we prove that |F|≤(nk)−(n−sk), provided n≥53sk−23s and s is sufficiently large. The bound on |F| is sharp since the family of all k-sets that intersect some fixed s-element set has such size and has no s+1 pairwise disjoint sets. We derive several corollaries concerning Dirac thresholds and deviations of sums of random variables. We also obtain several related results.
We prove that in all regular robust expanders G$$ G $$, every edge is asymptotically equally likely contained in a uniformly chosen perfect matching M$$ M $$. We also show that given any fixed ...matching or spanning regular graph N$$ N $$ in G$$ G $$, the random variable |M∩E(N)|$$ \mid M\cap E(N)\mid $$ is approximately Poisson distributed. This in particular confirms a conjecture and a question due to Spiro and Surya, and complements results due to Kahn and Kim who proved that in a regular graph every vertex is asymptotically equally likely contained in a uniformly chosen matching. Our proofs rely on the switching method and the fact that simple random walks mix rapidly in robust expanders.
Looms Aharoni, Ron; Berger, Eli; Briggs, Joseph ...
Discrete mathematics,
December 2024, 2024-12-00, Letnik:
347, Številka:
12
Journal Article
Recenzirano
A pair (A,B) of hypergraphs is called orthogonal if |a∩b|=1 for every pair of edges a∈A,b∈B. An orthogonal pair of hypergraphs is called a loom if each of its two members is the set of minimum covers ...of the other. Looms appear naturally in the context of a conjecture of Gyárfás and Lehel on the covering number of cross-intersecting hypergraphs. We study their properties and ways of construction, and prove special cases of a conjecture that if true would imply the Gyárfás–Lehel conjecture.
While every instance of the Hospitals/Residents problem admits a stable matching, the problem with lower quotas (HR-LQ) has instances with no stable matching. For such an instance, we expect the ...existence of an envy-free matching, which is a relaxation of a stable matching preserving a kind of fairness property. In this paper, we investigate the existence of an envy-free matching in several settings, in which hospitals have lower quotas and not all doctor–hospital pairs are acceptable. We first provide an algorithm that decides whether a given HR-LQ instance has an envy-free matching or not. Then, we consider envy-freeness in the Classified Stable Matching model due to Huang (in: Procedings of 21st annual ACM-SIAM symposium on discrete algorithms (SODA2010), SIAM, Philadelphia, pp 1235–1253,
2010
), i.e., each hospital has lower and upper quotas on subsets of doctors. We show that, for this model, deciding the existence of an envy-free matching is NP-hard in general, but solvable in polynomial time if quotas are paramodular.
PDF
