Search

A famous result by Rödl, Ruciński, and Szemerédi guarantees a (tight) Hamilton cycle in k -uniform hypergraphs H on n vertices with minimum (k − 1) -degree δ k − 1 (H) ⩾ (1 / 2 + o (1)) n , thereby extending Dirac's result from graphs to hypergraphs. For graphs, much more is known; each graph on n vertices with δ (G) ⩾ (1 / 2 + o (1)) n contains (1 − o (1)) r edge-disjoint Hamilton cycles where r is the largest integer such that G contains a spanning 2 r -regular subgraph, which is clearly asymptotically optimal. This was proved by Ferber, Krivelevich, and Sudakov answering a question raised by Kühn, Lapinskas, and Osthus. We extend this result to hypergraphs; every k -uniform hypergraph H on n vertices with δ k − 1 (H) ⩾ (1 / 2 + o (1)) n contains (1 − o (1)) r edge-disjoint (tight) Hamilton cycles where r is the largest integer such that H contains a spanning subgraph with each vertex belonging to kr edges. In particular, this yields an asymptotic solution to a question of Glock, Kühn, and Osthus. In fact, our main result applies to approximately vertex-regular k -uniform hypergraphs with a weak quasirandom property and provides approximate decompositions into cycle factors without too short cycles. [ABSTRACT FROM AUTHOR]

We prove that for any integer k≥2$$ k\ge 2 $$ and ε>0$$ \varepsilon >0 $$, there is an integer ℓ0≥1$$ {\ell}_0\ge 1 $$ such that any k‐uniform hypergraph on n vertices with minimum codegree at least (1/2+ε)n$$ \left(1/2+\varepsilon \right)n $$ has a fractional decomposition into (tight) cycles of length ℓ$$ \ell $$ (ℓ$$ \ell $$‐cycles for short) whenever ℓ≥ℓ0$$ \ell \ge {\ell}_0 $$ and n is large in terms of ℓ$$ \ell $$. This is essentially tight. This immediately yields also approximate integral decompositions for these hypergraphs into ℓ$$ \ell $$‐cycles. Moreover, for graphs this even guarantees integral decompositions into ℓ$$ \ell $$‐cycles and solves a problem posed by Glock, Kühn, and Osthus. For our proof, we introduce a new method for finding a set of ℓ$$ \ell $$‐cycles such that every edge is contained in roughly the same number of ℓ$$ \ell $$‐cycles from this set by exploiting that certain Markov chains are rapidly mixing. [ABSTRACT FROM AUTHOR]

We prove that the set of long cycles has the edge-Erdős-Pósa property: for every fixed integer ℓ ≥ 3 and every k ∈ ℕ, every graph G either contains k edge-disjoint cycles of length at least ℓ (long cycles) or an edge set X of size O(k2 logk+kℓ) such that G—X does not contain any long cycle. This answers a question of Birmelé, Bondy, and Reed (Combinatorica 27 (2007), 135-145). [ABSTRACT FROM AUTHOR]

We prove that for every graph, any vertex subset S, and given integers [ABSTRACT FROM AUTHOR]

We show the following for every sufficiently connected graph G, any vertex subset S of G, and given integer k: there are k disjoint odd cycles in G each containing a vertex of S or there is set X of at most [ABSTRACT FROM AUTHOR]

The boxicity of a graph G is the least integer d such that G has an intersection model of axis-aligned d-dimensional boxes. Boxicity, the problem of deciding whether a given graph G has boxicity at most d, is NP-complete for every fixed $$d \ge 2$$ . We show that Boxicity is fixed-parameter tractable when parameterized by the cluster vertex deletion number of the input graph. This generalizes the result of Adiga et al. (2010), that Boxicity is fixed-parameter tractable in the vertex cover number. Moreover, we show that Boxicity admits an additive 1-approximation when parameterized by the pathwidth of the input graph. Finally, we provide evidence in favor of a conjecture of Adiga et al. (2010) that Boxicity remains NP-complete even on graphs of constant treewidth. [ABSTRACT FROM AUTHOR]

Let [ABSTRACT FROM AUTHOR]