✦ LIBER ✦

Choosability in Random Hypergraphs

✍ Scribed by Michael Krivelevich; Van H. Vu

Publisher: Elsevier Science
Year: 2001
Tongue: English
Weight: 155 KB
Volume: 83
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.2001.2053

No coin nor oath required. For personal study only.

✦ Synopsis

The choice number of a hypergraph H=(V, E) is the least integer s for which, for every family of color lists S=[S(v): v # V], satisfying |S(v)|=s for every v # V, there exists a choice function f so that f (v) # S(v) for every v # V, and no edge of H is monochromatic under f. In this paper we consider the asymptotic behavior of the choice number of a random k-uniform hypergraph H(k, n, p). Our main result states that for every k 2 and for all values of the edge probability p= p(n) down to p=O(n &k+1 ) the ratio between the choice number and the chromatic number of H(k, n, p) does not exceed k 1Â(k&1) asymptotically. Moreover, for large values of p, namely, when p n &(k&1) 2 Â(2k)+= for an arbitrary positive constant =, the choice number and the chromatic number of H(k, n, p) have almost surely the same asymptotic value.

📜 SIMILAR VOLUMES

Perfect fractional matchings in random h

Perfect fractional matchings in random hypergraphs

✍ Michael Krivelevich 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 890 KB

Given an r-uniform hypergraph H = (V, E ) on ( V ( = n vertices, a real-valued function f(e) 5 1 for all u E V and C e E E f(e) = n/r. Considering a random r-uniform hypergraph process of n vertices, we show that with probability tending to 1 as n + m , at the very moment to when the last isolated

The chromatic numbers of random hypergra

The chromatic numbers of random hypergraphs

✍ Michael Krivelevich; Benny Sudakov 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 261 KB 👁 1 views

For a pair of integers 1 F ␥r, the ␥-chromatic number of an r-uniform Ž . hypergraph H s V, E is the minimal k, for which there exists a partition of V into subsets < < T, . . . , T such that e l T F ␥ for every e g E. In this paper we determine the asymptotic 1 k i Ž . behavior of the ␥-chromatic n

Hypergraphs, Quasi-randomness, and Condi

Hypergraphs, Quasi-randomness, and Conditions for Regularity

✍ Yoshiharu Kohayakawa; Vojtěch Rödl; Jozef Skokan 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 286 KB

Haviland and Thomason and Chung and Graham were the first to investigate systematically some properties of quasi-random hypergraphs. In particular, in a series of articles, Chung and Graham considered several quite disparate properties of random-like hypergraphs of density 1/2 and proved that they a

Choosability, Edge Choosability, and Tot

Choosability, Edge Choosability, and Total Choosability of Outerplane Graphs

✍ Wang Weifan; Ko-Wei Lih 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 101 KB

Let χ l (G), χ l (G), χ l (G), and (G) denote, respectively, the list chromatic number, the list chromatic index, the list total chromatic number, and the maximum degree of a non-trivial connected outerplane graph G. We prove the following results. ( 1 and only if G is an odd cycle. This proves the

A central limit theorem with application

A central limit theorem with applications to random hypergraphs

✍ Peter de Jong 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 691 KB

Define for each subset I C (1,. . . , n} the c+-algebra 9, = m{X, : i E I} with X , , . . . , X , independent random variables. In this paper we consider 9,measurable random variables W, subject to the centering condition E(W, I 9,) = 0 a s .

Circular choosability

✍ Frédéric Havet; Ross J. Kang; Tobias Müller; Jean-Sébastien Sereni 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 313 KB

## Abstract We study circular choosability, a notion recently introduced by Mohar and Zhu. First, we provide a negative answer to a question of Zhu about circular cliques. We next prove that cch(__G__)=__O__(ch(__G__)+ln|__V__(__G__)|) for every graph __G__. We investigate a generalization of circu