Seminars & Events for Discrete Mathematics Seminar

September 20, 2012
2:00pm - 3:30pm
The Erdos-Stone Theorem for finite geometries

For any class of graphs, the growth function h(n) of the class is defined to be the maximum number of edges in a graph in the class on n vertices. The Erdos-Stone Theorem remarkably states that, for any class of graphs that is closed under taking subgraphs, the asymptotic behaviour of h(n) can (almost) be precisely determined just by the minimum chromatic number of a graph not in the class. I will present a surprising version of this theorem for finite geometries, obtained in joint work with Jim Geelen. This result is a corollary of the famous Density Hales-Jewett Theorem of Furstenberg and Katznelson.

Speaker: Peter Nelson, Victoria University of Wellington
Location:
Fine Hall 224
September 27, 2012
2:00pm - 3:30pm
Apollonian structure in the abelian sandpile

The Abelian sandpile is a diffusion process on configurations of chips on the integer lattice, in which a vertex with at least 4 chips can "topple", distributing one of its chips to each of its 4 neighbors. Though the sandpile has been the object of study from a diverse set of perspectives, even some of the most basic questions about the terminal configurations produced by the process have remained unanswered. One of the most striking features of the sandpile is that when begun from a large concentration of n chips, the resulting terminal configurations seem to converge to a peculiar fractal pattern as n goes to infinity.

Speaker: Wesley Pegden , NYU
Location:
Fine Hall 224
October 4, 2012
2:00pm - 3:30pm
What have we learned about graph partitioning?

The graph partitioning problem consists of cutting a graph into two or more large pieces so as to minimize the number of edges between them. Since the problem is NP-hard, one needs to resort to approximation. This talk will give a quick survey of techniques for graph partitioning, focusing on work in the past 7-8 years that uses semidefinite programming and spectral techniques.

Speaker: Sanjeev Arora, Princeton University
Location:
Fine Hall 224
October 11, 2012
2:00pm - 3:30pm
Extremal problems in Eulerian digraphs

Graphs and digraphs behave quite differently, and many classical results for graphs are often trivially false when extended to general digraphs. Therefore it is usually necessary to restrict to a smaller family of digraphs to obtain meaningful results. One such very natural family is Eulerian digraphs, in which the in-degree equals out-degree at every vertex. In this talk, we discuss several natural parameters for Eulerian digraphs and study their connections. In particular, we show that for any Eulerian digraph G with n vertices and m arcs, the minimum feedback arc set (the smallest set of arcs whose removal makes G acyclic) has size at least m^2/2n^2 +m/2n, and this bound is tight. Using this result, we show how to find subgraphs of high minimum degrees, and also long cycles in Eulerian digraphs.

Speaker: Hao Huang , IAS
Location:
Fine Hall 224
October 18, 2012
2:00pm - 3:30pm
Directed width parameters: algorithms and structural properties

Treewidth of an undirected graph measures how close the graph is to being a tree. Several problems that are NP-hard on general graphs are solvable in polynomial time on graphs with bounded treewidth. Motivated by the success of treewidth, several directed analogues of treewidth have been introduced to measure the similarity of a directed graph to a directed acyclic graph (DAG). Directed treewidth, D-width, DAG-width and Kelly-width are some such width parameters. In this talk, I will present some of the algorithms and structural properties of these parameters with emphasis on Kelly-width and its equivalent characterizations. I will present some recent results and new research directions.

Speaker: Shiva Kintali, Princeton University
Location:
Fine Hall 224
October 25, 2012
2:00pm - 3:30pm
Expanders with respect to random regular graphs

The discrete Poincare inequality (PI) for a regular graph G=(V,E) is the following: For any mapping f:V-->H of the vertices into Hilbert space, the average of ||f(u)-f(v)||^2 over all pairs of vertices is at most the average of ||f(u)-f(v)||^2 over the edges (E) times 1/(1-lambda_2(G)), where lambda_2(G) is the second normalized eigenvalue of G. This inequality has a natural metric interpretation: There is no way to embed a constant degree expander in Hilbert space while "uniformly" preserving the shortest path metric, since in the shortest path metric the average square distance over all pairs is unbounded, whereas the average over the edges is (at most) 1. Motivated by this application, PI has been strengthen by replacing Hilbert space with other metric spaces X.

Speaker: Manor Mendel , Open U Israel and IAS
Location:
Fine Hall 224
November 8, 2012
2:00pm - 3:30pm
On the Erdos-Sos conjecture

We are going to prove that if k is large enough then a graph with average degree k contains all trees on k vertices.  This is joint work with Miklos Ajtai, Janos Komlos and Miklos Simonovits.

Speaker: Endre Szemeredi , Rutgers University
Location:
Fine Hall 224
November 15, 2012
2:00pm - 3:30pm
How long does it take to catch a drunk miscreant?

We discuss the answer to a question of Churchley who asked how long it will take a cop to catch a drunk robber who moves randomly. We begin by discussing other variants of the cop-robber paradigm. This is
joint work with Alex Scott, Colin McDiarmid, and Ross Kang. We rely heavily on work of Komarov and Winkler.

Speaker: Bruce Reed , McGill University
Location:
Fine Hall 224
November 29, 2012
2:00pm - 3:30pm
A Szemeredi-Trotter theorem in R^4

