Name
Abstract | ||
|---|---|---|
Let K-n((k)) be the complete k-uniform hypergraph,k >= 3,and let l be an integer such that 1 <= l <= k - 1 and k - l divides n.An l-overlapping Hamilton cycle in K-n((k)) is a spanning subhypergraph C of K-n((k)) with n/(k - l) edges and such that for some cyclic ordering of the vertices each edge of C consists of k consecutive vertices and every pair of adjacent edges in C intersects in precisely l vertices. We show that, for some constant c = c(k,l) and sufficiently large n, for every coloring (partition) of the edges of K-n((k)) which uses arbitrarily many colors but no color appears more than cn(k-l) times,there exists a rainbow l-overlapping Hamilton cycle C,that is every edge of C receives a different color. We also prove that, for some constant c'=c'(k,l) and sufficiently large n, for every coloring of the edges of K-n((k)) in which the maximum degree of the subhypergraph induced by any single color is bounded by c'n(k-l), there exists a properly colored l-overlapping Hamilton cycle C, that is every two adjacent edges receive different colors. For l - 1,both results are (trivially) best possible up to the constants. It is an open question if our results are also optimal for 2 <= l <= k - 1. The proofs rely on a version of the Lovasz Local Lemma and incorporate some ideas from Albert, Frieze, and Reed. |
Year | Venue | Field |
|---|---|---|
2012 | ELECTRONIC JOURNAL OF COMBINATORICS | Integer,Discrete mathematics,Combinatorics,Vertex (geometry),Hamiltonian path,Hypergraph,Degree (graph theory),Lovász local lemma,Partition (number theory),Mathematics,Bounded function |
DocType | Volume | Issue |
Journal | 19.0 | 1.0 |
ISSN | Citations | PageRank |
1077-8926 | 1 | 0.37 |
References | Authors | |
5 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrzej Dudek | 1 | 114 | 23.10 |
| Alan M. Frieze | 2 | 4837 | 787.00 |
| Andrzej Rucinski 0001 | 3 | 197 | 30.44 |