Partitioning the edge set of a hypergraph into almost regular cycles

Publication date 23 November 2018

Abstract: A cycle of length

t

in a hypergraph is an alternating sequence

v_{1}, e_{1}, v_{2} d o t s, v_{t}, e_{t}

of distinct vertices

v_{i}

and distinct edges

e_{i}

so that

v_{i}, v_{i + 1} s u b s e t e q e_{i}

(with

v_{t + 1} := v_{1}

). Let

l a m b d a K_{n}^{h}

be the

l a m b d a

-fold

n

-vertex complete

h

-graph. Let

m a t h c a l G = (V, E)

be a hypergraph all of whose edges are of size at least

h

, and

2 l e q c_{1} l e q d o t s l e q c_{k} l e q | V |

. In order to partition the edge set of

m a t h c a l G

into cycles of specified lengths

c_{1}, d o t s, c_{k}

, an obvious necessary condition is that

s u m_{i = 1}^{k} c_{i} = | E |

. We show that this condition is sufficient in the following cases: (i)

h g e q m a x c_{k}, l c e i l n / 2 c e i l + 1

; (ii)

m a t h c a l G = l a m b d a K_{n}^{h}

,

h g e q l c e i l n / 2 c e i l + 2

; (iii)

m a t h c a l G = K_{n}^{h}

,

c_{1} = d o t s = c_{k} := c

,

c | n (n - 1), n g e q 85

. In (ii), we guarantee that each cycle is almost regular. In (iii), we also solve the case where a "small" subset

L

of edges of

K_{n}^{h}

is removed.

Recommendations

Cited in

(5)

This page was built for publication: Partitioning the edge set of a hypergraph into almost regular cycles