论文标题
有限度超图中的许多集团
Many cliques in bounded-degree hypergraphs
论文作者
论文摘要
最近，蔡斯（Chase）确定了$ n $顶点的最大尺寸$ t $ $ t $ t $的总数。不久之后，Chakraborti和Chen回答了这个问题的版本，我们要求该图具有$ M $边缘和固定的最高度（而不对顶点的数量施加任何限制）。在本文中，我们解决了超图上的这些问题。对于$ s $ - 绘图，带有$ s \ ge 3 $，出现在图案中未出现的许多问题。例如，对于一般$ s $绘图，我们可以将学位分配给带有$ 1 \ le i i \ le s-1 $的顶点设置的任何$ i $ -subset。 我们在$ s-graph $ \ mathcal {h} $中以$ i $ -Degree在三个上下文中界限$ i $ -Degree的$ t $ cliques数量：$ \ nathcal {h} $具有$ n $ vertices; $ \ MATHCAL {H} $具有$ M $（超级）边缘； （概括以前的情况）$ \ MATHCAL {H} $具有固定的数字$ p $ $ u $ -cliques，对于某些$ u $，带有$ s \ le u \ le \ le \ le t $。当$δ$是一种特殊形式时，我们表征了极端$ s $ graphs，并证明边界很紧。这些极端示例是Steiner系统或部分Steiner系统的阴影。在证明我们的独特性结果的路上，我们将Füredi和Griggs的结果扩展到Kruskal-Katona的独特性，从影子案件到集团案例。
Recently Chase determined the maximum possible number of cliques of size $t$ in a graph on $n$ vertices with given maximum degree. Soon afterward, Chakraborti and Chen answered the version of this question in which we ask that the graph have $m$ edges and fixed maximum degree (without imposing any constraint on the number of vertices). In this paper we address these problems on hypergraphs. For $s$-graphs with $s\ge 3$ a number of issues arise that do not appear in the graph case. For instance, for general $s$-graphs we can assign degrees to any $i$-subset of the vertex set with $1\le i\le s-1$. We establish bounds on the number of $t$-cliques in an $s$-graph $\mathcal{H}$ with $i$-degree bounded by $Δ$ in three contexts: $\mathcal{H}$ has $n$ vertices; $\mathcal{H}$ has $m$ (hyper)edges; and (generalizing the previous case) $\mathcal{H}$ has a fixed number $p$ of $u$-cliques for some $u$ with $s\le u \le t$. When $Δ$ is of a special form we characterize the extremal $s$-graphs and prove that the bounds are tight. These extremal examples are the shadows of either Steiner systems or partial Steiner systems. On the way to proving our uniqueness results, we extend results of Füredi and Griggs on uniqueness in Kruskal-Katona from the shadow case to the clique case.
