“Bulletin Board”

 School of Mathematics - March 29, 2011

Mathematical Lectures

Alexandr Kostochka
University of Illinois at Urbana-Champaign
May 14 and 18, 2011

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

Titles of Talks

  • 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.5-o(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 $(r-1)$-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)^{r-2}$ and still be $2$-list-colorable.
    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:00-16: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 $(2k-2)$-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:00-12:00


Place: School of Mathematics, Niavaran Bldg., Niavaran Square, Tehran, Iran
back to top
scroll left or right