



\section{Introduction}\label{sec:intro}
\input{intro-paths.tex}




\section{Complex hypergraphs}\label{sec:complex}
\input{main-thm.tex}
\input{condensation.tex}

\section{Tools}\label{sec:tools}
\input{tools.tex}

\section{Shrinking the hypergraph}\label{sec:shrink}
\input{shrink.tex}

\section{Path-graphs}\label{sec:path-graphs}
\input{conflict-2.tex}
\input{rainbow-trees.tex}

\section{Proof of a key lemma}\label{sec:core}
\input{core-2.tex}

\section{Proof of Theorem~\ref{thm:main}}\label{sec:paths}
\input{main-proof.tex}

\section*{Acknowledgements}
We would like to thank to Julien Bensmail, Ararat Harutyunyan and Tien-Nam Le
for helpful discussions.

The work was done while the first author was a postdoc at Laboratoire d’Informatique du Parall\'elisme,
\'Ecole Normale Sup\'erieure de Lyon,
69364 Lyon Cedex 07, France.





\section{Graph fractions and other tools}
In this section, we introduce several tools used in the rest of the paper. First, we focus on connectivity in hypergraphs and state generalizations of some classical results for graphs.

The following Lemma~\ref{cor:sparse-tree} was essentially proven in~\cite{bib:thomassen-paths}. Our version (which we prove in~\cite{bib:our-trees}) differs in some details.


\begin{lemma}\label{cor:sparse-tree}
For every $\varepsilon>0$ and integer $m$, there exists $L$ such that every $2^n$-edge-connected stub graph $G$ with minimum degree at least $L$, where $n=2+m+ \lceil\log (1/\varepsilon)\rceil$,   
has $2^{m}$ edge-disjoint spanning trees $T_1,\ldots, T_{2^m}$ such that
\[\sum_{i\in [2^m]}\deg_{T_i} v \leq \varepsilon \deg_{G} v\]
 for every $v\in V(G)$.
\end{lemma}

A {\em bridge} in a graph or a hypergraph is an edge such that after removing it, the graph or the hypergraph becomes disconnected.

A hypergraph $H$ is {\em $k$-partition-connected} if for any partition of $V(H)$ into $p$ non-empty parts, the number of hyperedges 
of $H$ containing vertices in more than one part is at least $k(p-1)$. The following easy observation links partition-connectivity to edge-connectivity.

\begin{observation}\label{obs:part-con}
A $3k$-edge-connected hypergraph $H$ with edges of size at most three is $k$-partition-connected. 
\end{observation}

\begin{proof}
Let $\HH$ be a partition of $H$ into $p$ nonempty parts. Since $H$ is $3k$-edge-connected, every part of $\HH$ is connected to other parts by at least $3k$ edges. Each such edge contains vertices in at most three parts of $\HH$, therefore in total there are at least $3kp/3=kp$ edges containing vertices in more than one part of $\HH$.
\end{proof}

A {\em spanning hypertree} of a hypergraph $(V,E)$ is a hypergraph $(V,F)$, where $F\subseteq E$, $|F|=|V|-1$, $\bigcup_{e\in F}e=V$ and there are at most $|X|-1$ hyperedges $e\in F$ such that $e\subseteq X$ for every $X\subseteq V$.
The classical result of Nash-Williams and Tutte about the number of edge-disjoint spanning trees
 was generalized to hypergraphs in~\cite{bib:nwh} as follows.

\begin{theorem}[Nash-Williams for hypergraphs~\cite{bib:nwh}]\label{thm:nwh}
A hypergraph $H$ is $k$-partition-connected if and only if $H$ contains $k$-hyperedge-disjoint spanning hypertrees.

\end{theorem}

Thus, every $1$-partition-connected hypergraph contains a spanning hypertree. By a result of Lov\'asz~\cite{bib:lovasz}, it is possible to shrink a spanning hypertree in such a way that the resulting graph is a spanning tree.


Let $H$ be a hypergraph. We call an ordered partition $(A,B)$ of the vertex set of $H$ into two parts a {\em cut} in $H$. We denote by $E(A,B)$ the set of hyperedges of $H$ incident with vertices in both $A$ and $B$ and call $|E(A,B)|$ the {\em order of the cut} $(A,B)$.
We define the {\em value} of the cut $(A,B)$ as $val(A,B)=\sum_{e\in E(A,B)}|e\cap A|$. Note that this definition is asymmetric, i.e., $val(A,B)$ and $val(B,A)$ are not equal in general. Next, we prove an analogue of Lemma~\ref{lem:cut} for hypergraphs.

