Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFinding tight Hamilton cycles in random hypergraphs faster
93
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In an $r$-uniform hypergraph on $n$ vertices a tight Hamilton cycle consists of $n$ edges such that there exists a cyclic ordering of the vertices where the edges correspond to consecutive segments of $r$ vertices. We provide a first deterministic polynomial time algorithm, which finds a.a.s. tight Hamilton cycles in random $r$-uniform hypergraphs with edge probability at least $C log^3n/n$. Our result partially answers a question of Dudek and Frieze [Random Structures & Algorithms 42 (2013), 374-385] who proved that tight Hamilton cycles exists already for $p=omega(1/n)$ for $r=3$ and $p=(e + o(1))/n$ for $rge 4$ using a second moment argument. Moreover our algorithm is superior to previous results of Allen, Bottcher, Kohayakawa and Person [Random Structures & Algorithms 46 (2015), 446-465] and Nenadov and v{S}koric [arXiv:1601.04034] in various ways: the algorithm of Allen et al. is a randomised polynomial time algorithm working for edge probabilities $pge n^{-1+varepsilon}$, while the algorithm of Nenadov and v{S}koric is a randomised quasipolynomial time algorithm working for edge probabilities $pge Clog^8n/n$.
rate research
Read More
We show that, for a natural notion of quasirandomness in $k$-uniform hypergraphs, any quasirandom $k$-uniform hypergraph on $n$ vertices with constant edge density and minimum vertex degree $Omega(n^{k-1})$ contains a loose Hamilton cycle. We also give a construction to show that a $k$-uniform hypergraph satisfying these conditions need not contain a Hamilton $ell$-cycle if $k-ell$ divides $k$. The remaining values of $ell$ form an interesting open question.
A tight Hamilton cycle in a $k$-uniform hypergraph ($k$-graph) $G$ is a cyclic ordering of the vertices of $G$ such that every set of $k$ consecutive vertices in the ordering forms an edge. R{o}dl, Ruci{n}ski, and Szemer{e}di proved that for $kgeq 3$, every $k$-graph on $n$ vertices with minimum codegree at least $n/2+o(n)$ contains a tight Hamilton cycle. We show that the number of tight Hamilton cycles in such $k$-graphs is $exp(nln n-Theta(n))$. As a corollary, we obtain a similar estimate on the number of Hamilton $ell$-cycles in such $k$-graphs for all $ellin{0,dots,k-1}$, which makes progress on a question of Ferber, Krivelevich and Sudakov.
Given an $n$ vertex graph whose edges have colored from one of $r$ colors $C={c_1,c_2,ldots,c_r}$, we define the Hamilton cycle color profile $hcp(G)$ to be the set of vectors $(m_1,m_2,ldots,m_r)in [0,n]^r$ such that there exists a Hamilton cycle that is the concatenation of $r$ paths $P_1,P_2,ldots,P_r$, where $P_i$ contains $m_i$ edges. We study $hcp(G_{n,p})$ when the edges are randomly colored. We discuss the profile close to the threshold for the existence of a Hamilton cycle and the threshold for when $hcp(G_{n,p})={(m_1,m_2,ldots,m_r)in [0,n]^r:m_1+m_2+cdots+m_r=n}$.
Inspired by the study of loose cycles in hypergraphs, we define the emph{loose core} in hypergraphs as a structure which mirrors the close relationship between cycles and $2$-cores in graphs. We prove that in the $r$-uniform binomial random hypergraph $H^r(n,p)$, the order of the loose core undergoes a phase transition at a certain critical threshold and determine this order, as well as the number of edges, asymptotically in the subcritical and supercritical regimes. Our main tool is an algorithm called CoreConstruct, which enables us to analyse a peeling process for the loose core. By analysing this algorithm we determine the asymptotic degree distribution of vertices in the loose core and in particular how many vertices and edges the loose core contains. As a corollary we obtain an improved upper bound on the length of the longest loose cycle in $H^r(n,p)$.
We prove a lower bound on the length of the longest $j$-tight cycle in a $k$-uniform binomial random hypergraph for any $2 le j le k-1$. We first prove the existence of a $j$-tight path of the required length. The standard sprinkling argument is not enough to show that this path can be closed to a $j$-tight cycle -- we therefore show that the path has many extensions, which is sufficient to allow the sprinkling to close the cycle.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
