On the matching problem in random hypergraphs

DOI10.1016/J.DISC.2025.114839MaRDI QIDQ6883688zbMATH OpenFDO

Authors Peter Frankl, Jiaxi Nie, Jian Wang

Publication date 16 December 2025

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DISC.2025.114839

zbMATH Keywords

Erdős matching problemrandom hypergraph

Mathematics Subject Classification ID

Hypergraphs (05C65) Random graphs (graph-theoretic aspects) (05C80) Transversal (matching) theory (05D15)

Review text

This paper studies a `transference' version of a stability result related to the Erdős matching conjecture. Given \(k\), \(s\), \(n\), what is the largest number of edges in an \(n\)-vertex \(k\)-uniform hypergraph with no \(s+1\) disjoint edges? Equivalently, we want the hypergraph to have `matching number' \(s\). For \(s\) small in comparison with \(n/k\), the best-known extremal example is the `trivial' \(k\)-uniform graph obtained as follows: fix a set \(T\) of size \(s\), put every \(k\)-edge intersecting \(T\), and nothing else.\N\NNow consider a random \(n\)-vertex \(k\)-uniform hypergraph \(K_p(n,k)\), where every edge is included independently with probability \(p\). We are interested in the subgraph of \(K_p(n,k)\) with matching number at most \(s\), and the largest possible number of edges. It is still the case that this maximum is also attained by a `trivial' subgraph, that is, just keeping at the edges intersecting a given \(s\)-sized set \(T\)? Indeed, such a result was known for \(s=1\), fixed \(p \in (0,1)\) and some values of \(k\), thanks to previous work of \textit{J. Balogh} et al. [Comb. Probab. Comput. 18, No. 5, 629--646 (2009; Zbl 1193.05118)].\N\NThe authors obtain a similar result for wider ranges of \(s\), \(k\), and \(p\), possibly depending on \(n\). There are two main results (Theorems 1.3 and 1.4) differing in their quantifications; the latter allows for larger values of \(s\) but worse values of \(p\). Complementing their result, the authors also identify some ranges of \(s\), \(p\), \(k\) where their main result does not hold, i.e., where the largest subgraph of \(K_p(n,k)\) with matching number \(s\) is not trivial.

Cites work

• Erdős-Ko-Rado for random hypergraphs: asymptotics and stability
• Erdős-Ko-Rado in random hypergraphs
• scientific article; zbMATH DE number 3221072 (Why is no real title available?)
• Improved bounds for Erdős' matching conjecture
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Matching theory
• On Erdős-Ko-Rado for random hypergraphs. I
• On Erdős-Ko-Rado for random hypergraphs. II
• On maximal paths and circuits of graphs
• Resilient hypergraphs with fixed matching number
• SETS OF INDEPENDENT EDGES OF A HYPERGRAPH
• Sharp threshold for the Erdős–Ko–Rado theorem
• The Erdős matching conjecture and concentration inequalities
• Turán graphs with bounded matching number

This page was built for publication: On the matching problem in random hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6883688)