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

Series: Combinatorics Seminar

In a "rotor walk" the exits from each vertex follow a prescribed
periodic sequence. On an infinite Eulerian graph embedded periodically
in $\R^d$, we show that any simple rotor walk, regardless of rotor
mechanism or initial rotor configuration, visits at least on the order
of t^{d/(d+1)} distinct sites in t steps. We prove a shape theorem for the
rotor walk on the comb graph with i.i.d.\ uniform initial rotors, showing
that the range is of order t^{2/3} and the asymptotic shape of the range is a
diamond. Using a connection to the mirror model and critical percolation,
we show that rotor walk with i.i.d. uniform initial rotors is recurrent on
two different directed graphs obtained by orienting the edges of the square
grid, the Manhattan lattice and the F-lattice.
Joint work with Lionel Levine and Yuval Peres.

Series: Combinatorics Seminar

The Jacobian group Jac(G) of a finite graph G is a finite abelian group whose cardinality is the number of spanning trees of G. It is natural to wonder whether there is a canonical simply transitive action of Jac(G) on the set of spanning trees which "explains" this numerical coincidence. Surprisingly, this turns out to be related to topological embeddings: we will explain a certain precise sense in which the answer is yes if and only if G is planar. We will also explain how tropical geometry sheds an interesting new light on this picture.

Series: Combinatorics Seminar

In graph/hypergraph theory, perfect matchings are fundamental objects of study. Unlike the graph case, perfect matchings in hypergraphs have not been well understood yet. It is quite natural and desirable to
extend the classical theory on perfect matchings from graphs to hypergraphs, as many important problems
can be phrased in this framework, such as Ryser's conjecture on transversals in Latin squares and the
Existence Conjecture for block designs. I will focus on Dirac-type conditions (minimum degree
conditions) in uniform hypergraphs and discuss some recent progresses. In particular, we determine the
minimum codegree threshold for the existence of a near perfect matching in hypergraphs, which confirms a
conjecture of Rodl, Rucinski and Szemeredi, and we show that there is a polynomial-time algorithm
that can determine whether a k-uniform hypergraph with minimum codegree n/k has a perfect matching,
which solves a problem of Karpinski, Rucinski and Szymanska completely.

Series: Combinatorics Seminar

We will present the solution to a statistical mechanics model on random lattices. More precisely, we consider the Potts model on the set of planar triangulations (embedded planar graph such that every face has degree 3). The partition function of this model is the generating function of vertex-colored triangulations counted according to the number of monochromatic edges and dichromatic edges. We characterize this partition function by a simple system of differential equations. Some special cases, such as properly 4-colored triangulations, lead to particularly simple equations waiting for a more direct combinatorial explanation. This is joint work with Mireille Bousquet-Melou.

Series: Combinatorics Seminar

In this talk I will present the notion of a \delta-packing for set systems of bounded primal shatter dimension (closely related to the notion of finite VC-dimension). The structure of \delta-packing, which has been studied by Dudley in 1978 and Haussler in 1995, emerges from empirical processes and is fundamental in theoretical computer science and in computational geometry in particular. Moreover, it has applications in geometric discrepancy, range searching, and epsilon-approximations, to name a few. I will discuss a variant of \delta-packings where all the sets have small cardinality, we call these structures "shallow packings", and then present an upper bound on their size under additional natural assumptions on the set system, which correspond to several geometric settings, among which is the case of points and halfspaces in d-dimensions.

Series: Combinatorics Seminar

Bio: Georgios Piliouras is a postdoc at Caltech, Center for Mathematics and

Computation. He received his PhD in Computer Science from Cornell

University and has been a Georgia Tech postdoc at the EE department.

In a recent series of papers a strong connection has been established
between standard models of sexual evolution in mathematical biology and
Multiplicative Weights Updates Algorithm, a ubiquitous model of online
learning and optimization. These papers show that mathematical models of
biological evolution are tantamount to applying discrete replicator
dynamics, a close variant of MWUA on coordination games. We show that in
the case of coordination games, under minimal genericity assumptions,
discrete replicator dynamics converge to pure Nash equilibria for all but a
zero measure of initial conditions. This result holds despite the fact that
mixed Nash equilibria can be exponentially (or even uncountably) many,
completely dominating in number the set of pure Nash equilibria. Thus, in
haploid organisms the long term preservation of genetic diversity needs to
be safeguarded by other evolutionary mechanisms, such as mutation and
speciation.
This is joint work with Ruta Mehta and Ioannis Panageas.

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.