论文标题
计算大周长的超图
Counting Hypergraphs with Large Girth
论文作者
论文摘要
莫里斯（Morris）和萨克斯顿（Saxton）使用容器的方法来绑定$ n $ vertex图的数量，其中包含$ \ ell $ -cycles的$ m $边缘，因此腰围的图形超过$ \ ell $。我们认为对$ r $均匀的超图的概括。超graph $ h $的{\ em girth}是最低$ \ ell $，因此对于某些$ f \ subseteq h $，存在Bookjection $ ϕ：e（c_ \ ell）\ to E（f）$，to E（f）$ a $ e \ e \ subseteq（e subSeteq（e）$ e（e）$ e（e）$ e（e）$ e e（e）in El（c_ \ el ell）$。让$ n_m^r（n，\ ell）$表示$ n $ -vertex $ r $ r $ r $均匀的超图的数量，带有$ m $边缘，大于$/ n_m^2（n，\ ell）^{r -1 +λ} \]，当$ \ ell -2 $ 2 $ divides $ r -2 $ dist $ 1 + o（1）$（1）$（1）$（1）$（1）$（1）。该结果用于解决围绕腰围的极端问题，超过$ \ ell $在随机$ r $ r $均匀的超图中。
Morris and Saxton used the method of containers to bound the number of $n$-vertex graphs with $m$ edges containing no $\ell$-cycles, and hence graphs of girth more than $\ell$. We consider a generalization to $r$-uniform hypergraphs. The {\em girth} of a hypergraph $H$ is the minimum $\ell$ such that for some $F \subseteq H$, there exists a bijection $ϕ: E(C_\ell) \to E(F)$ with $e\subseteq ϕ(e)$ for all $e\in E(C_\ell)$. Letting $N_m^r(n,\ell)$ denote the number of $n$-vertex $r$-uniform hypergraphs with $m$ edges and girth larger than $\ell$ and defining $λ= \lceil (r - 2)/(\ell - 2)\rfloor$, we show \[ N_m^r(n,\ell) \leq N_m^2(n,\ell)^{r - 1 + λ}\] which is tight when $\ell - 2 $ divides $r - 2$ up to a $1 + o(1)$ term in the exponent. This result is used to address the extremal problem for subgraphs of girth more than $\ell$ in random $r$-uniform hypergraphs.
