Seminars and Colloquia by Series

On the Maximum Number of Rich Lines in General Position

Series
Combinatorics Seminar
Time
Friday, January 27, 2012 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Chris Pryby and Albert BushSchool of Mathematics, Georgia Tech
A famous theorem of Szemeredi and Trotter established a bound on the maximum number of lines going through k points in the plane. J. Solymosi conjectured that if one requires the lines to be in general position -- no two parallel, no three meet at a point -- then one can get a much tighter bound. Using methods of G. Elekes, we establish Solymosi's conjecture on the maximum size of a set of rich lines in general position.

On Approximating Expansion of Small Sets in Graphs

Series
Combinatorics Seminar
Time
Friday, January 13, 2012 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Prasad RaghavendraSchool of Computer Science, Georgia Tech
A small set expander is a graph where every set of sufficiently small size has near perfect edge expansion. This talk concerns the computational problem of distinguishing a small set-expander, from a graph containing a small non-expanding set of vertices. This problem henceforth referred to as the Small-Set Expansion problem has proven to be intimately connected to the complexity of large classes of combinatorial optimization problems. More precisely, the small set expansion problem can be shown to be directly related to the well-known Unique Games Conjecture -- a conjecture that has numerous implications in approximation algorithms. In this talk, we motivate the problem, and survey recent work consisting of algorithms and interesting connections within graph expansion, and its relation to Unique Games Conjecture.

Total Positivity, graphs, tilings and Weakly separated sets

Series
Combinatorics Seminar
Time
Friday, December 9, 2011 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
SuHo OhUniversity of Michigan, Ann Arbor
Wiring diagrams are classical objects of combinatorics. Plabic graphs were defined by Postnikov, to study the total positivity of the Grassmannian. We will show how to generalize several definitions and properties of wiring diagrams to Plabic graphs, proving a conjecture by Leclerc-Zelevinsky and Scott on the way. We will begin with a brief introduction to total positivity and end with connection to cluster algebras. Major part of the talk comes from a joint work with Alexander Postnikov and David Speyer.

Symmetric chain decomposition for cyclic quotients of Boolean algebras and relation to cyclic crystals

Series
Combinatorics Seminar
Time
Friday, November 18, 2011 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Patricia HershNorth Carolina State University, Raleigh, NC
The quotient of a Boolean algebra by a cyclic group is proven to have a symmetric chain decomposition. This generalizes earlier work of Griggs, Killian and Savage on the case of prime order, giving an explicit construction for any order, prime or composite. The combinatorial map specifying how to proceed downward in a symmetric chain is shown to be a natural cyclic analogue of Kashiwara's sl_2 lowering operator in the theory of crystal bases. The talk will include a survey of related past work on symmetric chain decomposition and unimodality by Greene-Kleitman, Griggs-Killian-Savage, Proctor, Stanley and others as well as a discussion of open questions that still remain. This is joint work with Anne Schilling.

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. WestUniversity 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 McDonaldSimon 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 YuSchool 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 VallaCharles 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 RiceUniversity 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.

Pages