首页|Hamiltonian cycles above expectation in r-graphs and quasi-random r-graphs
Hamiltonian cycles above expectation in r-graphs and quasi-random r-graphs
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NSTL
Elsevier
Let H-r(n, p) denote the maximum number of Hamiltonian cycles in an n-vertex r-graph with density p is an element of (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)!/2and in the random graph model G(r)(n, m) with m = p(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 pcan be larger than E(n, p) by a polynomial factor. For hypergraphs (i.e. r >= 3) the situation is drastically different. For all r >= 3 it is proved that H-r(n, p) is larger than E(n, p) by an exponentialfactor and, moreover, there are quasi-random r-graphs with density pwhose number of Hamiltonian cycles is larger than E(n, p) by an exponential factor. (C) 2021 Elsevier Inc. All rights reserved.
NSTL
Elsevier
