## Seminars and Colloquia by Series

### Linear Colorings of Subcubic Graphs

Series
ACO Student Seminar
Time
Friday, September 14, 2012 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Chun-Hung LiuGeorgia Tech, Math
A linear coloring of a graph is a proper coloring of the vertices of the graph so that each pair of color classes induce a union of disjoint paths. In this talk, I will prove that for every connected graph with maximum degree at most three and every assignment of lists of size four to the vertices of the graph, there exists a linear coloring such that the color of each vertex belongs to the list assigned to that vertex and the neighbors of every degree-two vertex receive different colors, unless the graph is $C_5$ or $K_{3,3}$. This confirms a conjecture raised by Esperet, Montassier, and Raspaud. Our proof is constructive and yields a linear-time algorithm to find such a coloring. This is joint work with Gexin Yu.

### Higher Order Cheeger Inequalities

Series
ACO Student Seminar
Time
Friday, September 7, 2012 - 14:00 for 1 hour (actually 50 minutes)
Location
ISyE Executive Classroom
Speaker
Anand LouisGeorgia Tech, CoC
Cheeger's fundamental inequality states that any edge-weighted graph has a vertex subset $S$ such that its expansion (a.k.a. conductance of $S$ or the sparsity of the cut $(S,\bar{S})$)is bounded as follows: \phi(S) = w(S,S') /w(S) \leq \sqrt{2 \lambda_2},where $w$ is the total edge weight of a subset or a cut and $\lambda_2$ is the second smallest eigenvalue of thenormalized Laplacian of the graph.We study natural generalizations of the sparsest cut in a graph: (i) a partition ofthe vertex set into $k$ parts that minimizes the sparsity of the partition (defined as the ratio of theweight of edges between parts to the total weight of edges incident to the smallest $k-1$ parts); (ii) a collection of $k$ disjoint subsets $S_1, \ldots, S_k$ that minimize $\max_{i \in [k]} \phi(S_i)$; (iii) a subset of size $O(1/k)$ of the graph with minimum expansion. Our main results are extensions of Cheeger's classical inequality to these problems via higher eigenvalues of the graph Laplacian.In particular, for the sparsest $k$-partition, we prove that the sparsity is at most $8\sqrt{\lambda_k} \log k$where $\lambda_k$ is the $k^{th}$ smallest eigenvalue of the normalized Laplacian matrix.For the $k$ sparse cuts problem we prove that there exist$ck$ disjoint subsets $S_1, \ldots, S_{(1 - \eps)k}$, such that \max_i \phi(S_i) \leq C \sqrt{\lambda_{k} \log k}where $C>0$ are suitable absolute constants; this leads to a similar bound for the small-set expansion problem, namely for any $k$, there is a subset $S$ whoseweight is at most a $\bigO(1/k)$ fraction of the total weight and $\phi(S) \le C \sqrt{\lambda_k \log k}$. The latter two results are the best possible in terms of the eigenvalues up to constant factors. Our results are derived via simple and efficient algorithms, and can themselves be viewed as generalizations of Cheeger's method.Based on joint work with Prasad Raghavendra, Prasad Tetali and Santosh Vempala.

### 5-List-Coloring Graphs on Surfaces

Series
ACO Student Seminar
Time
Friday, April 27, 2012 - 13:00 for 1 hour (actually 50 minutes)
Location
Executive classroom, ISyE Main Building
Speaker
Luke PostleSchool of Math., Georgia Tech
Thomassen proved that there are only finitely many 6-critical graphs embeddable on a fixed surface. He also showed that planar graphs are 5-list-colorable. We develop new techniques to prove a general theorem for 5-list-coloring graphs embedded on a fixed surface. Namely, for every surface S and every integer C > 0, there exists D such that the following holds: Let G be a graph embedded in a surface S with edge-width at least D and a list assignment L such that, for every vertex v in G, L(v) has size at least five. If F is a collection of any number of facial cycles of length at most C such that every two cycles in F are distance at least D apart and every cycle in F has a locally planar neighborhood up to distance D/2, then any proper L-coloring of F extends to an L-coloring of G. This theorem implies the following results. In what follows, let S be a fixed surface, G be a graph embedded in S (except in 4, where G is drawn in S) and L a list assignment such that, for every vertex v of G, L(v) has size at least five. 1. If G has large edge-width, then G is 5-list-colorable. (Devos, Kawarabayashi and Mohar) 2. There exists only finitely many 6-list-critical graphs embeddable in S. (Conjectured by Thomassen, Proof announced by Kawarabayashi and Mohar) As a corollary, there exists a linear-time algorithm for deciding 5-list-colorability of graphs embeddable on S. Furthermore, we exhibit an explicit bound on the size of such graphs. 3. There exists D(S) such that the following holds: If X is a subset of the vertices of G that are pairwise distance at least D(S) apart, then any L-coloring of X extends to an L-coloring G. For planar graphs, this was conjectured by Albertson and recently proved by Dvorak, Lidicky, Mohar, and Postle. 4. There exists D(S) such that the following holds: If G is a graph drawn in S with face-width at least D(S) such that any pair of crossings is distance at least D apart, then G is L-colorable. For planar graphs, this was recently proved by Dvorak, Lidicky and Mohar. Joint work with Robin Thomas.

