
Alexandr Kostochka University of Illinois at Urbana Champaign USA May 14 and 18, 2011 School of Mathematics, IPM


List Colorings of Dense Hypergraphs
ABSTRACT: The {\em list chromatic number}
$\chi_{\ell}(G)$ of a hypergraph $G=(V,E)$ is the minimum integer $s$
such that for every assignment of a list $L_v$ of $s$ colors to
each vertex $v$ of $G$, there is a vertex coloring of $G$
in which the color of each vertex is in its list and there are no
monochromatic edges. Fifteen year ago, Alon
showed that the list chromatic number of every graph with
average degree $d$ is at least $(0.5o(1))\log_2 d$.
In this talk, we discuss two related results by Alon
and the speaker on list coloring of uniform hypergraphs.
The first of them states that for
$r\geq 3$, every $r$uniform hypergraph in which at
least half of the $(r1)$vertex subsets are contained in at least $d$
edges has list chromatic number at least $ \frac{\ln d}{(20r)^3}$.
When $r$ is fixed, this is sharp up to a constant factor.
In particular, $n$vertex $r$uniform hypergraphs may have average degree
about $(n/r)^{r2}$ and still be $2$listcolorable.
The second result concerns
{\em simple} hypergraphs, that is, the hypergraphs in which
any two distinct edges have at most one vertex in common. It is proved that
for every fixed $r$, all $r$uniform hypergraphs with high
average degree have ``high" list chromatic number.
The result implies that for any finite set of points $X$ in the
plane, and for any finite integer $s$, one can assign a list of $s$
distinct colors to each point of the plane so that any coloring of
the plane that colors each point by a color from its list contains a
monochromatic isometric copy of $X$. As mentioned above, this is
joint work with Noga Alon.
Date and Time:
Saturday, May 14, 2011 at 15:0016:00

$K_{s,t}$ Minors in $(s+t)$chromatic Graphs
ABSTRACT: In search of ways to attack Hadwiger's
Conjecture, Woodall and independently Seymour
suggested to prove the weaker
conjecture that
{\em
Every $(s+t)$chromatic graph has a $K_{s,t}$minor.}
If the conjecture were true for all values of $s$ and $t$, it would imply that
for $k\geq 2$
every $(2k2)$chromatic graph has a $K_{k}$minor.
The conjecture is evident for $s=1$. The validity of the conjecture
for $s=2$ and all $t$ was proved
by Woodall, and also
follows from a result by
Chudnovsky, Reed, and Seymour.
Prince and the speaker
proved the conjecture for $s=3$ and $t\geq 6500$.
Then the speaker proved the conjecture for arbitrary $s$ if $t\geq C^{s^2}$.
The aim of the talk is to show a refinement by Prince and the speaker:
{\em Let $s$ and $t$ be positive integers such that
$t>t_1(s):= (100s\log_2 s)^4.$
Then every $(s+t)$chromatic graph has a $K^*_{s,t}$minor, where
$K^*_{s,t}$ is obtained from $K_{s,t}$ by
adding all edges
between the vertices of the partite set of size $s$.}
The result is sharp in the sense that for every $s,t\geq 3$, there are infinitely many
$(s+t)$critical
graphs that do not have $K_{s,t+1}$minors.
Date and Time:
Wednesday, May 18, 2011 at 11:0012:00
Information:
Place: School of Mathematics, Niavaran Bldg., Niavaran Square, Tehran, Iran

 