The Szemeredi-Trotter theorem states that m points and n lines in the plane can have at most O(m^{2/3}n^{2/3}+m+n) incidences. This theorem has seen a number of generalizations, including a theorem of Toth that obtains the same result for (complex) points and lines in the complex plane. PLEASE CLICK ON SEMINAR TITLE FOR COMPLETE ABSTRACT.

Speaker: Josh Zahli , UCLA
Location:
Fine Hall 224
December 6, 2012
2:00pm - 3:30pm
Cover-decomposition and polychromatic numbers

In the cover-decomposition problem we are given a ground set of points and a collection of its subsets. Suppose that we want to colour some subsets blue and the others red, so that every point lies in both a blue subset and a red subset. An obvious necessary condition is that every point lies in at least two subsets; is there an exact or approximate converse? What about when there are many colours? Using probabilistic methods and iterated linear programming we'll give positive answers in some settings. This is joint work with Bela Bollobas, Thomas Rothvoss and Alex Scott.

Speaker: David Pritchard, Princeton University
Location:
Fine Hall 224
February 14, 2013
4:30pm - 6:00pm
Polar codes and randomness extraction for structured sources

Polar codes have recently emerged as a new class of low-complexity codes achieving Shannon capacity. This talk introduces polar codes with emphasis on the probabilistic phenomenon underlying the code construction. New results and connections to matroid theory and randomness extraction are discussed.

Speaker: Emmanuel Abbe , Princeton University
Location:
Fine Hall 224
February 21, 2013
4:30pm - 6:00pm
Discrepancy of graphs and hypergraphs

How uniformly is it possible to distribute edges in a graph? For instance, is there a graph of density 1/2 in which every induced subgraph has approximately the same number of edges as nonedges? Erdos and Spencer showed in 1971 that every graph on n vertices has an induced subgraph in which the numbers of edges and nonedges differ by at least cn^{3/2} (and gave a similar result for hypergraphs). Erdos, Goldberg, Pach and Spencer subsequently proved a weighted extension of this for graphs with density p. We shall discuss generalizations of these results and related questions involving intersections of pairs of graphs or hypergraphs. Joint work with Bela Bollobas.

Speaker: Alex Scott, Oxford University
Location:
Fine Hall 224
March 7, 2013
4:30pm - 6:00pm
Graph constructions, graph decompositions, and random graphs

Recent work of Kolaitis and Kopparty relates the number of copies of a subgraph in the random graph G(n; p) to questions about logic and circuit complexity. PLEASE CLICK ON SEMINAR TITLE FOR COMPLETE ABSTRACT.

Speaker: Amanda Redlich , Rutgers University
Location:
Fine Hall 224
March 14, 2013
4:30pm - 6:00pm
Informal and formal verification of nonlinear inequalities with applications to discrete geometry

This talk will describe some tools for the automated verification of nonlinear inequalities involving a small number of real independent variables.  Various problems in discrete geometry can be reduced to finite collections of nonlinear inequalities.   In this way computer-assisted proofs of various conjectures in discrete geometry can be obtained.

Speaker: Tom Hales , University of Pittsburgh Mellon
Location:
Fine Hall 224
March 28, 2013
4:30pm - 6:00pm
Even-cycle decompositions of graphs with no odd-K_4-minor

A graph is ``even-cycle decomposable'' if its edge set can be partitioned into even length cycles. Evidently, every Eulerian bipartite graph is even-cycle decomposable. PLEASE CLICK ON SEMINAR TITLE FOR COMPLETE ABSTRACT.

Speaker: Tony Huynh , Simon Fraser
Location:
Fine Hall 224
April 11, 2013
4:30pm - 6:00pm
Transversal signed-graphic matroids

Signed-graphic matroids are a genuine generalization of graphic matroids, and a lot of research has been done on determining to what extent we can transfer properties of graphic matroids to signed-graphic matroids. In this talk we focus on two theorems from the 1970s. The first one, due to Matthews, characterizes graphs whose bicircular matroids are graphic. We characterize graphs whose bicircular matroids are signed-graphic. The second one, due to Bondy and Las Vergnas, characterizes graphs whose cycle matroids are transversal. We attempt to characterize signed graphs whose frame matroids are transversal. Time permitting, we will discuss the issue of basis counting in different classes of matroids, and progress on a related conjecture of Welsh.

Speaker: Vaidy Sivaraman , Binghamton University
Location:
Fine Hall 224
April 18, 2013
4:30pm - 6:00pm
On Relative Approximations in Geometric Hypergraphs

Motivated by range counting problems, relative approximations have become a central tool in computational geometry. In fact, they were introduced by Har-Peled and Sharir, who derived them from the seminal work of Li, Long, and Srinivasan in the theory of machine learning. In this talk I will discuss properties of relative approximations, and present improved upper bounds for their size under certain favorable assumptions. Our approach is probabilistic, where we apply the constructive version of the Asymmetric Lovasz Local Lemma.

Speaker: Esther Ezra , NYU
Location:
Fine Hall 224
May 2, 2013
4:30pm - 6:00pm
A polynomial time algorithm for lossy population recovery

PLEASE CLICK ON SEMINAR TITLE FOR COMPLETE ABSTRACT. We give a polynomial time algorithm for the lossy population recovery problem. In this problem, the goal is to approximately learn an unknown distribution on binary strings of length n from lossy samples: for some parameter μ each coordinate of the sample is preserved with probability μ and otherwise is replaced by a ‘?’.

Speaker: Ankur Moitra , IAS
Location:
Fine Hall 224