论文标题
没有大匹配的超图中最大数量
The Maximum Number of Cliques in Hypergraphs without Large Matchings
论文作者
论文摘要
令$ [n] $表示集合$ \ {1，2，\ ldots，n \} $和$ \ Mathcal {f}^{（r）} _ {n，k，k，a} $是$ r $ r $ rub-robiform-suiltermy hypergraph in the $ rement $ rement $ rement $ rement $ -Element $ -Element n N.在$ [AK+A-1] $中。对于$ n \ geq 2rk $，弗兰克尔证明了$ \ Mathcal {f}^{（r）} _ {n，k，1} $最大化$ r $ r $ rob-robil-N $ Vertices上的边缘数，最多是$ k $。黄，Loh和Sudakov考虑了Erds匹配猜想的多色版本，并为多色HyperGraph的边缘数量提供了足够的条件，以包含尺寸$ K $的彩虹匹配。在本文中，我们表明$ \ Mathcal {f}^{（r）} _ {n，k，a} $最大化$ r $ r $ r $均匀的$ n $ n $ pertices中的$ s $ cliques的数量，最大值的$ n $ pertices，最大的$ k $，最大的$ k $，在$ k $中，$ n $ a $ a $ a = \ rfloor+1 $。我们还获得了$ s $ clques数量的条件，用于$ r $ r $均匀的超图，以包含尺寸$ k $的彩虹匹配，当$ k $的情况下，当$ s = r $时，它会降低Huang，Loh和Sudakov的状态。
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$, Frankl 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$. Huang, Loh and Sudakov 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$. 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 Huang, Loh and Sudakov when $s=r$.
