***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Gal Kronenberg

Thursday 15th Novermber, 3:00 in Fine Hall 224.

Title: The chromatic index of random multigraphs

For a (multi)graph G=(V,E), we denote by χ'(G) the minimum number of colors
needed to color the edges of G properly. Clearly, Δ≤χ'(G). Vizing proved that
χ'(G)≤ Δ(G)+μ(G), where μ(G) is the maximum edge multiplicity of G. 
Let S⊆V and let ρ(G)=ceil max{ e(S)/ floor{|S|/2} | S⊆V }. By the fact that 
every color class forms a matching, we have that χ'(G)≥ ρ(G). In the 70s,
Goldberg, and independently Seymour, conjectured that for any multigraph G, 
χ'(G)ϵ{Δ, Δ+1, ρ(G)}. We show that their conjecture (in a stronger form) 
is true for random multigraphs. 

Let M(n,m) be the collection of all multigraphs with n vertices and m edges. 
Our result states that, for a given m:=m(n), almost all multigraphs in M(n,m)
satisfy χ'(G)=max{Δ,ρ(G)}. In particular, we show that if n is even and 
m:=m(n), then χ'(M)=Δ(M) for a typical M~M(n,m). Furthermore, for a fixed ε >0,
if n is odd, then a typical M~M(n,m) has χ'(M)=Δ for m≤(1- ε)n^3\log n, and 
for m≥(1+ε)n^3\log n, a typical M~M(n,m) has χ'(M)=ρ(M).

Joint work with Penny Haxell and Michael Krivelevich.


		----------------------------------

Next week: Thanksgiving, no seminar. Week after, TBA

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)