\begin{lemma}\label{lem:hycut}
Let $k$ be an integer and $H$ be a hypergraph with edges of size at most three. Then there is a cut $(A,B)$ in $H$ of value at most $3k$ (and thus, of order at most $3k$) such that $H[A]$ is $k$-edge-connected or has only one vertex.
\end{lemma}

\begin{proof}
If $H$ is $k$-edge-connected, we are done. Otherwise, we consider a cut $(A,B)$ with value at most $3k$ such that $A$ is inclusion-wise minimal. (Such a cut exists in $H$, because $val(A,B)\leq 2|E(A,B)|$ for every cut $(A,B)$.) Consider a cut $(A_1,A_2)$ in $H[A]$ and let $r$ be its order. We show that $r>k$. We have
\[ val(A_1,V\setminus A_1) + val(A_2,V\setminus A_2)=val(A,B)+\sum_{e\in E(A_1,A_2)}|e|.\]
Note that $val(A,B)\leq 3k$ and $\sum_{e\in E(A_1,A_2)}|e|\leq 3r$. Moreover, $val(A_1,V\setminus A_1), val(A_2,V\setminus A_2)>3k$ by minimality of $A$.  It follows that $\sum_{e\in E(A_1,A_2)}|e|>3k$ and thus, $r>k$. Since this is true for any cut in $H[A]$, $H[A]$ is $k$-edge-connected.
\end{proof}




Let $G$ be a hypergraph (or a multigraph). We denote the minimum number of hyperedges in a cut separating vertices $u$ and $v$ in $G$ by $\lambda_{G}(u,v)$.

{\em Splitting off} a pair of edges $su$, $sv$ in a multigraph $G$ is replacing these two edges by a new edge $uv$. We define splitting off a pair of hyperedges of size two in a hypergraph in the same way.

\begin{theorem}[Mader splitting off theorem~\cite{bib:mader}]\label{thm:mader}

Let $G=(V,E)$ be a connected multigraph and let $s$ be a vertex such that the degree of $s$ is not three and $s$ is not incident with bridges.
Then there are two edges $e,f$ incident with $s$ such that the multigraph $G_{e,f}$ obtained by splitting off $e$ and $f$ satisfies $\lambda_{G_{e,f}}(u,v)=\lambda_{G}(u,v)$ for any $u,v\in V\setminus \{s\}$.
\end{theorem}

\begin{corollary}\label{cor:mader}
Let $H$ be a connected hypergraph with at least two vertices and hyperedges of size at most three and let $s$ be a vertex that is not contained in any hyperedge of size three and not incident with bridges. Then there are two hyperedges $e,f$ of size two incident with $s$ such that the hypergraph $H_{e,f}$ obtained from $H$ by splitting off $e$ and $f$ satisfies $\lambda_{H_{e,f}}(u,v)=\lambda_{H}(u,v)$ for any $u,v\in V\setminus \{s\}$.
\end{corollary}

\begin{proof}
Let $G$ be a hypergraph with hyperedges of size at most three.
Let $\tau$ be the operation creating a multigraph $\tau(G)$ from $G$ by replacing each hyperedge $h$ of size $3$ containing vertices $u_1,u_2$ and $u_3$ by a vertex $h$ adjacent to $u_1$, $u_2$ and $u_3$ (with possible multiplicities if $u_i=u_j$ for some $i\not= j$).
Observe that $\lambda_{G}(u,v)=\lambda_{\tau(G)}(u,v)$ for every $u,v\in V(G)$. In particular, if $s$ is not incident with a bridge in $G$, it is not incident with a bridge in $\tau(G)$.

Therefore, we can apply Theorem~\ref{thm:mader} to $\tau(H)$ and the vertex $s$. Let $e,f$ be a pair of edges incident with $s$ in $\tau(H)$ as in Theorem~\ref{thm:mader} and let $\tau(H)_{e,f}$ be the multigraph obtained from $\tau(H)$ by splitting off $e$ and $f$. Then, $\lambda_{\tau(H)_{e,f}} (u,v)=\lambda_{\tau(H)}(u,v)$ for every $u,v\in V(\tau(H))\setminus \{s\}$.

