Seminars and Colloquia by Series

Indexed Additive Energy

Series
Combinatorics Seminar
Time
Friday, January 18, 2013 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Albert Bush – Georgia Tech
The additive energy of a set of integers gives key information on the additive structure of the set. In this talk, we discuss a new, closely related statistic called the indexed additive energy. We will investigate the relationship between the indexed additive energy, the regular additive energy, and the size of the sumset.

Polynomial progressions in the primes

Series
Combinatorics Seminar
Time
Friday, January 11, 2013 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Thai Hoang Le – U. Texas
The Green-Tao theorem says that the primes contain arithmetic progressions of arbitrary length. Tao and Ziegler extended it to polynomial progressions, showing that congurations {a+P_1(d), ..., a+P_k(d)} exist in the primes, where P_1, ..., P_k are polynomials in \mathbf{Z}[x] without constant terms (thus the Green-Tao theorem corresponds to the case where all the P_i are linear). We extend this result further, showing that we can add the extra requirement that d be of the form p-1 (or p + 1) where p is prime. This is joint work with Julia Wolf.

The k-core thresholds in random graphs and hypergraphs

Series
Combinatorics Seminar
Time
Friday, December 7, 2012 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Omar Abuzzahab – University of Pennsylvania, Philadelphia
The k-core of a (hyper)graph is the unique subgraph where all vertices have degree at least k and which is the maximal induced subgraph with this property. It provides one measure of how dense a graph is; a sparse graph will tend to have a k-core which is smaller in size compared to a dense graph. Likewise a sparse graph will have an empty k-core for more values of k. I will survey the results on the random k-core of various random graph models. A common feature is how the size of the k-core undergoes a phase transition as the density parameter passes a critical threshold. I will also describe how these results are related to a class of related problems that initially don't appear to involve random graphs. Among these is an interesting problem arising from probabilistic number theory where the random hypergraph model has vertex degrees that are "non-homogeneous"---some vertices have larger expected degree than others.

Exact minimum degree thresholds for perfect matchings in uniform hypergraphs

Series
Combinatorics Seminar
Time
Friday, November 30, 2012 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Yi Zhao – Georgia State University
Given integers k\ge 3 and d with k/2 \leq d \leq k-1, we give a minimum d-degree condition that ensures a perfect matching in a k-uniform hypergraph. This condition is best possible and extends the results of Pikhurko, R\"odl, Ruci\'{n}ski and Szemer\'edi. Our approach makes use of the absorbing method. This is a joint work with Andrew Treglown.

The van der Waerden Number and Colorings of Hypergraphs

Series
Combinatorics Seminar
Time
Friday, November 16, 2012 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Dmitry Shabanov – Moscow State University and Yandex Corporate
The talk is devoted to the classical problem of estimating the Van der Waerden number W(n,k). The famous Van der Waerden theorem states that, for any integers n\ge 3, k\ge 2, there exists the smallest integer W(n,k) such that in any k-coloring of the set {1,2,...,W(n,k)}, there exists a monochromatic arithmetic progression of length n. Our talk is focused on the lower bounds for the van der Waerden number. We shall show that estimating W(n,k) from below is closely connected with extremal problems concerning colorings of uniform hypergraphs with large girth. We present a new lower bound for W(n,k), whose proof is based on a continuous-time random recoloring process.

On the densities of cliques and independent sets in graphs

Series
Combinatorics Seminar
Time
Friday, November 9, 2012 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Humberto Silva Naves – Math, UCLA –
A variety of problems in extremal combinatorics can be stated as: For two given graphs $H_1$ and $H_2$, if the number of induced copies of $H_1$ in a $n$-vertex graph $G$ is known, what is the maximum or minimum number of induced copies of $H_2$ in $G$? Numerous cases of this question were studied by Tur\'an, Erd\H{o}s, Kruskal and Katona, and several others. Tur\'an proved that the maximal edge density in any graph with no cliques of size $r$ is attained by an $r-1$ partite graph. Kruskal and Katona found that cliques, among all graphs, maximize the number of induced copies of $K_s$ when $r

Tiling simply connected regions by rectangles

Series
Combinatorics Seminar
Time
Friday, November 2, 2012 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Jed Yang – Math, UCLA –

Please Note: Given a set of tiles on a square grid (think polyominoes) and a region, can we tile the region by copies of the tiles? In general this decision problem is undecidable for infinite regions and NP-complete for finite regions. In the case of simply connected finite regions, the problem can be solved in polynomial time for some simple sets of tiles using combinatorial group theory; whereas the NP-completeness proofs rely heavily on the regions having lots of holes. We construct a fixed set of rectangular tiles whose tileability problem is NP-complete even for simply connected regions.This is joint work with Igor Pak.

Hereditary Chip-Firing Models and Spanning Trees

Series
Combinatorics Seminar
Time
Friday, October 26, 2012 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Spencer Backman – School of Math, Georgia Tech –
A hereditary chip-firing model is a chip-firing game whose dynamics are induced by an abstract simplicial complex \Delta on the vertices of a graph, where \Delta may be interpreted as encoding graph gluing data. These models generalize two classical chip-firing games: The Abelian sandpile model, where \Delta is disjoint collection of points, and the cluster firing model, where \Delta is a single simplex. Two fundamental properties of these classical models extend to arbitrary hereditary chip-firing models: stabilization is independent of firings chosen (the Abelian property) and each chip-firing equivalence class contains a unique recurrent configuration. We will present an explicit bijection between the recurrent configurations of a hereditary chip-firing model on a graph G and the spanning trees of G and, if time permits, we will discuss chip-firing via gluing in the context of binomial ideals and metric graphs.

Tree-width and Dimension - Part 1

Series
Combinatorics Seminar
Time
Friday, October 19, 2012 - 15:00 for 1 hour (actually 50 minutes)
Location
Siles 005
Speaker
Tom Trotter – Georgia Tech
Over the past 40 years, researchers have made many connections between the dimension of posets and the issue of planarity for graphs and diagrams, but there appears to be little work connecting dimension to structural graph theory. This situation has changed dramatically in the last several months. At the Robin Thomas birthday conference, Gwenael Joret, made the following striking conjecture, which has now been turned into a theorem: The dimension of a poset is bounded in terms of its height and the tree-width of its cover graph. In this talk, I will outline how Joret was led to this conjecture by the string of results on planarity. I will also sketch how the resolution of his conjecture points to a number of new problems, which should interest researchers in both communities.

Divisors on graphs, connected flags, and syzygies

Series
Combinatorics Seminar
Time
Friday, October 12, 2012 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Farbod Shokrieh – Georgia Tech
Associated to every finite graph G there is a canonical ideal which encodes the linear equivalences of divisors on G. We study this ideal and its associated initial ideal. We give an explicit description of their syzygy modules and the Betti numbers in terms of the "connected flags" of G. This resolves open questions posed by Postnikov-Shapiro, Perkinson-Perlmen-Wilmes, and Manjunath-Sturmfels. No prior knowledge in advanced commutative algebra will be assumed. This is a joint work with Fatemeh Mohammadi.

Pages