### Some properties of convex hulls of mixed integer points contained in general convex sets.

Series
ACO Student Seminar
Time
Wednesday, April 25, 2012 - 12:00 for 1 hour (actually 50 minutes)
Location
Executive classroom, ISyE Main Building
Speaker
Diego MoránISyE, Georgia Tech
A mixed integer point is a vector in $\mathbb{R}^n$ whose first $n_1$ coordinates are integer. We present necessary and sufficient conditions for the convex hull of mixed integer points contained in a general convex set to be closed. This leads to useful results for special classes of convex sets such as pointed cones and strictly convex sets. Furthermore, by using these results, we show that there exists a polynomial time algorithm to check the closedness of the convex hull of the mixed integer points contained in the feasible region of a second order conic programming problem, for the special case this region is defined by just one Lorentz cone and one rational matrix. This is joint work with Santanu Dey.

### Queues, GUEs and Tubes

Series
ACO Student Seminar
Time
Friday, April 6, 2012 - 13:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Christian HoudréGeorgia Tech, School of Mathematics
Consider a series of n single-server queues each with unlimited waiting space and FIFO discipline. At first the system is empty, then m customers are placed in the first queue. The service times of all the customers at all the queues are iid. We are interested in the exit time of the last customer from the last server and that's when queues meet random matrices and GUEs. If the number of customers is a small fractional power of the number of servers, and as such customers stay within a tube, that's when queues encounter Tracy and Widom. This talk will be self contained and accessible to graduate students.

### Approximating CSPs with Global Cardinality Constraints Using SDP Hierarchies

Series
ACO Student Seminar
Time
Friday, March 30, 2012 - 13:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Ning TanSchool of Math, Georgia Tech
In a celebrated result, Raghavendra [Rag08] showed that, assuming Unique Game Conjecture, every Max-CSP problem has a sharp approximation threshold that matches the integrality gap of a natural SDP relaxation. Raghavendra and Steurer [RS09] also gave a simple and unified framework for optimally approximating all the Max-CSPs.In this work, we consider the problem of approximating CSPs with global cardinality constraints. For example, Max-Cut is a boolean CSP where the input is a graph $G = (V,E)$ and the goal is to find a cut $S \cup \bar S = V$ that maximizes the number of crossing edges, $|E(S,\bar S)|$. The Max-Bisection problem is a variant of Max-Cut with an additional global constraint that each side of the cut has exactly half the vertices, i.e., $|S| = |V|/2$. Several other natural optimization problems like Small Set Expansion, Min Bisection and approximating Graph Expansion can be formulated as CSPs with global constraints.In this talk, I will introduce a general approach towards approximating CSPs with global constraints using SDP hierarchies. To demonstrate the approach, I will present an improved algorithm for Max-Bisection problem that achieves the following:- Given an instance of Max-Bisection with value $1-\epsilon$, the algorithm finds a bisection with value at least $1-O(\sqrt{\epsilon})$ with running time $O(n^{poly(1/\eps)})$. This approximation is near-optimal (up to constant factors in $O()$) under the Unique Games Conjecture.- Using computer-assisted proof, we show that the same algorithm also achieves a 0.85-approximation for Max-Bisection, improving on the previous bound of 0.70 (note that it is UGC-hard to approximate better than 0.878 factor). As an attempt to prove matching hardness result, we show a generic conversion from SDP integrality gap to dictatorship test for any CSP with global cardinality constraints. The talk is based on joint work with Prasad Raghavendra.

### LP-based Covering Games with Low Price of Anarchy

