- You are here:
- GT Home
- Home
- News & Events

Series: Combinatorics Seminar

Weighted Bipartite Edge Coloring problem is a generalization of two classical optimization problems: Bipartite Edge Coloring and Bin Packing. Given an edge-weighted bipartite multi-graph G, the goal is to color all edges with minimum colors such that the sum of the edges incident to any vertex of any color is at most one. Chung and Ross conjectured that given an instance of the weighted bipartite edge coloring problem, there is a proper weighted coloring using at most 2n-1 colors where n denotes the maximum over all the vertices of the number of unit-sized bins needed to pack the weights of edges incident at the vertex. In this talk I will present an algorithm that gives a proper weighted coloring using $20n/9$ colors and improved results for some special cases. I will also present an alternative proof of Konig's edge coloring theorem using skew-supermodular functions. The talk will have all three components of ACO: Approximation Algorithms, Graph Theory and Supermodular Optimization.

Series: Combinatorics Seminar

The famous Doignon-Bell-Scarf theorem is a Helly-type result about the existence of integer solutions on systems linear inequalities. The purpose
of this paper is to present the following ``weighted'' generalization: Given an integer k, we prove that there exists a constant c(k,n),
depending only on the dimension n and k, such that if a polyhedron {x : Ax <= b} contains exactly k integer solutions, then there exists a subset
of the rows of cardinality no more than c(k,n), defining a polyhedron that contains exactly the same k integer solutions. We work on both
upper and lower bounds for this constant.
This is joint work with Quentin Louveaux, Iskander Aliev and Robert Bassett.

Series: Combinatorics Seminar

Let G be an abelian group. A subset A of G is a Sidon set if A has the property that no sum of two elements of A is equal to another sum of two elements of A. These sets have a rich history in combinatorial number theory and frequently appear in the problem papers of Erdos. In this talk we will discuss some results in which Sidon sets were used to solve problems in extremal graph theory. This is joint work with Mike Tait and Jacques Verstraete.

Series: Combinatorics Seminar

(This seminar has been rescheduled for April 17 (Thursday) 12-1pm. Generalized triangle T_r is an r-graph with edges {1,2,…,r}, {1,2,…,r-1, r+1} and {r,r+1, r+2, …,2r-2}. The family \Sigma_r consists of all r-graphs with three edges D_1, D_2, D_3 such that |D_1\cap D_2|=r-1 and D_1\triangle D_2\subset D_3. In 1989 it was conjectured by Frankl and Furedi that ex(n,T_r) = ex(n,\Sigma_r) for large enough n, where ex(n,F) is the Tur\'{a}n function. The conjecture was proven to be true for r=3, 4 by Frankl, Furedi and Pikhurko respectively. We settle the conjecture for r=5,6 and show that extremal graphs are blow-ups of the unique (11, 5, 4) and (12, 6, 5) Steiner systems. The proof is based on a technique for deriving exact results for the Tur\'{a}n function from “local stability" results, which has other applications. This is joint work with Sergey Norin.

Series: Combinatorics Seminar

The celebrated Green-Tao theorem states that there are arbitrarily long arithmetic progressions in the primes. In this talk, I will explain the ideas of the proof and discuss our recent simplifications. One of the main ingredients in the proof is a relative Szemerédi theorem, which says that every relatively dense subset of a pseudorandom set of integers contains long arithmetic progressions. Our main advance is both a simplification and a strengthening of the relative Szemerédi theorem, showing that a much weaker pseudorandomness condition suffices. I will explain the transference principle strategy used in the proof. Also see our recent exposition of the Green-Tao theorem: http://arxiv.org/abs/1403.2957 Based on joint work with David Conlon and Jacob Fox.

Series: Combinatorics Seminar

We will explain the concept of aproximate well-supported Nash equilibrium
and show that one must consider equilibria with large supports to achieve
good approximation ratio. Our arguments use tools from probabilistic,
extremal and additive combinatorics.
Joint work with Y. Anbalagan, R. Savani and A. Vetta.

Series: Combinatorics Seminar

We study an old problem of Linial and Wilf to find the graphs with n vertices and m edges which maximize the number of proper q-colorings of their vertices. In a breakthrough paper, Loh, Pikhurko and Sudakov asymptotically reduced the problem to an optimization problem. We prove the following structural result which tells us how the optimal solutionlooks like: for any instance, each solution of the optimization problem corresponds to either a complete multipartite graph or a graph obtained from a complete multipartite graph by removing certain edges. We then apply this result on optimal graphs to general instances, including a conjecture of Lazebnik from 1989 which asserts that for any q>=s>= 2, the Turan graph T_s(n) has the maximum number of q-colorings among all graphs with the same number of vertices and edges. We disprove this conjecture by providing infinity many counterexamples in the interval s+7 <= q <= O(s^{3/2}). On the positive side, we show that when q= \Omega(s^2) the Turan graph indeed achieves the maximum number of q-colorings. Joint work with Humberto Naves.

Series: Combinatorics Seminar

We discuss the Maker-Breaker component game, played on the edge set of a sparse random graph. Given a graph G and positive integers s and b, the s-component (1:b) game is defined as follows. In every round Maker claims one free edge of G and Breaker claims b free edges. Maker wins this game if her graph contains a connected component of size at least s; otherwise, Breaker wins the game. For the Erdos-Renyi graph G(n,p), we show that the maximum component size achievable by Maker undergoes a phase transition around p = lambda_{b+2}/n, where lambda_k is the threshold for the appearance of a non-empty k-core in G(n,p) To this end, we analyze the stabilization time of the k-core process in G(n,p). Joint work with Michael Krivelevich, Tobias Mueller, Alon Naor, and Nicholas Wormald.

Series: Combinatorics Seminar

Abstract: There has been a recent flurry of interest in the spectral theory of tensors and hypergraphs as new ideas have faithfully analogized spectral graph theory to uniform hypergraphs. However, even in their simplest incarnation -- the homogeneous adjacency spectrum -- a large number of seemingly basic questions about hypergraph spectra remain out of reach. One of the problems that has yet to be resolved is the (asymptotically almost sure) spectrum of a random hypergraph in the Erd\H{o}s-R\'{e}nyi sense, and we still don't know the spectrum of complete hypergraphs (other than a kind of implicit description for 3-uniform). We introduce the requisite theoretical framework and discuss some progress in this area that involves tools from commutative algebra, eigenvalue stability, and large deviations.

Series: Combinatorics Seminar

We introduce a discrete dynamical system on the set of partial orientations
of a graph, which generalizes Gioan's cycle-cocycle reversal system. We
explain how this setup allows for a new interpretation of the linear
equivalence of divisors on graphs (chip-firing), and a new proof of Baker
and Norine's combinatorial Riemann Roch formula. Fundamental connections
to the max-flow min-cut theorem will be highlighted.