Skip to content
Preprint

Tight Hamiltonian Cycles in Uniformly Dense $3$-Graphs

Aug 2026 · 0 citations · 38 references
Mathematics

Abstract

We study minimum degree conditions for tight Hamiltonian cycles in uniformly dense $3$-uniform hypergraphs. We prove that for every $d,\alpha>0$, every sufficiently large $(\rho,d)$-dense $3$-graph on $n$ vertices with minimum codegree at least $(1/3+\alpha)n$ contains a tight Hamiltonian cycle. This resolves a problem of Aigner-Horev and Levy in a stronger form, and the constant $1/3$ is asymptotically best possible. We also show that uniform density does not lower the asymptotic vertex-degree threshold: there are $(\rho,d)$-dense $3$-graphs with minimum vertex degree $(5/9-o(1))\binom{n}{2}$ and no tight Hamiltonian cycle. Finally, we construct $(\rho,2-\sqrt{3})$-dense examples with minimum codegree $(2-\sqrt{3}-o(1))n$ and no tight Hamiltonian cycle, answering negatively a question of Ara{\'u}jo, Piga and Schacht.

View source

Similar papers

Preprint Aug 2026

Hamiltonian graphs with prescribed minimum degree and no near-spanning cycles

In 1984, Roland H\"{a}ggkvist posed the problem of constructing Hamiltonian graphs of order $n$ with large minimum degree and no $(n-2)$-cycle. He remarked that he did not know of such a graph with minimum degree at least three. We solve this problem by proving the following two results. (1) For every integer $d\ge 3$...

Xing-Zhi Zhan · 0 citations
Preprint Aug 2026

Sparse chromatic graphs and the complete-graph triangle bound

We prove that there is an absolute constant $c>0$ such that every graph of chromatic number at least $r$ and at most $cr^3\log^2 r$ edges contains at least $\binom r3$ triangles. The proof has three ingredients. First, a sparse-core argument based on a triangle-sensitive coloring estimate of Harris extracts, from any c...

Shu-Yan Chen · 0 citations
Preprint Oct 2026

Optimal Bounds on Spanning Tree Embeddings

We prove that the number of labelled embeddings of any $n$-vertex tree $T$ into an $n$-vertex graph $G$ of maximum degree $d$ satisfies $$ \mathrm{inj}(T,G) \leq (d/e)^n \exp(o_d(1) n). $$ The bound is sharp up to determining $o_d(1)$, even for paths, and the dependence of the error $\exp(o_d(1)n)$ on $d$ is necessary....

Csongor Beke, V. Boskovic, Nina Kamčev et al. · 0 citations
Preprint Sep 2026

Exact local spectral thresholds for perfect matchings in $3$-graphs and $3$-partite $3$-graphs

For a $3$-uniform hypergraph $H$, let $\sigma(H)$ be the minimum over the vertices of $H$ of the spectral radius of the link. Lin, Lu, Yuan and Zhao conjectured that $\sigma(H)>\tfrac{2n}3-2$ forces a perfect matching in a $3$-graph of order $n$ divisible by three, and Lu and Yuan conjectured that $\sigma(H)>\tau(q)$ f...

Pei Liu, O. Suil · 0 citations
Preprint Oct 2026

Extremal spectral gap of regular graphs with bounded vertex connectivity

The well-known inequality of Fiedler ensures that the spectral gap $r-\lambda_2(G)$ of a connected non-complete $r$-regular graph $G$ is bounded from above by the vertex connectivity $\kappa(G)$ of $G$. We prove that, for integers $t\geq2$ and $r>2t^2$, every connected $r$-regular graph with vertex connectivity at most...

Yu Wang, Sanming Zhou · 0 citations
Preprint Sep 2026

Bounded chromatic number of graphs with small clique number and large minimum degree

We prove that every triangle-free graph with minimum degree at least $\frac{n}{3}$ is $4$-colorable and thereby settle a problem of Brandt and Thomass\'e (2005) at the threshold $\frac{n}{3}$. The number four is best possible. For a positive integer-valued function $f(n)=o(n)$, we relate the chromatic number of $f(n)$-...

Jia-Ao Li, Xin-Yuan Li · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.