Search

For a $k$-uniform hypergraph (or simply $k$-graph) $F$, the codegree Tur\'{a}n density $\pi_{\mathrm{co}}(F)$ is the supremum over all $\alpha$ such that there exist arbitrarily large $n$-vertex $F$-free $k$-graphs $H$ in which every $(k-1)$-subset of $V(H)$ is contained in at least $\alpha n$ edges. Recently, it was proved that for every $3$-graph $F$, $\pi_{\mathrm{co}}(F)=0$ implies $\pi_{\therefore}(F)=0$, where $\pi_{\therefore}(F)$ is the uniform Tur\'{a}n density of $F$ and is defined as the supremum over all $d$ such that there are infinitely many $F$-free $k$-graphs $H$ satisfying that any induced linear-size subhypergraph of $H$ has edge density at least $d$. In this paper, we introduce a layered structure for $3$-graphs which allows us to obtain the reverse implication: every layered $3$-graph $F$ with $\pi_{\therefore}(F)=0$ satisfies $\pi_{\mathrm{co}}(F)=0$. Along the way, we answer in the negative a question of Falgas-Ravry, Pikhurko, Vaughan and Volec [J. London Math. Soc., 2023] about whether $\pi_{\therefore}(F)\leq\pi_{\mathrm{co}}(F)$ always holds. In particular, we construct counterexamples $F$ with positive but arbitrarily small $\pi_{\mathrm{co}}(F)$ while having $\pi_{\therefore}(F)\ge 4/27$., Comment: 17 pages. This work will be merged with arXiv:2312.02879

For a $k$-uniform hypergraph (or simply $k$-graph) $F$, the codegree Tur\'{a}n density $\pi_{\mathrm{co}}(F)$ is the infimum over all $\alpha$ such that any $n$-vertex $k$-graph $H$ with every $(k-1)$-subset of $V(H)$ contained in at least $\alpha n$ edges has a copy of $F$. The uniform Tur\'{a}n density $\pi_{\therefore}(F)$ is the supremum over all $d$ such that there are infinitely many $F$-free $k$-graphs $H$ satisfying that any linear-size subhypergraph of $H$ has edge density at least $d$. Falgas-Ravry, Pikhurko, Vaughan and Volec [J. London Math. Soc., 2023] asked whether for every $3$-graph $F$, $\pi_{\therefore}(F)\leq\pi_{\mathrm{co}}(F)$. We provide a positive answer to this question provided that $\pi_{\mathrm{co}}(F)=0$. Our proof relies on a random geometric construction and a new formulation of the characterization of $3$-graphs with vanishing uniform Tur\'{a}n density due to Reiher, R{\"o}dl and Schacht [J. London Math. Soc., 2018]. Along the way, we answer a question of Falgas-Ravry, Pikhurko, Vaughan and Volec about subhypergraphs with linear minimum codegree in uniformly dense hypergraphs in the negative., Comment: 10 pages

Given $k\ge 2$ and two $k$-graphs ($k$-uniform hypergraphs) $F$ and $H$, an \emph{$F$-factor} in $H$ is a set of vertex disjoint copies of $F$ that together covers the vertex set of $H$. Lenz and Mubayi studied the $F$-factor problems in quasi-random $k$-graphs with minimum degree $\Omega(n^{k-1})$. In particular, they constructed a sequence of $1/8$-dense quasi-random $3$-graphs $H(n)$ with minimum degree $\Omega(n^2)$ and minimum codegree $\Omega(n)$ but with no $K_{2,2,2}$-factor. We prove that if $p>1/8$ and $F$ is a $3$-partite $3$-graph with $f$ vertices, then for sufficiently large $n$, all $p$-dense quasi-random $3$-graphs of order $n$ with minimum codegree $\Omega(n)$ and $f\mid n$ have $F$-factors. That is, $1/8$ is the density threshold for ensuring all $3$-partite $3$-graphs $F$-factors in quasi-random $3$-graphs given a minimum codegree condition $\Omega(n)$. Moreover, we show that one can not replace the minimum codegree condition by a minimum vertex degree condition. In fact, we find that for any $p\in(0,1)$ and $n\ge n_0$, there exist $p$-dense quasi-random $3$-graphs of order $n$ with minimum degree $\Omega (n^2)$ having no $K_{2,2,2}$-factor. In particular, we study the optimal density threshold of $F$-factors for each $3$-partite $3$-graph $F$ in quasi-random $3$-graphs given a minimum codegree condition $\Omega(n)$., Comment: 22 pages. Accepted by Journal of Combinatorial Theory, Series B

Given $k\ge 2$ and two $k$-graphs ($k$-uniform hypergraphs) $F$ and $H$, an $F$-factor in $H$ is a set of vertex-disjoint copies of $F$ that together covers the vertex set of $H$. Lenz and Mubayi [J. Combin. Theory Ser. B, 2016] studied the $F$-factor problem in quasi-random $k$-graphs with minimum degree $\Omega(n^{k-1})$. They posed the problem of characterizing the $k$-graphs $F$ such that every sufficiently large quasi-random $k$-graph with constant edge density and minimum degree $\Omega(n^{k-1})$ contains an $F$-factor, and in particular, they showed that all linear $k$-graphs satisfy this property. In this paper we prove a general theorem on $F$-factors which reduces the $F$-factor problem of Lenz and Mubayi to a natural sub-problem, that is, the $F$-cover problem. By using this result, we answer the question of Lenz and Mubayi for those $F$ which are $k$-partite $k$-graphs, and for all 3-graphs $F$, separately. Our characterization result on 3-graphs is motivated by the recent work of Reiher, R\"odl and Schacht [J. Lond. Math. Soc., 2018] that classifies the 3-graphs with vanishing Tur\'an density in quasi-random $k$-graphs., Comment: 28pages

Properly colored cycles in edge-colored graphs are closely related to directed cycles in oriented graphs. As an analogy of the well-known Caccetta-H\"{a}ggkvist Conjecture, we study the existence of properly colored cycles of bounded length in an edge-colored graph. We first prove that for all integers $s$ and $t$ with $t\geq s\geq2$, every edge-colored graph $G$ with no properly colored $K_{s,t}$ contains a spanning subgraph $H$ which admits an orientation $D$ such that every directed cycle in $D$ is a properly colored cycle in $G$. Using this result, we show that for $r\geq4$, if the Caccetta-H\"{a}ggkvist Conjecture holds , then every edge-colored graph of order $n$ with minimum color degree at least $n/r+2\sqrt{n}+1$ contains a properly colored cycle of length at most $r$. In addition, we also obtain an asymptotically tight total color degree condition which ensures a properly colored (or rainbow) $K_{s,t}$., Comment: 17 pages, 0 figure