Coloring Nonuniform Hypergraphs: A New Algorithmic Approach to the General Lovasz Local Lemma

Coloring Nonuniform Hypergraphs: A New Algorithmic Approach to the General Lovasz Local Lemma : The Lovasz Local Lemma is a useful tool for making probabilistic arguments for the existence of certain structures, such as proper graph colorings, however it generally provides no help when it comes to actually developing such a structure. The first known method for converting the results of LLL into an efficient algorithm was developed by Beck in 1991, specifically applied to the problem of 2-coloring a uniform hypergraph in polynomial time. I will be discussing a 2000 paper by Czumaj and Scheideler that generalizes these results to nonuniform hypergraphs. I will give a detailed description of the algorithm developed by Czumaj and Scheideler, including how it differs from previous efforts, outlines of proofs of its validity, and extensions of it to more difficult problems. I will end by describing work that has taken place more recently.

On Counting Weighted Graph Homomorphisms: My talk is based on the work by David Galvin and Prasad Tetali. We've discussed about Kahn's theorem on the number of independent sets in an N-vertex d-regular bipartite graph. This actually is a special case of homomorphisms, Hom(G,H_ind), where H_ind is a two vertex graph with one edge between the two vertices and one loop. We are talking about more general results on the numbers of homomorphisms from G to general H. Similar bound will be proved using entropy methods and asymptotics of the logarithm of |Hom(G,H)| in terms of a parameter of H will be given.

Event Topic

Discrete Applied Math Seminar