Seminars and Colloquia by Series

The giant component in a random subgraph of a given graph

Series
Combinatorics Seminar
Time
Thursday, October 9, 2008 - 16:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Lincoln LuUniversity of South Carolina
We consider a random subgraph G_p of a host graph G formed by retaining each edge of G with probability p. We address the question of determining the critical value p (as a function of G) for which a giant component emerges. Suppose G satisfies some (mild) conditions depending on its spectral gap and higher moments of its degree sequence. We define the second order average degree \tilde{d} to be \tilde{d}=\sum_v d_v^2/(\sum_v d_v) where d_v denotes the degree of v. We prove that for any \epsilon > 0, if p > (1+ \epsilon)/\tilde{d} then almost surely the percolated subgraph G_p has a giant component. In the other direction, if p < (1-\epsilon)/\tilde{d} then almost surely the percolated subgraph G_p contains no giant component. (Joint work with Fan Chung Graham and Paul Horn)

Maps and Branched Covers - Combinatorics, Geometry and Physics

Series
Combinatorics Seminar
Time
Friday, October 3, 2008 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Ian GouldenUniversity of Waterloo
This is an expository account of recent work on the enumeration of maps (graphs embedded on a surface of arbitrary genus) and branched covers of the sphere.  These combinatorial and geometric objects can both be represented by permutation factorizations, in the which the subgroup generated by the factors acts transitively on the underlying symbols (these are called "transitive factorizations"). Various results and methods are discussed, including a number of methods from mathematical physics, such as matrix integrals and the KP hierarchy of integrable systems. A notable example of the results is a recent recurrence for triangulations of a surface of arbitrary genus obtained from the simplest partial differential equation in the KP hierarchy. The recurrence is very simple, but we do not know a combinatorial interpretation of it, yet it leads to precise asymptotics for the number of triangulations with n edges, of a surface of genus g.

Avoiding Grid-Points in Affine or Linear Spaces of Small Dimension

Series
Combinatorics Seminar
Time
Thursday, September 25, 2008 - 12:05 for 1.5 hours (actually 80 minutes)
Location
Skiles 255
Speaker
Hanno LefmannTechnical University Chemnitz, Germany
Motivated by a question raised by P\'or and Wood in connection with compact embeddings of graphs into the grid {\mathbb Z}^d, we consider generalizations of the no-three-in-line-problem. For several pairs (d,k,l) we give algorithmic or probabilistic, combinatorial lower, and upper bounds on the largest sizes of subsets S of grid-points in the d-dimensional T \times ... \times T-grid, where T is large and no l distinct grid-points of S are contained in a k-dimensional affine or linear subspace.

On a hypergraph generalization of the Balog-Szemeredi-Gowers Theorem

Series
Combinatorics Seminar
Time
Friday, September 19, 2008 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Evan BorensteinSchool of Mathematics, Georgia Tech
The Balog-Szemeredi-Gowers theorem is a widely used tool in additive combinatorics, and it says, roughly, that if one has a set A such that the sumset A+A is "concentrated on few values," in the sense that these values v each get close to n representations as v = a+b, with a,b in A, then there is a large subset A' of A such that the sumset A'+A' is "small" -- i.e. it has size a small multiple of n. Later, Sudakov, Szemeredi and Vu generalized this result to handle multiple sums A_1 + ... + A_k. In the present talk we will present a refinement of this result of Sudakov, Szemeredi and Vu, where we get better control on the growth of sums A'+...+A'. This is joint work with Ernie Croot.

On the upper bound for the Tur\'an density of K^r_{r+1}

Series
Combinatorics Seminar
Time
Friday, September 12, 2008 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Yi ZhaoGeorgia State University
Let K^r_{r+1} denote the complete r-graph on r+1 vertices. The Turan density of K^r_{r+1} is the largest number t such that there are infinitely many K^r_{r+1}-free r-graphs with edge density t-o(1). Determining t(K^r_{r+1}) for r > 2 is a famous open problem of Turan. The best upper bound for even r, t(K^r_{r+1})\leq 1-1/r, was given by de Caen and Sidorenko. In a joint work with Linyuan Lu, we slightly improve it. For example, we show that t(K^r_{r+1})\leq 1 - 1/r - 1/(2r^3) for r=4 mod 6.  One of our lemmas also leads to an exact result for hypergraphs.  Given r > 2, let p be the smallest prime factor of r-1. Every r-graph on n > r(p-1) vertices such that every r+1 vertices contain 0 or r edges must be empty or a complete star.

On rich lines in grids

Series
Combinatorics Seminar
Time
Friday, September 5, 2008 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Ernie CrootSchool of Mathematics, Georgia Tech
Let A be a set of n real numbers. A central problem in additive combinatorics, due to Erdos and Szemeredi, is that of showing that either the sumset A+A or the product set A.A, must have close to n^2 elements. G. Elekes, in a short and brilliant paper, showed that one can give quite good bounds for this problem by invoking the Szemeredi-Trotter incidence theorem (applied to the grid (A+A) x (A.A)). Perhaps motivated by this result, J. Solymosi posed the following problem (actually, Solymosi's original problem is slightly different from the formulation I am about to give). Show that for every real c > 0, there exists 0 < d < 1, such that the following holds for all grids A x B with |A| = |B| = n sufficiently large: If one has a family of n^c lines in general position (no three meet at a point, no two parallel), at least one of them must fail to be n^(1-d)-rich -- i.e. at least one of then meets in the grid in fewer than n^(1-d) points. In this talk I will discuss a closely related result that I and Evan Borenstein have proved, and will perhaps discuss how we think we can use it to polish off this conjecture of Solymosi.

Bilinear and Quadratic variants on the Littlewood-Offord Lemma

Series
Combinatorics Seminar
Time
Friday, August 29, 2008 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Kevin CostelloSchool of Mathematics, Georgia Tech
Let f be a polynomial or multilinear form in a large number of variables. A basic question we can ask about f is how dispersed it becomes as the number of variables increases. To be more concrete: If we randomly (and independently) set each entry to be either 1 or -1, what is the largest concentration of the output of f on any single value, assuming all (or most) of the coefficients of f are nonzero? Can we somehow describe the structure of those forms which are close to having maximal concentration? If f is a linear polynomial, this is a question originally examined by Littlewood and Offord and answered by Erdos: The maximal concentration occurs when all the nonzero coefficients of f are equal. Here we will consider the case where f is a bilinear or quadratic form.

Pages