ترغب بنشر مسار تعليمي؟ اضغط هنا

Hamiltonian paths and cycles in some 4-uniform hypergraphs

91   0   0.0 ( 0 )
 نشر من قبل Xiaonan Liu
 تاريخ النشر 2021
  مجال البحث
والبحث باللغة English




اسأل ChatGPT حول البحث

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$.



قيم البحث

اقرأ أيضاً

89 - Oliver Cooley 2021
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.
92 - Luyining Gan , Jie Han , Lin Sun 2021
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-disj oint 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)}$ c ontains 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 deter mine 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 gi ve 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.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا