Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userHamiltonian paths and cycles in some 4-uniform hypergraphs
91
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In 1999, Katona and Kierstead conjectured that if a $k$-uniform hypergraph $cal H$ on $n$ vertices has minimum co-degree $lfloor frac{n-k+3}{2}rfloor$, i.e., each set of $k-1$ vertices is contained in at least $lfloor frac{n-k+3}{2}rfloor$ edges, then it has a Hamiltonian cycle. R{o}dl, Ruci{n}ski and Szemer{e}di in 2011 proved that the conjecture is true when $k=3$ and $n$ is large. We show that this Katona-Kierstead conjecture holds if $k=4$, $n$ is large, and $V({cal H})$ has a partition $A$, $B$ such that $|A|=lceil n/2rceil$, $|{ein E({cal H}):|e cap A|=2}| <epsilon n^4$.
rate research
Read More
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.
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 $.
A $k$-uniform tight cycle is a $k$-uniform hypergraph with a cyclic ordering of its vertices such that its edges are all the sets of size $k$ formed by $k$ consecutive vertices in the ordering. We prove that every red-blue edge-coloured $K_n^{(4)}$ contains a red and a blue tight cycle that are vertex-disjoint and together cover $n-o(n)$ vertices. Moreover, we prove that every red-blue edge-coloured $K_n^{(5)}$ contains four monochromatic tight cycles that are vertex-disjoint and together cover $n-o(n)$ vertices.
Given integers $k,j$ with $1le j le k-1$, we consider the length of the longest $j$-tight path in the binomial random $k$-uniform hypergraph $H^k(n,p)$. We show that this length undergoes a phase transition from logarithmic length to linear and determine the critical threshold, as well as proving upper and lower bounds on the length in the subcritical and supercritical ranges. In particular, for the supercritical case we introduce the `Pathfinder algorithm, a depth-first search algorithm which discovers $j$-tight paths in a $k$-uniform hypergraph. We prove that, in the supercritical case, with high probability this algorithm will find a long $j$-tight path.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
