Berge tight cycles of all lengths in hypergraphs
이 뉴스, 어떠셨어요?
한 번의 탭으로 반응을 남겨요 · 로그인 불필요
Abstract
Given a set $R$ of positive integers, an $R$-graph $H = (V, E)$ is a hypergraph where the cardinality of each hyperedge belongs to $R$. If $R = \{r\}$, we sometimes refer to the hypergraph as an $r$-graph rather than an $R$-graph. For a set $S \subseteq V$, let $d_H(S)$ denote the number of hyperedges of $H$ containing $S$. Given a nonnegative integer $s$, the minimum $s$-degree $\delta_s(H)$ is the minimum of $d_H(S)$ over all $s$-vertex subsets $S$ of $V$. Let $r$ and $t$ be positive integers with $r < t$. We denote by $C_t^r$ the $t$-vertex $r$-uniform tight cycle, which is an $r$-graph with at least three hyperedges whose vertices admit a cyclic ordering such that every $r$ consecutive vertices form a hyperedge. In particular, $C_t^2$ is the classical cycle $C_t$ in $2$-graphs. For hypergraphs $F$ and $H$, we say that $H$ is a Berge-$F$ if there exist an injection $f \colon V(F) \to V(H)$ and a bijection $g \colon E(F) \to E(H)$ such that $\{f(v): v \in e\} \subseteq g(e)$ for all $e \in E(F)$.
Lu and Wang [Discrete Math. 344 (2021), 112462] proved that every $[3]$-graph $H$ on $n \geq 6$ vertices with $\delta_2(H) \geq 1$ contains a Berge-$C_t$ for all $3 \leq t \leq n$. In this paper, we prove that for any positive integer $r$ and any set $R \subseteq [k]$ with $k \geq 2$, there exists an integer $n_0 = n_0(k,r)$ such that every $R$-graph $H$ on $n \geq n_0$ vertices with $\delta_r(H) \geq 1$ contains a Berge-$C_t^r$ for all $r+1 \leq t \leq n$. In particular, when $k = 4$ and $r = 3$, we show that every $[4]$-graph $H$ on $n \geq 9$ vertices with $\delta_3(H) \geq 1$ contains a Berge-$C_t^3$ for all $4 \leq t \leq n$. We also characterize all the counterexamples when $4 \leq n \leq 8$.