Seminars and Colloquia by Series

Expanders via Random Spanning Trees

Series
Combinatorics Seminar
Time
Friday, December 5, 2008 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Luis Rademacher – School of Computer Science, Georgia Tech
Expanders via Random Spanning Trees Motivated by the problem of routing reliably and scalably in a graph, we introduce the notion of a splicer, the union of spanning trees of a graph. We prove that for any bounded-degree n-vertex graph, the union of two random spanning trees approximates the expansion of every cut of the graph to within a factor of O(log n). For the random graph G_{n,p}, for p > c (log n)/n, two spanning trees give an expander. This is suggested by the case of the complete graph, where we prove that two random spanning trees give an expander. The construction of the splicer is elementary — each spanning tree can be produced independently using an algorithm by Aldous and Broder: a random walk in the graph with edges leading to previously unvisited vertices included in the tree. A second important application of splicers is to graph sparsification where the goal is to approximate every cut (and more generally the quadratic form of the Laplacian) using only a small subgraph of the original graph. Benczur-Karger as well as Spielman-Srivastava have shown sparsifiers with O(n log n/eps^2) edges that achieve approximation within factors 1+eps and 1-eps. Their methods, based on independent sampling of edges, need Omega(n log n) edges to get any approximation (else the subgraph could be disconnected) and leave open the question of linear-size sparsifiers. Splicers address this question for random graphs by providing sparsifiers of size O(n) that approximate every cut to within a factor of O(log n). This is joint work with Navin Goyal and Santosh Vempala.

Vizing's Independence Number Conjecture on Edge Chromatic Critical Graphs

Series
Combinatorics Seminar
Time
Friday, November 21, 2008 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Nick Zhao – University of Central Florida
In 1968, Vizing proposed the following conjecture which claims that if G is an edge chromatic critical graph with n vertices, then the independence number of G is at most n/2. In this talk, we will talk about this conjecture and the progress towards this conjecture.

Green's Conjecture and Testing Linear-Invariant Properties

Series
Combinatorics Seminar
Time
Friday, November 7, 2008 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Asaf Shapira – School of Mathematics, Georgia Tech
Given a set of linear equations Mx=b, we say that a set of integers S is (M,b)-free if it contains no solution to this system of equations. Motivated by questions related to testing linear-invariant Boolean functions, as well as recent investigations in additive number theory, the following conjecture was raised (implicitly) by Green and by Bhattacharyya, Chen, Sudan and Xie: we say that a set of integers S \subseteq [n], is \epsilon-far from being (M,b)-free if one needs to remove at least \epsilon n elements from S in order to make it (M,b)-free. The conjecture was that for any system of homogeneous linear equations Mx=0 and for any \epsilon > 0 there is a *constant* time algorithm that can distinguish with high probability between sets of integers that are (M,0)-free from sets that are \epsilon-far from being (M,0)-free. Or in other words, that for any M there is an efficient testing algorithm for the property of being (M,0)-free. In this paper we confirm the above conjecture by showing that such a testing algorithm exists even for non-homogeneous linear equations. As opposed to most results on testing Boolean functions, which rely on algebraic and analytic arguments, our proof relies on results from extremal hypergraph theory, such as the recent removal lemmas of Gowers, R\"odl et al. and Austin and Tao.

Polynomial configurations in difference sets

Series
Combinatorics Seminar
Time
Friday, October 31, 2008 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Neil Lyall – University of Georgia
We will discuss some extensions/generalizations of the striking and elegant fact (proved independently by Furstenberg and Sarkozy) that any subset of the integers of positive upper density necessarily contains two distinct elements whose difference is a perfect square. This is joint work with Akos Magyar.

The triangle-free process

Series
Combinatorics Seminar
Time
Friday, October 24, 2008 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Tom Bohman – CMU
Consider the following random graph process. We begin with the empty graph on n vertices and add edges chosen at random one at a time. Each edge is chosen uniformly at random from the collection of pairs of vertices that do not form triangles when added as edges to the existing graph. In this talk I discuss an analysis of the triangle-free process using the so-called differential equations method for random graph processes. It turns out that with high probability the triangle-free process produces a Ramsey R(3,t) graph, a triangle-free graph whose independence number is within a multiplicative constant factor of the smallest possible.

The Erdos-Ko-Rado Theorem

Series
Combinatorics Seminar
Time
Monday, October 20, 2008 - 11:05 for 1.5 hours (actually 80 minutes)
Location
Skiles 255
Speaker
Chris Godsil – University of Waterloo
In its simplest form, the Erdos-Ko-Rado theorem tells us that if we have a family F of subsets of size k from set of size v such that any two sets in the family have at least one point in common, then |F|<=(v-1)\choose(k-1) and, if equality holds, then F consists of all k-subsets that contain a given element of the underlying set. This theorem can also be viewed as a result in graph theory, and from this viewpoint it has many generalizations. I will outline how it can be proved using linear algebra, and then discuss how this approach can be applied in other cases.

Self-intersection of random paths

Series
Combinatorics Seminar
Time
Friday, October 17, 2008 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Ravi Montenegro – University of Massachussetts
The Birthday Paradox says that if there are N days in a year, and 1.2*sqrt(N) days are chose uniformly at random with replacement, then there is a 50% probability that some day was chosen twice. This can be interpreted as a statement about self-intersection of random paths of length 1.2*sqrt(N) on the complete graph K_N with loops. We prove an extension which shows that for many graphs random paths with length of order sqrt(N) will have the same self-intersection property. We finish by discussing an application to the Pollard Rho Algorithm for Discrete Logarithm. (joint work with Jeong-Han Kim, Yuval Peres and Prasad Tetali).

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 Lu – University 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 Goulden – University 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 Lefmann – Technical 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.

Pages