论文标题
哈密顿的周期高于R图和准随机R图的预期
Hamiltonian cycles above expectation in r-graphs and quasi-random r-graphs
论文作者
论文摘要
令$ h_r（n，p）$表示在$ n $ -vertex $ r $ -graph（0,1）$中的汉密尔顿周期数量的最大数量。随机$ r $ -graph模型$ g_r（n，p）$是$ e（n，p）= p^n（n-1）！/2 $以及随机图型$ g_r $ g_r（n，m）$，带有$ m = p \ binom {n} {r} $比$ y（n it y y y y y y y y limper p）对于图形，$ H_2（n，p）$被一个多项式因素证明仅大于$ e（n，p）$，这是一个开放的问题，无论是否通过多项式因素可以大于$ p $的准随机图大于$ e（n，p）$。对于超图（即$ r \ ge 3 $），情况大不相同。对于所有$ r \ ge 3 $，证明$ h_r（n，p）$由{\ em depentential}因子大于$ e（n，p）$，此外，有一个准密度$ p $的准r $ r $ r $ r $ praphs，其密度$ p $的汉密尔顿周期的数量比$ e（n，p）$ e Expentient actextentian $ e（p）。
Let $H_r(n,p)$ denote the maximum number of Hamiltonian cycles in an $n$-vertex $r$-graph with density $p \in (0,1)$. The expected number of Hamiltonian cycles in the random $r$-graph model $G_r(n,p)$ is $E(n,p)=p^n(n-1)!/2$ and in the random graph model $G_r(n,m)$ with $m=p\binom{n}{r}$ it is, in fact, slightly smaller than $E(n,p)$. For graphs, $H_2(n,p)$ is proved to be only larger than $E(n,p)$ by a polynomial factor and it is an open problem whether a quasi-random graph with density $p$ can be larger than $E(n,p)$ by a polynomial factor. For hypergraphs (i.e. $r \ge 3$) the situation is drastically different. For all $r \ge 3$ it is proved that $H_r(n,p)$ is larger than $E(n,p)$ by an {\em exponential} factor and, moreover, there are quasi-random $r$-graphs with density $p$ whose number of Hamiltonian cycles is larger than $E(n,p)$ by an exponential factor.
