Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userHamilton cycles in quasirandom hypergraphs
163
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
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$.
Let $Y_{3,2}$ be the $3$-uniform hypergraph with two edges intersecting in two vertices. Our main result is that any $n$-vertex 3-uniform hypergraph with at least $binom{n}{3} - binom{n-m+1}{3} + o(n^3)$ edges contains a collection of $m$ vertex-disjoint copies of $Y_{3,2}$, for $mle n/7$. The bound on the number of edges is asymptotically best possible. This can be viewed as a generalization of the ErdH{o}s Matching Conjecture.We then use this result together with the absorbing method to determine the asymptotically best possible minimum $(k-3)$-degree threshold for $ell$-Hamiltonicity in $k$-graphs, where $kge 7$ is odd and $ell=(k-1)/2$. Moreover, we give related results on $ Y_{k,b} $-tilings and Hamilton $ ell $-cycles with $ d $-degree for some other $ k,ell,d $.
Chung, Graham, and Wilson proved that a graph is quasirandom if and only if there is a large gap between its first and second largest eigenvalue. Recently, the authors extended this characterization to k-uniform hypergraphs, but only for the so-called coregular k-uniform hypergraphs. In this paper, we extend this characterization to all k-uniform hypergraphs, not just the coregular ones. Specifically, we prove that if a k-uniform hypergraph satisfies the correct count of a specially defined four-cycle, then there is a gap between its first and second largest eigenvalue.
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}$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