Note that since $s$ is not contained in any hyperedge of size three in $H$, $e$ and $f$ are hyperedges of size two in $H$. Moreover, $\tau(H)_{e,f}$ is isomorphic to $\tau(H_{e,f})$. It follows that $\lambda_{H_{e,f}}(u,v)=\lambda_{H}(u,v)$ for any $u,v\in V(H)\setminus \{s\}$.  
\end{proof}


Let $G$ be a complex graph without stubs. We say that a spanning subgraph $H$ of $G$ is an {\em $\varepsilon$-fraction of $G$} if it satisfies $|\deg_H v- \varepsilon\deg_G v|\le 2$ for every vertex $v$ of $G$. 
The following lemma shows that there exists an $\varepsilon$-fraction of $G$ for any  $\varepsilon=1/2^c$, $c\in \NN$.

\begin{lemma} \label{lem:fraction}
Let $m_1, \ldots, m_k$ be such that $\sum_{i\in [k]} 2^{-m_i}\leq 1$ and let $G$ be a complex graph without stubs. Then, there exist edge-disjoint subgraphs $G_1,\ldots,G_k$ of $G$ such that $G_i$ is a $2^{-m_i}$-fraction of $G$ for every $i\in [k]$.
\end{lemma}

\begin{proof}

Let $m=\max_{i\in [k]} m_i$ 
and let $H$ be the underlying multigraph of $G$. 

Let $\bar{H}$ be the multigraph obtained from $H$ by adding an auxiliary vertex $s$ adjacent to all vertices of odd degree in $H$. Since the number of such vertices is even, all vertices of $\bar{H}$ have even degree. 
Consider an Eulerian tour in each connected component of $\bar{H}$ and color its edges by two colors, $0$ and $1$, in an alternating way, starting from $s$ if the connected component contains $s$.

Let $H_0$ be the subgraph of $H$ of color $0$ and $H_1$ the subgraph of $H$ of color $1$. We apply the procedure described above for $H_0$ and $H_1$ to obtain graphs $H_{00}$, $H_{01}$, $H_{10}$ and $H_{11}$ and repeat it recursively until we obtain a collection $\{H_Q\}_{Q\in \{0,1\}^m}$ of edge-disjoint spanning subgraphs of $H$. 

 Let $v$ be a vertex of $H$ and let $d$ be its degree. Observe that $\deg_{H_0} v,\deg_{H_1} v \in [d/2-1,d/2+1]$ and this is true for every iteration of the procedure. Thus, 
  \[\deg_{H_Q} v\leq \underbrace{(\ldots (}_{i \times} d/\underbrace{2 +1)/2 +1)/2 \ldots )/2+1}_{i \times}\leq d/2^i+\sum_{j=0}^{i-1} 1/2^{j}\leq d/2^i +2\]
for every $H_{Q}$ with $Q\in \{0,1\}^{i}$.
 Analogously, $\deg_{H_Q} v \geq d/2^i-2$ for every $H_{Q}$ with $Q\in \{0,1\}^{i}$. 


We choose $Q_i\in \{0,1\}^{m_i}$ for every $i\in [k]$ so that the graphs $H_{Q_i}$ are pairwise edge-disjoint. We let $G_i$ be the subgraph of $G$ with underlying multigraph $H_{Q_i}$ for every $i\in [k]$.  
Consequently, all $G_i$'s are edge-disjoint $2^{-m_i}$-fractions of $G$.  

\end{proof}

We conclude the section by stating the Asymmetric Lov\'asz Local Lemma, which we extensively use in the following sections.

\begin{lemma}[Lov\'asz Local Lemma (asymmetric version)~\cite{bib:lll}]\label{LLL}
Let ${\mathcal {A}}=\{A_{1},\ldots, A_{n}\}$ be a finite set of events in a probability space $\Omega$. For each $A\in {\mathcal {A}}$, we let $\Gamma (A)$ denote a subset of ${\mathcal {A}}$ such that $A$ is independent from the collection of events ${\mathcal {A}}\setminus (\{A\}\cup \Gamma (A))$. If there exists an assignment of reals $x:{\mathcal {A}}\to (0,1)$ to the events such that  for every $A\in {\mathcal {A}}$:
\[\Pr(A)\leq x(A)\prod_{B\in \Gamma (A)}(1-x(B)),\]
then the probability of avoiding all events in ${\mathcal {A}}$ is positive, in particular

    \[\Pr \left(\bigwedge_{A\in {\mathcal {A}}}{\overline {A}}\right)\geq \prod \nolimits _{A\in {\mathcal {A}}}(1-x(A)).\] 
\end{lemma}
