Seminars and Colloquia by Series

Decomposition of Sparse Graphs into Forests and a Graph with Bounded Degree

Series
Combinatorics Seminar
Time
Friday, November 4, 2011 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Prof. Douglas B. West – University of Illinois
Say that a graph with maximum degree at most $d$ is {\it $d$-bounded}.  For$d>k$, we prove a sharp sparseness condition for decomposition into $k$ forestsand a $d$-bounded graph.  The condition holds for every graph with fractionalarboricity at most $k+\FR d{k+d+1}$.  For $k=1$, it also implies that everygraph with maximum average degree less than $2+\FR{2d}{d+2}$ decomposes intoone forest and a $d$-bounded graph, which contains several earlier results onplanar graphs.

Immersing cliques in graphs and digraphs

Series
Combinatorics Seminar
Time
Friday, October 28, 2011 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Jessica McDonald – Simon Frazer University
Immersion is a containment relation between graphs (or digraphs) which is defined similarly to the more familiar notion of minors, but is incomparable to it. Of particular interest is to find conditions on a graph (or digraph) G which guarantee that G contains a clique (or bidirected clique) of order t as an immersion. This talk will begin with a gentle introduction, and will then share two new results of this form, one for graphs and one for digraphs. In the former case, we find that minimum degree 200t is sufficient, and in the later case, we find that minimum degree t(t-1) is sufficient, provided that G is Eulerian. These results come from joint work with Matt DeVos, Jacob Fox, Zdenek Dvorak, Bojan Mohar and Diego Scheide.

Triangulations and Resultants

Series
Combinatorics Seminar
Time
Friday, October 21, 2011 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Josephine Yu – School of Math, Ga Tech
The secondary polytope of a point configuration A is a polytope whose faces are in bijection with regular subdivions of A, e.g. the secondary polytope of the vertices of polygon is an associahedron. The resultant of a tuple of point configurations A_1, A_2, ..., A_k in Z^n is the set of coefficients for which the polynomials with supports A_1, A_2, ..., A_k have a common root with no zero coordinates over complex numbers, e.g. when each A_1 is a standard simplex and k = n+1, the resultant is defined by a determinant. The Newton polytope of a polynomial is the convex hull of the exponents, e.g. the Newton polytope of the determinant is the perfect matching polytope. In this talk, I will explain the close connection between secondary polytopes and Newton polytopes of resultants, using tropical geometry, based on joint work with Anders Jensen.

Restricted Ramsey theorems and Combinatorial Games

Series
Combinatorics Seminar
Time
Friday, October 14, 2011 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Thomas Valla – Charles University, Prague
Ramsey theory studies the internal homogenity of mathematical structures (i.e. graphs, number sets), parts of which (subgraphs, number subsets) are arbitrarily coloured. Often, the sufficient object size implies the existence of a monochromatic sub-object. Combinatorial games are 2-player games of skill with perfect information. The theory of combinatorial games studies mostly the questions of existence of winning or drawing strategies. Let us consider an object that is studied by a particular Ramsey-type theorem. Assume two players alternately colour parts of this object by two colours and their goal is to create certain monochromatic sub-object. Then this is a combinatorial game. We focus on the minimum object size such that the appropriate Ramsey-type theorem holds, called "Ramsey number", and on the minimum object size such that the first player has a winning strategy in the corresponding combinatorial game, called "game number". In this talk, we investigate the "restricted Ramsey-type theorems". This means, we show the existence of first player's winning strategies, and we show that game numbers are surprisingly small, compared to Ramsey numbers. (This is joint work with Jarek Nesetril.)

Polynomial Patterns in Subsets of the Integers

Series
Combinatorics Seminar
Time
Friday, September 30, 2011 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Alex Rice – University of Georgia
How large can a subset of the first N natural numbers be before it is guaranteed to contain two distinct elements which differ by a perfect square? What if I replaced "perfect square" with the image of a more general polynomial, or perhaps "one less than a prime number"? We will discuss results of this flavor, including recent improvements and generalizations.

Concave generalized flows with applications to market equilibria

Series
Combinatorics Seminar
Time
Friday, September 9, 2011 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Laszlo Vegh – School of Computer Science, Georgia Tech –
The generalized flow model is a classical and widely applicable extension of network flows, where on every arc, the flow leaving the arc is a linear function of the flow entering the arc. In the talk, I will investigate a nonlinear extension of this model, with the flow leaving an arc being a concave function of the entering flow. I exhibit the first combinatorial polynomial time algorithm for solving corresponding optimization problems. This model turns out to be a common framework for solving several market equilibrium problems, such as linear Fisher markets, and immediately enables to extend them to more general settings. I will also give a survey on generalized flow algorithms and previous nonlinear flow models.

Clustering in Discrete Models of Colloids

Series
Combinatorics Seminar
Time
Friday, May 6, 2011 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Amanda Pascoe Streib – Georgia Tech
Colloids are mixtures of molecules  well-studied in material science that are not well-understood mathematically.  Physicists model colloids as a system of two types of tiles (type A and type B) embedded on a region of the plane, where no two tiles can overlap.  It is conjectured that at high density, the type A tiles tend to separate out and form large "clusters".   To verify this conjecture, we need methods for counting these configurations directly or efficient algorithms for sampling.  Local sampling algorithms are known to be inefficient. However, we provide the first rigorous analysis of a global "DK Algorithm" introduced by Dress and Krauth.  We also examine the clustering effect directly via a combinatorial argument. We prove for a certain class of colloid models that at high density the configurations are likely to exhibit clustering, whereas at low density the tiles are all well-distributed. Joint work with Sarah Miracle and Dana Randall.

The Bohman-Frieze Process

Series
Combinatorics Seminar
Time
Friday, April 29, 2011 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Will Perkins – Courant Institute, NYU –
The Bohman-Frieze process is a simple modification of the Erdős-Rényi random graph that adds dependence between the edges biased in favor of joining isolated vertices. We present new results on the phase transition of the Bohman-Frieze process and show that qualitatively it belongs to the same class as the Erdős-Rényi process. The results include the size and structure of small components in the barely sub- and supercritical time periods. We will also mention a class of random graph processes that seems to exhibit markedly different critical behavior.

Testing Odd-Cycle Freeness of Boolean Functions

Series
Combinatorics Seminar
Time
Friday, April 22, 2011 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Elena Grigorescu – College of Computing, Georgia Tech
In the Property Testing model an algorithm is required to distinguish between the case that an object has a property or is far from having the property. Recently, there has been a lot of interest in understanding which properties of Boolean functions admit testers making only a constant number of queries, and a common theme investigated in this context is linear invariance. A series of gradual results has led to a conjectured characterization of all testable linear invariant properties. Some of these results consider properties where the query upper bounds are towers of exponentials of large height dependent on the distance parameter. A natural question suggested by these bounds is whether there are non-trivial families with testers making only a polynomial number of queries in the distance parameter.In this talk I will focus on a particular linear-invariant property where this is indeed the case: odd-cycle freeness.Informally, a Boolean function fon n variables is odd-cycle free if there is no x_1, x_2, .., x_2k+1 satisfying f(x_i)=1 and sum_i x_i = 0.This property is the Boolean function analogue of bipartiteness in the dense graph model. I will discuss two testing algorithms for this property: the first relies on graph eigenvalues considerations and the second on Fourier analytic techniques. I will also mention several related open problems. Based on joint work with Arnab Bhattacharyya, Prasad Raghavendra, Asaf Shapira

Pages