\documentclass[12pt]{article} \usepackage{e-jc} \usepackage{amssymb,amsmath,amsthm, calc, graphicx} \usepackage{epsfig} \usepackage{breqn} \usepackage{footnpag} \usepackage{rotating} \usepackage{amsfonts} \usepackage{setspace} \usepackage{fullpage} \usepackage{enumitem} \usepackage{bbold} \usepackage{comment} \usepackage{pgf,tikz} \usepackage{mathrsfs} \usetikzlibrary{arrows} \usepackage{yhmath} %\usepackage{hyperref} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \dateline{Sep 16, 2017}{Apr 14, 2018}{TBD} \MSC{05C35, 05C69} \Copyright{ The authors. Released under the CC BY-ND license (International 4.0).} \bibliographystyle{plain} %% THEOREM TYPE %\newtheorem{thm}{Theorem}%[section] %\newtheorem{definition}{Definition} %\newtheorem{claim}[thm]{Claim} %\newtheorem{lemma}[thm]{Lemma} %\newtheorem{corollary}[thm]{Corollary} %\newtheorem{problem}[thm]{Problem} %\newtheorem{notation}[thm]{Notation} %\newtheorem{remark}[thm]{Remark} %\newtheorem{conjecture}[thm]{Conjecture} %\newtheorem{observation}[thm]{Observation} %\newtheorem*{cons}{Construction} %\newtheorem{case}{Case} %\newcommand{\thistheoremname}{} %\newtheorem*{genericthm*}{\thistheoremname} %\newenvironment{namedthm*}[1] %{\renewcommand{\thistheoremname}{#1}% % \begin{genericthm*}} % {\end{genericthm*}} % %\newtheorem{innercustomthm}{Case} %\newenvironment{Casethm}[1] % {\renewcommand\theinnercustomthm{#1}\innercustomthm} % {\endinnercustomthm} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \def\ul{\underline} \newcommand{\F}{\mathcal{F}} \renewcommand{\L}{\mathcal{L}} \newcommand{\M}{\mathcal{M}} \newcommand{\U}{\mathcal{U}} \newcommand{\Y}{\mathcal{Y}} \newcommand{\A}{\mathcal{A}} \newcommand{\I}{\mathcal{I}} \renewcommand{\O}{\mathcal{O}} \newcommand{\D}{\mathcal{D}} \renewcommand{\P}{\mathcal{P}} \newcommand{\N}{\mathcal{N}} \newcommand{\abs}[1]{\left\lvert{#1}\right\rvert} \author{Beka Ergemlidze\\ \small Department of Mathematics\\[-0.8ex] \small Central European University\\[-0.8ex] \small Budapest, Hungary.\\ \small\tt beka.ergemlidze@gmail.com\\ \and Ervin Gy\H{o}ri\\ \small Alfr\'ed R\'enyi Institute of Mathematics\\[-0.8ex] \small Hungarian Academy of Sciences\\[-0.8ex] \small and \\[-0.8ex] \small Central European University\\[-0.8ex] \small Budapest, Hungary.\\ \small\tt gyori.ervin@renyi.mta.hu \\ \and Abhishek Methuku \\ \small Department of Mathematics\\[-0.8ex] \small Central European University\\[-0.8ex] \small Budapest, Hungary.\\ \small\tt abhishekmethuku@gmail.com\\} \title{A Note on the Linear Cycle Cover Conjecture \\ of Gy\'arf\'as and S\'ark\"ozy} %\author{ % Beka Ergemlidze\thanks{ % Department of Mathematics, Central European University, Budapest. % E-mail: beka.ergemlidze@gmail.com % } \qquad Ervin Gy\H{o}ri \thanks{R\'enyi Institute, Hungarian Academy of Sciences and % Department of Mathematics, Central European University, Budapest. E-mail: gyori.ervin@renyi.mta.hu} \qquad Abhishek Methuku \thanks{Department of Mathematics, Central European University, Budapest. E-mail: abhishekmethuku@gmail.com} %} \begin{document} %\author{Beka Ergemlidze \and Ervin Gy\H{o}ri \and Abhishek Methuku} \maketitle %\begin{abstract} %In this paper we continue the work of Gyr\'af\'as, Simonovits and the second author on $3$-uniform hypergraphs without linear cycles and answer some questions posed by them. Our main results are the following. % %We show that if a 3-uniform hypergraph $H$ without linear cycles, contains no %subhypergraph $K_5^3$, then it is $2$-colorable. This implies that the independence number of such hypergraphs is at least $\lceil \frac{V(H)}{2} \rceil$. We prove that this bound is sharp. % %We also show that a $3$-uniform hypergraph without linear cycles, on $n \ge 10$ vertices has a vertex of degree at most $n-2$. %\end{abstract} \begin{abstract} A linear cycle in a $3$-uniform hypergraph $H$ is a cyclic sequence of hyperedges such that any two consecutive hyperedges intersect in exactly one element and non-consecutive hyperedges are disjoint. Let $\alpha(H)$ denote the size of a largest independent set of $H$. We show that the vertex set of every $3$-uniform hypergraph $H$ can be covered by at most $\alpha(H)$ edge-disjoint linear cycles (where we accept a vertex and a hyperedge as a linear cycle), proving a weaker version of a conjecture of Gy\'arf\'as and S\'ark\"ozy. \end{abstract} \section{Introduction} A well-known theorem of P\'osa \cite{Posa} states that the vertex set of every graph $G$ can be partitioned into at most $\alpha(G)$ cycles where $\alpha(G)$ denotes the independence number of $G$ (where a vertex or an edge is accepted as a cycle). \begin{definition} \label{linear_cycle_def} A \emph{(linear cycle) linear path} is a (cyclic) sequence of hyperedges such that two consecutive hyperedges intersect in exactly one element and two non-consecutive hyperedges are disjoint. %from a vertex by repeatedly adding hyperedges so that the next hyperedge always intersects the previous hyperedge in a vertex of degree one. A \emph{linear cycle} is obtained from a linear path of at least two hyperedges, by adding a hyperedge that intersects the first and last hyperedges of the linear path in one of their degree one vertices. \end{definition} An independent set of a hypergraph $H$ is a set of vertices that contain no hyperedges of $H$. Let $\alpha(H)$ denote the size of a largest independent set of $H$ and we call it the independence number of $H$. Gy\'arf\'as and S\'ark\"ozy \cite{Gy_Sar} conjectured that the following extension of P\'osa's theorem holds: One can partition every $k$-uniform hypergraph $H$ into at most $\alpha(H)$ linear cycles (here, as in P\'osa's theorem, vertices and subsets of hyperedges are accepted as linear cycles). In \cite{Gy_Sar} Gy\'arf\'as and S\'ark\"ozy prove a weaker version of their conjecture for \emph{weak} cycles (where only cyclically consecutive hyperedges intersect, but their intersection size is not restricted) instead of linear cycles. Recently, Gy\'arf\'as, Gy\H{o}ri and Simonovits \cite{GyGyoSim} showed that this conjecture is true for $k =3$ if we assume there are no linear cycles in $H$. \vspace{2mm} In this note, we show their conjecture is true for $k =3$ provided we allow the linear cycles to be edge-disjoint, instead of being vertex-disjoint. \begin{theorem} \label{mainthm} If $H$ is a $3$-uniform hypergraph, then its vertex set can be covered by at most $\alpha(H)$ edge-disjoint linear cycles (where we accept a single vertex or a hyperedge as a linear cycle). \end{theorem} Our proof uses induction on $\alpha(H)$. However, perhaps surprisingly, in order to make induction work, our main idea is to allow the hypergraph $H$ to contain hyperedges of size $2$ (in addition to hyperedges of size $3$). First we will delete some vertices, and add certain hyperedges of size $2$ into the remaining hypergraph so as to ensure the independence number of the remaining hypergraph is smaller than that of $H$. Then applying induction we will find edge-disjoint linear cycles (which may contain these added hyperedges) covering the remaining hypergraph. It will turn out that the added hyperedges behave nicely, allowing us to construct edge-disjoint linear cycles in $H$ covering all of its vertices. The detailed proof is given in the next section. %\begin{thm} % \label{mainthm} % The set of hyperedges of every $3$-uniform hypergraph can be partitioned into at most $\alpha(H)$ (edge-disjoint) linear cycles (where we accept a single vertex or a hyperedge as a cycle). %\end{thm} \section{Proof of Theorem \ref{mainthm}} We call a hypergraph \emph{mixed} if it can contain hyperedges of both sizes $2$ and $3$. A linear cycle in a mixed hypergraph is still defined according to Definition \ref{linear_cycle_def}. We will in fact prove our theorem for mixed hypergraphs (which is clearly a bigger class of hypergraphs than $3$-uniform hypergraphs). More precisely, we will prove the following stronger theorem. \begin{theorem} \label{stronger} If $H$ is a mixed hypergraph, then its vertex set $V(H)$ can be covered by at most $\alpha(H)$ edge-disjoint linear cycles (where we accept a single vertex or a hyperedge as a linear cycle). \end{theorem} \begin{proof} We prove the theorem by induction on $\alpha(H)$. If $\abs{V(H)}=1$ or $2$, then the statement is trivial. If $\abs{V(H)} \ge 3$ and $\alpha(H) = 1$, then $H$ contains all possible edges of size $2$ and there is a Hamiltonian cycle consisting only of edges of size $2$, which is of course a linear cycle covering $V(H)$. Let $\alpha(H) > 1$. If $E(H) = \emptyset$, then $\alpha(H) = V(H)$ and the statement of our theorem holds trivially since we accept each vertex as a linear cycle. If $E(H) \not = \emptyset$, then let $P$ be a longest linear path in $H$ consisting of hyperedges $h_0, h_1, \ldots, h_l$ ($l \ge 0$). If $h_i$ is of size $3$, then let $h_i = v_i v_{i+1} u_{i+1}$ and if it is of size $2$, then let $h_i = v_i v_{i+1}$. A linear subpath of $P$ starting at $v_0$ (i.e., a path consisting of hyperedges $h_0, h_1, \ldots, h_j$ for some $j \le l$) is called an \emph{initial segment} of $P$. Let $C$ be a linear cycle in $H$ which contains the longest initial segment of $P$. If there is no linear cycle containing $h_0$, then we simply let $C = h_0$. Let us denote the subhypergraph of $H$ induced on $V(H) \setminus V(C)$ by $H \setminus C$. Let $R = \{v_ku_k \mid \{v_k,u_k\} \subseteq V(P) \setminus V(C) \text{ and } v_0 v_k u_k \in E(H)\}$ be the set of \emph{red} edges. Let us construct a new hypergraph $H'$ where $V(H') = V(H) \setminus V(C)$ and $E(H') = E(H \setminus C) \cup R$. We will show that $\alpha(H') < \alpha(H)$ and any linear cycle cover of $H'$ can be extended to a linear cycle cover of $H$ by adding $C$ and extending the red edges by $v_0$. The following claim shows that the independence number of $H'$ is smaller than the independence number of $H$. This fact will later allow us to apply induction. \begin{claim} \label{independent} If $I$ is an independent set in $H'$, then $I \cup {v_0}$ is an independent set in $H$. \end{claim} \begin{proof} Suppose by contradiction that $h \subseteq (I \cup {v_0})$ for some $h \in E(H)$. Then, clearly $v_0 \in h$ because otherwise $I$ is not an independent set in $H'$. Now let us consider different cases depending on the size of $h \cap (V(P) \setminus V(C))$. If $\abs{h \cap (V(P) \setminus V(C))} = 0$ then, by adding $h$ to $P$, we can produce a longer path than $P$, a contradiction. If $\abs{h \cap (V(P) \setminus V(C))} = 1$, let $h \cap (V(P) \setminus V(C)) = \{x\}$. Then the linear subpath of $P$ between $v_0$ and $x$ together with $h$ forms a linear cycle which contains a larger initial segment of $P$ than $C$, a contradiction. If $\abs{h \cap (V(P) \setminus V(C))} = 2$, then let $h \cap (V(P) \setminus V(C)) = \{x,y\}$. Let us take smallest $i$ and $j$ such that $x \in h_i$ and $y \in h_j$ (i.e., if $x \in h_i \cap h_{i+1}$ then let us take $h_i$). If $i \not = j$, say $ i < j$ without loss of generality, then the linear subpath of $P$ between $v_0$ and $x$ together with $h$ forms a linear cycle with longer initial segment of $P$ than $C$, a contradiction. Therefore, $i = j$ but in this case, $\{x,y\}$ is a red edge and so at most one of them can be contained in $I$, contradicting the assumption that $h = v_0xy \subseteq (I \cup {v_0})$. Hence, $I \cup {v_0}$ is an independent set in $H$, as desired. \end{proof} The following claim will allow us to construct linear cycles in $H$ from red edges. \begin{claim} \label{onered} The set of hyperedges of every linear cycle in $H'$ contains at most one red edge. \end{claim} \begin{proof} Suppose by contradiction that there is a linear cycle $C'$ in $H'$ containing at least two hyperedges which are red edges. Then there is a linear subpath $P'$ of $C'$ consisting of hyperedges $h'_0,h'_1,\ldots,h'_m$ such that $h'_0 := v_su_s$ and $h'_m := v_tu_t$ (where $s > t$) are red edges but $h'_k$ is not a red edge for any $1 \le k \le m-1$. Let us first take the smallest $i$ such that $V(P') \cap h_i \not = \emptyset$ and then the smallest $j$ such that $h'_j \cap h_i \not = \emptyset$. It is easy to see that $\abs{V(P') \cap h_i} \le 2$ (since $i$ was smallest). If $\abs{h'_j \cap h_i} = 1$, then the linear cycle consisting of hyperedges $h'_1,\ldots,h'_j$ and $h_i, h_{i-1}, \ldots, h_0$ and $v_0v_su_s$ contains a larger initial segment of $P$ than $C$ (as $h'_j \cap h_i \in V(P) \setminus V(C)$), a contradiction. If $\abs{h'_j \cap h_i} = 2$, then notice that $\abs{h'_{j+1} \cap h_i} = 1$. Now the linear cycle consisting of the hyperedges $h'_{m-1}, h'_{m-2}, \ldots, h'_{j+1}$ and $h_i, h_{i-1}, \ldots, h_0$ and $v_0v_tu_t$ contains a larger initial segment of $P$ than $C$, a contradiction. \end{proof} %If $E(H') \not = \emptyset$, then there is a longest path in it, and so By Claim \ref{independent}, $\alpha(H') \le \alpha(H)-1$. So by induction hypothesis, $V(H')$ can be covered by at most $\alpha(H)-1$ edge-disjoint linear cycles (where we accept a single vertex or a hyperedge as a linear cycle). Now let us replace each red edge $\{x, y\}$ with the hyperedge $xyv_0$ of $H$. Claim \ref{onered} ensures that in each of these linear cycles, at most one of the hyperedges is a red edge. Therefore, it is easy to see that after the above replacement, linear cycles of $H'$ remain as \emph{linear} cycles in $H$ and they cover $V(H') = V(H) \setminus V(C)$. Now the linear cycle $C$, together with these linear cycles give us at most $\alpha(H)-1 +1 = \alpha(H)$ edge-disjoint linear cycles covering $V(H)$, completing the proof. \end{proof} %Gy\'arf\'as, Gy\H{o}ri and Simonovits \cite{GyGyoSim} initiated the study of linear cycle-free hypergraphs by showing, % %\begin{thm}(Gy\'arf\'as, Gy\H{o}ri, Simonovits \cite{GyGyoSim}) % If $H$ is a $3$-uniform hypergraph on $n$ vertices without linear cycles, then it is $3$-colorable. Moreover, $\alpha(H) \leq \frac{2n}{5}$. %\end{thm} % %We proved, % %\begin{thm} %\label{2coloring} %Let $H$ be a $3$-uniform hypergraph without linear cycles, and no $K_5^3$ as a sub-hypergraph. Then it is $2$-colorable. %\end{thm} % %\begin{corollary} %Let $H$ be a $3$-uniform hypergraph without linear cycles, and no $K_5^3$ as a sub-hypergraph. Then $\alpha(H) \ge \lceil \frac{n}{2} \rceil$ and it is sharp. %\end{corollary} % %Indeed, from Theorem \ref{2coloring}, it trivially follows that $\alpha(H) \ge \lceil \frac{n}{2} \rceil$. The hypergraph $H_n$ on $n$ vertices obtained from the following construction shows that this inequality is sharp. Let $H_3$ be the hypergraph on $3$ vertices $v_1, v_2, v_3$ such that $v_1v_2v_3 \in E(H_3)$ and let $H_4$ be the complete $3$-uniform hypergraph $K_4^3$ on $4$ vertices $v_1, v_2, v_3, v_4$. Now for each $3 \le i \le n-2$ let us define the hypergraph $H_{i+2}$ such that $V(H_{i+2}) := V(H_{i}) \cup \{v_{i+1}, v_{i+2} \}$ and $E(H_{i+2}):= E(H_i) \cup \cup_{j=1}^i \{v_{i+1} v_{i+2} v_j\}$. If $n$ is even, we start this iterative process with the hypergraph $H_4$ and if $n$ is odd, we start with $H_3$. Notice that $\alpha(H_{i+2}) = \alpha(H_i)+1$ for each $i$, which implies that $\alpha(H_n) = \lceil \frac{n}{2} \rceil$. % % %Given a $3$-uniform hypergraph $H$, if $v \in V(H)$ the link of $v$ in $H$ is defined as the graph with vertex set $V(H)$ and edge set $\{(x, y) : (v, x, y) \in E(H)\}$. The \emph{strong degree} $d^+(v)$ for $v \in V$ is the maximum number of independent edges in the link of $v$. The \emph{degree} of $v \in V$ is simply the number of hyperedges of $H$ containing $v$. % %\begin{thm}(Gy\'arf\'as, Gy\H{o}ri, Simonovits \cite{GyGyoSim}) % Suppose that $H$ is a $3$-uniform hypergraph with $d^+(v) \geq 3$ for all % $v \in V$. Then $H$ contains a linear cycle. %\end{thm} % %We showed, % %\begin{thm} %\label{degree_condition} %Let $H$ be a $3$-uniform hypergraph on $n \ge 10$ vertices without linear cycles. Then, there is a vertex whose degree is at most $n-2$. %\end{thm} % %We remark that on $9$ vertices there is a $3$-uniform hypergraph without linear cycles where the degree of every vertex is $8$. This hypergraph $H$ is defined by taking a copy of $K_4^3$ on vertices $\{u_1, u_2, v_1, v_2\}$ and a vertex disjoint copy of $K_5^3$ such that $u_1u_2x, v_1v_2x \in E(H)$ for each $x \in V(K_5^3)$ and there are no other hyperedges in $H$. % %Also notice that Theorem \ref{degree_condition} cannot be improved because there is a $3$-uniform hypergraph $H'$, with $E(H') := \{ xab\mid \{a,b\} \in V(H')\setminus \{x\} \}$, in which every vertex has degree at least $n-2$. % %The paper is organized as follows: In section \ref{theorem2} we prove Theorem \ref{2coloring} using our main lemma - Lemma \ref{skeleton_coloring} (which is proved in section \ref{mainlemma}). In section \ref{degree} we prove Theorem \ref{degree}. Finally in section \ref{concluding_remarks}, we present some concluding remarks and open questions. \section*{Acknowledgements} We thank the anonymous referee for carefully reading our article. The research of the authors is partially supported by the National Research, Development and Innovation Office –NKFIH, grant K116769. \begin{thebibliography}{99} \bibitem{GyGyoSim} A. Gy\'arf\'as, E. Gy\H{o}ri and M. Simonovits. ``On $3 $-uniform hypergraphs without linear cycles.'' Journal of Combinatorics 7.1 (2016): 205--216. \bibitem{Gy_Sar} A. Gy\'arf\'as and G. S\'ark\"ozy ``Monochromatic loose-cycle partitions in hypergraphs.'' The Electronic Journal of Combinatorics 21.2 (2014): 2--36. \bibitem{Posa} L. P\'osa ``On the circuits of finite graphs." Magyar Tud. Akad. Mat. Kutató Int. Közl 8 (1963): 355--361. \end{thebibliography} \end{document}