Counting Independent sets up to tree threshold

Counting Independent sets up to tree threshold : We consider the problem of counting a given weighted independent set of a Graph. Our goal is to count weighted independent set I that is proportional l which is activity of graph. Indeed, an algorithm for sampling independent set can help us find a maximum independent set. In this project, we will use an efficient scheme to get the bound of l. The new regime improves maximum degree from 4 to 5 when, for approximate counting of uniformly weighted independent sets of a graph and other implication will also discussed by using the new regime.

Properly colored copies and rainbow copies of large graphs with small maximum degree : Let G be a graph on n vertices with maximum degree. We use the Lovász local lemma to show the following two results about colorings X of the edges of the complete graph K_n. If for each vertex v of K_n the coloring X assigns each color to at most (n-2)/(22.4 D^2) edges emanating from v (D is the max degree of G), then there is a copy of G in K_n which is properly edge-colored by X. If X assigns each color to at most n/(51 D^2) edges of K_n, the there is a copy of G in K_n such that each edge of G receives a different color from X.

Event Topic

Discrete Applied Math Seminar