The maximum number of cliques in hypergraphs without large matchings (Q2205126)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The maximum number of cliques in hypergraphs without large matchings |
scientific article |
Statements
The maximum number of cliques in hypergraphs without large matchings (English)
0 references
20 October 2020
0 references
Summary: Let \([n]\) denote the set \(\{1, 2, \ldots, n\}\) and \(\mathcal{F}^{(r)}_{n,k,a}\) be an \(r\)-uniform hypergraph on the vertex set \([n]\) with edge set consisting of all the \(r\)-element subsets of \([n]\) that contains at least \(a\) vertices in \([ak+a-1]\). For \(n\geq 2rk\), \textit{P. Frankl} [J. Comb. Theory, Ser. A 120, No. 5, 1068--1072 (2013; Zbl 1277.05123)] proved that \(\mathcal{F}^{(r)}_{n,k,1}\) maximizes the number of edges in \(r\)-uniform hypergraphs on \(n\) vertices with the matching number at most \(k\). \textit{H. Huang} et al. [Comb. Probab. Comput. 21, No. 3, 442--450 (2012; Zbl 1242.05268)] considered a multicolored version of the Erdős matching conjecture, and provided a sufficient condition on the number of edges for a multicolored hypergraph to contain a rainbow matching of size \(k\). \par In this paper, we show that \(\mathcal{F}^{(r)}_{n,k,a}\) maximizes the number of \(s\)-cliques in \(r\)-uniform hypergraphs on \(n\) vertices with the matching number at most \(k\) for sufficiently large \(n\), where \(a=\lfloor \frac{s-r}{k} \rfloor+1\). We also obtain a condition on the number of \(s\)-clques for a multicolored \(r\)-uniform hypergraph to contain a rainbow matching of size \(k\), which reduces to the condition of H. Huang et al. [loc. cit.] when \(s=r\).
0 references
matching number
0 references
Erdős conjecture
0 references
Katona's theorem on shadows of intersecting hypergraphs
0 references