On Erdős' extremal problem on matchings in hypergraphs
From MaRDI portal
Publication:2439573
DOI10.1016/J.JCTA.2014.01.003zbMath1283.05143arXiv1202.4196OpenAlexW2095093161MaRDI QIDQ2439573
Katarzyna Mieczkowska, Tomasz Łuczak
Publication date: 14 March 2014
Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)
Abstract: In 1965 ErdH{o}s conjectured that the number of edges in k-uniform hypergraphs on n vertices in which the largest matching has s edges is maximized for hypergraphs of one of two special types. We settled this conjecture in the affirmative for k=3 and n is large enough.
Full work available at URL: https://arxiv.org/abs/1202.4196
Extremal problems in graph theory (05C35) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Unnamed Item
- Unnamed Item
- On matchings in hypergraphs
- On the maximum number of edges in a hypergraph with given matching number
- On the Maximum Number of Edges in a Triple System Not Containing a Disjoint Family of a Given Size
- The Size of a Hypergraph and its Matching Number
- SETS OF INDEPENDENT EDGES OF A HYPERGRAPH
Related Items (37)
Rainbow version of the Erdős Matching Conjecture via concentration ⋮ A Stability Result on Matchings in 3-Uniform Hypergraphs ⋮ The \((p, q)\)-extremal problem and the fractional chromatic number of Kneser hypergraphs ⋮ Size and structure of large \((s,t)\)-union intersecting families ⋮ Perfect Matchings in Hypergraphs and the Erdös Matching Conjecture ⋮ Factorially many maximum matchings close to the Erdős-Gallai bound ⋮ Degree versions of the Erdős-Ko-Rado theorem and Erdős hypergraph matching conjecture ⋮ The Erdős matching conjecture and concentration inequalities ⋮ Rainbow Perfect Matchings for 4-Uniform Hypergraphs ⋮ Proof of the Erdős matching conjecture in a new range ⋮ Anti-Ramsey Number of Matchings in 3-Uniform Hypergraphs ⋮ On maximal tail probability of sums of nonnegative, independent and identically distributed random variables ⋮ Large Yk,b ${Y}_{k,b}$‐tilings and Hamilton ℓ $\ell $‐cycles in k $k$‐uniform hypergraphs ⋮ Families with no matchings of size \(s\) ⋮ A better bound on the size of rainbow matchings ⋮ Rainbow Turán numbers of matchings and forests of hyperstars in uniform hypergraphs ⋮ On Rainbow Matchings for Hypergraphs ⋮ A short proof of Erdős' conjecture for triple systems ⋮ The structure of large intersecting families ⋮ On the random version of the Erdős matching conjecture ⋮ Structure of the largest subgraphs of \(G_{n , p}\) with a given matching number ⋮ Rainbow matchings in properly-colored hypergraphs ⋮ On the maximum number of edges in a hypergraph with given matching number ⋮ A generalization of Erdős' matching conjecture ⋮ The minimum number of disjoint pairs in set systems and related problems ⋮ On the maximum size of subfamilies of labeled set with given matching number ⋮ Extremal \(G\)-free induced subgraphs of Kneser graphs ⋮ Linear trees in uniform hypergraphs ⋮ Large \(Y_{3,2}\)-tilings in 3-uniform hypergraphs ⋮ Rainbow matchings for 3-uniform hypergraphs ⋮ Some results around the Erdős matching conjecture ⋮ Lagrangian densities of 4-uniform matchings and degree stability of extremal hypergraphs ⋮ Vertex degree sums for matchings in 3-uniform hypergraphs ⋮ Two problems on matchings in set families -- in the footsteps of Erdős and Kleitman ⋮ Vertex degree sums for matchings in 3-uniform hypergraphs ⋮ On the size of the product of overlapping families ⋮ On the rainbow matching conjecture for 3-uniform hypergraphs
This page was built for publication: On Erdős' extremal problem on matchings in hypergraphs
