Randomly coloring simple hypergraphs

Alan Frieze, Páll Melsted

Rannsóknarafurð: Framlag til fræðitímaritsGreinritrýni

4 Tilvitnanir (Scopus)

Útdráttur

We study the problem of constructing a (near) uniform random proper q-coloring of a simple k-uniform hypergraph with n vertices and maximum degree Δ. (Proper in that no edge is mono-colored and simple in that two edges have maximum intersection of size one.) We show that if for some α<1 we have Δ≥ nα and q≥Δ ( 1+α)/kα then Glauber dynamics will become close to uniform in O(nlogn) time from a random (improper) start. Note that for k>1+α-1 we can take q=o(Δ).

Upprunalegt tungumálEnska
Síður (frá-til)848-853
Síðufjöldi6
FræðitímaritInformation Processing Letters
Bindi111
Númer tölublaðs17
DOI
ÚtgáfustaðaÚtgefið - 15 sep. 2011

Athugasemd

Funding Information:
E-mail addresses: alan@random.math.cmu.edu (A. Frieze), pmelsted@gmail.com (P. Melsted). 1 Supported in part by NSF grant CCF-0502793.

Fingerprint

Sökktu þér í rannsóknarefni „Randomly coloring simple hypergraphs“. Saman myndar þetta einstakt fingrafar.

Vitna í þetta