Series
ACO Student Seminar
Time
Friday, March 16, 2012 - 13:00 for 1 hour (actually 50 minutes)
Location
Executive classroom, ISyE Main Building
Speaker
László VeghCoC, Georgia Tech
I present a new class of vertex cover and set cover games, with the price of anarchy bounds matching the best known constant factor approximation guarantees for the centralized optimization problems for linear and also for submodular costs. In particular, the price of anarchy is 2 for vertex cover. The basic intuition is that the members of the vertex cover form a Mafia that has to "protect" the graph, and may ask ransoms from their neighbors in exchange for the protection. These ransoms turn out to capture a good dual solution to the linear programming relaxation. For linear costs we also exhibit linear time best response dynamics that converge that mimic the classical greedy approximation algorithm of Bar-Yehuda and Even. This is a joint work with Georgios Piliouras and Tomas Valla.

### Neighborly measures for sampling independent sets, and a perturbative approach to the question of uniqueness

Series
ACO Student Seminar
Time
Friday, March 9, 2012 - 13:00 for 1 hour (actually 50 minutes)
Location
Executive classroom, ISyE Main Building
Speaker
David GoldbergISyE
Recently, there has been great interest in understanding the fundamental limits of our ability to sample from the independent sets (i.s.) of a graph. One approach involves the study of the so-called hardcore model, in which each i.s. is selected with probability proportional to some fixed activity $\lambda$ raised to the cardinality of the given i.s. It is well-known that for any fixed degree $\Delta$, there exists a critical activity $\lambda_{\Delta}$ s.t. for all activities below $\lambda_{\Delta}$, the sampled i.s. enjoys a long-range independence (a.k.a. uniqueness) property when implemented on graphs with maximum degree $\Delta$, while for all activities above $\lambda_{\Delta}$, the sampled i.s. exhibits long-range dependencies. Such phase transitions are known to have deep connections to the inherent computational complexity of the underlying combinatorial problems. In this talk, we study a family of measures which generalizes the hardcore model by taking more structural information into account, beyond just the number of nodes belonging to the i.s., with the hope of further probing the fundamental limits of what we can learn about the i.s. of a graph using only local information. In our model, the probability assigned to a given i.s. depends not only on its cardinality, but also on how many excluded nodes are adjacent to exactly $k$ nodes belonging to the i.s., for each $k$, resulting in a parameter for each $k$. We generalize the notion of critical activity to these neighborly measures", and give necessary and sufficient conditions for long-range independence when certain parameters satisfy a log-convexity(concavity) requirement. To better understand the phase transitions in this richer model, we view the classical critical activity as a particular point in the parameter space, and ask which directions can one move and still maintain long-range independence. We show that the set of all such directions of uniqueness” has a simple polyhedral description, which we use to study how moving along these directions changes the probabilities associated with the sampled i.s. We conclude by discussing implications for choosing how to sample when trying to optimize a linear function of the underlying probabilities.

### Spatial mixing in spin systems

Series
ACO Student Seminar
Time
Friday, March 2, 2012 - 13:00 for 1 hour (actually 50 minutes)
Location
TBA
Speaker
Linji YangCoC, Georgia Tech
In this seminar, I will talk about a few recent developments in the random colorings, random weighted independent sets and other 2-spin models on different classes of graphs such as the square lattices and the triangular free graphs. I will focus on the so-called spatial mixing property of these models and discuss about the consequences (e.g., fast mixing of the Markov chains) of the spatial mixing property as well as the techniques of proving it.

### A Discrepancy based Approach to Integer Programming

Series
ACO Student Seminar
Time
Friday, February 24, 2012 - 13:00 for 1 hour (actually 50 minutes)
Location
Klaus 1116W
Speaker
Karthekeyan ChandrasekaranCoC, Georgia Tech
I will show a new approach based on the discrepancy of the constraint matrix to verify integer feasibility of polytopes. I will then use this method to show a threshold phenomenon for integer feasibility of random polytopes. The random polytope model that we consider is P(n,m,x0,R) - these are polytopes in n-dimensional space specified by m "random" tangential hyperplanes to a ball of radius R centered around the point x0. We show that there exist constants c_1 < c_2 such that with high probability, the random polytope P(n,m,x0=(0.5,...,0.5),R) is integer infeasible if R is less than c_1sqrt(log(2m/n)) and the random polytope P(n,m,x0,R) is integer feasible for every center x0 if the radius R is at least c_2sqrt(log(2m/n)). Thus, a transition from infeasibility to feasibility happens within a constant factor increase in the radius. Moreover, if the polytope contains a ball of radius Omega(log (2m/n)), then we can find an integer solution with high probability (over the input) in randomized polynomial time. This is joint work with Santosh Vempala.