Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ Electronic Journal o...arrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
Electronic Journal of Combinatorics
Article . 2012 . Peer-reviewed
Data sources: Crossref
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
zbMATH Open
Article . 2012
Data sources: zbMATH Open
DBLP
Article
Data sources: DBLP
versions View all 6 versions
addClaim

This Research product is the result of merged Research products in OpenAIRE.

You have already added 0 works in your ORCID record related to the merged Research product.

Rainbow Hamilton Cycles in Uniform Hypergraphs

Rainbow Hamilton cycles in uniform hypergraphs
Authors: Andrzej Dudek; Alan M. Frieze; Andrzej Rucinski 0001;

Rainbow Hamilton Cycles in Uniform Hypergraphs

Abstract

Let $K_n^{(k)}$ be the complete $k$-uniform hypergraph, $k\ge3$, and let $\ell$ be an integer such that $1\le \ell\le k-1$ and $k-\ell$ divides $n$. An $\ell$-overlapping Hamilton cycle in $K_n^{(k)}$ is a spanning subhypergraph $C$ of $K_n^{(k)}$ with $n/(k-\ell)$ 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 $\ell$ vertices.We show that, for some constant $c=c(k,\ell)$ 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-\ell}$ times, there exists a rainbow $\ell$-overlapping Hamilton cycle $C$, that is every edge of $C$ receives a different color. We also prove that, for some constant $c'=c'(k,\ell)$ 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-\ell}$, there exists a properly colored $\ell$-overlapping Hamilton cycle $C$, that is every two adjacent edges receive different colors. For $\ell=1$, both results are (trivially) best possible up to the constants. It is an open question if our results are also optimal for $2\le\ell\le k-1$.The proofs rely on a version of the Lovász Local Lemma and incorporate some ideas from Albert, Frieze, and Reed.

Keywords

Eulerian and Hamiltonian graphs, Extremal problems in graph theory, Coloring of graphs and hypergraphs, FOS: Mathematics, 19999 Mathematical Sciences not elsewhere classified, Vertex degrees, Hypergraphs, \(\ell\)-overlapping Hamilton cycle in \(K_n^{(k)}\)

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    16
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Top 10%
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Top 10%
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
16
Top 10%
Top 10%
Average
gold