Combsem: Eli Shamir (HUJI)

Mon, 03/05/202110:30-12:30
Sprinzak Building, Jerusalem, Israel

HUJI Combinatorics Seminar 

When: Monday May 3rd, 2021, at 10:30AM

Where: Sprinzak 28

Live session:

Speaker: Eli Shamir (HUJI)
Title: List Coloring of Latin Graphs


For G(V,E) list coloring each vertex v has a palette  P(V) of allowed colors it can  get. It is harder than standard coloring and often max  I(P(v)I is higher than chi(G).  But it is amenable to stepwise coloring and validity proof by induction on IVI.  

For the next step let

A(c)={v I c  is in P'(v),the current  palette)       ;      K(c)=some maximal independent  set in A(c)

Color K(c)  by c ,delete it from V and c from P’(v). Induction on IVI will prove success if  for v in A(c)\K(c)  the degree and P(v)    .

decrease by the same amount.

Question is :how to to specify K(c) and  INV -the  invariant decease relation.

Consider this process for the family of simple[single] latin graphs [ SLG ] on nXn domain D, in which the edges form cliques on all rows and columns { or on similar double partitions of D to n sets of size n.}

This G is a line graph of a [complete] bipartite graph H with sides C and R of size n.

This G is known to be perfect:: for all induced subgraphs G’  chi(G’) =max clique size of G’.

Dinitz problem  is: does this equality extend to list coloring number[the choice number]?

Galvin solved it for SLG; using stable matching algorithm on sets of lines in H; to define the kernels K(c) in A(c).

Our method connects a pair of  maximal semi-matchings in the sides C and R of H by a mirror map. This pair "incarnate” to the same set K(c) of entries in D; and due to maximality the degrees of  C- and R cliques attached  to any v in A(c) \K(c) decrease by 1 and the same for P'(v). Thus the perfection of G is directly proved [on top of Dinitz ] while in Galvin proof it is complicated due to recourse to digraph, and using outdegree instead of degree for INV relation.

Next -the list coloring and perfection is proved for twins latin  graphs[TLG]: two single SLGs load their edges on the same domain D. Here G is line graph of H which is not bipartite but 4-partite: Lines running top to bottom sides  and left to right sides of a square.

The maps between the semi-matches heavily rely on a balanced indexing of the 2 sides C and R of H  by a pair d,d’ in [p]   ;     e,e’ in [q]       The additive groups of size p and q. This bypasses the adjoint map which arises when rows to columns are mapped using  indexing by [n]. Here n=p.q  but the case of prime n is obtained from n+1 by a subgraph of deficiency 1.