Pseudorandom hypergraph matchings
From MaRDI portal
Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Transversal (matching) theory (05D15) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)
Abstract: A celebrated theorem of Pippenger states that any almost regular hypergraph with small codegrees has an almost perfect matching. We show that one can find such an almost perfect matching which is `pseudorandom', meaning that, for instance, the matching contains as many edges from a given set of edges as predicted by a heuristic argument.
Recommendations
Cites work
- A bandwidth theorem for approximate decompositions
- A blow-up lemma for approximate decompositions
- A dense infinite Sidon sequence
- A geometric theory for hypergraph matching
- A linear programming perspective on the Frankl?R�dl?Pippenger theorem
- A Lower Bound for Heilbronn'S Problem
- A rainbow blow-up lemma for almost optimally bounded edge-colourings
- Asymptotically good list-colorings
- Blow-up lemma
- Counting designs
- Decompositions into spanning rainbow structures
- Dirac-type questions for hypergraphs -- a survey (or more problems for Endre to solve)
- Embedding rainbow trees with applications to graph labelling and decomposition
- Factors and loose Hamilton cycles in sparse pseudo-random hypergraphs
- Factors in random graphs
- scientific article; zbMATH DE number 4170917 (Why is no real title available?)
- HYPERGRAPH MATCHINGS AND DESIGNS
- Matchings and covers in hypergraphs
- Near perfect coverings in graphs and hypergraphs
- Near-optimal list colorings
- On a hypergraph matching problem
- On a packing and covering problem
- On perfect matchings in uniform hypergraphs with large minimum vertex degree
- Optimal packings of bounded degree trees
- Packing Hamilton cycles in random and pseudo-random hypergraphs
- Perfect matchings in \(r\)-partite \(r\)-graphs
- Perfect matchings in large uniform hypergraphs with large minimum collective degree
- Perfect Matchings in Random r-regular, s-uniform Hypergraphs
- Perfect packings in quasirandom hypergraphs. I.
- Probability theory. A comprehensive course
- Reducibility among combinatorial problems
- The Existence of Designs via Iterative Absorption: Hypergraph 𝐹-designs for Arbitrary 𝐹
Cited in
(22)- On testing the `pseudo-randomness' of a hypergraph
- On the number of nearly perfect matchings in almost regular uniform hypergraphs
- Decomposing hypergraphs into cycle factors
- The generalised Oberwolfach problem
- A Short proof of the blow-up lemma for approximate decompositions
- Santa claus meets hypergraph matchings
- Santa Claus Meets Hypergraph Matchings
- scientific article; zbMATH DE number 3957168 (Why is no real title available?)
- Decompositions of quasirandom hypergraphs into hypergraphs of bounded degree
- A rainbow blow-up lemma for almost optimally bounded edge-colourings
- A natural barrier in random greedy hypergraph matching
- Graph and hypergraph colouring via nibble methods: a survey
- A proof of the Erdős-Faber-Lovász conjecture
- Thresholds for Latin squares and Steiner triple systems: Bounds within a logarithmic factor
- New bounds on the size of nearly perfect matchings in almost regular hypergraphs
- Threshold for Steiner triple systems
- Graph and hypergraph packing
- Conflict-free hypergraph matchings
- Tight Hamilton cycles with high discrepancy
- Almost Steiner systems in finite classical polar spaces
- Ringel's tree packing conjecture in quasirandom graphs
- Cycle type in Hall-Paige: a proof of the Friedlander-Gordon-Tannenbaum conjecture
This page was built for publication: Pseudorandom hypergraph matchings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4993112)
