 \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}