If you

Subscribe to the ACO seminar mailing list

Title: The triangle-free process

Speaker: Tom Bohman

When: Thursday, September 18, 4:30-5:30

Where: Wean 5320

Abstract:

Speaker: Tom Bohman

When: Thursday, September 18, 4:30-5:30

Where: Wean 5320

Abstract:

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.

Title: An Analytic Approach to Stability

Speaker: Oleg Pikhurko

When: Thursday, September 25, 4:30-5:30

Where: Wean 5320

Abstract:

Speaker: Oleg Pikhurko

When: Thursday, September 25, 4:30-5:30

Where: Wean 5320

Abstract:

I present an attempt to understand how the recently developed
theory of graph limits may apply to finite problem of extremal graph
theory. We formulate the notion of a stable problem (meaning, roughly
speaking, that almost extremal graphs have structure close to that of an
extremal graph) and give an equivalent characterization in terms of graph
limits. As an application, we present a new proof of the Erdos-Simonovits
stability theorem.

Title: Degree Bounded Directed Network Design

Speaker: Viswanath Nagarajan

When: Thursday, October 2, 4:30-5:30

Where: Wean 5320

Abstract:

Speaker: Viswanath Nagarajan

When: Thursday, October 2, 4:30-5:30

Where: Wean 5320

Abstract:

We show that the minimum degree arborescence problem admits a plus 2 approximation
algorithm. This is then extended to a large class of "intersecting supermodular" connectivity
problems on digraphs, to obtain additive approximations for the degree-bounded variants. As a
byproduct of these results, we also obtain a short proof of the recent "plus 1" approximation
result for bounded-degree minimum spanning tree.

Title: Cliques in Steiner Systems

Speaker: Andrzej Dudek

When: Thursday, October 9, 4:30-5:30

Where: Wean 5320

Abstract:

Speaker: Andrzej Dudek

When: Thursday, October 9, 4:30-5:30

Where: Wean 5320

Abstract:

A partial Steiner (k,l)-system is a k-uniform hypergraph G=(V,E) with the property that every l-element subset of V is
contained in at most one edge of G. In this talk we show that for given k, l and t there exists a partial Steiner
(k,l)-system such that whenever an l-element subset from every edge is chosen, the resulting l-uniform hypergraph contains a
clique of size t. We also establish asymptotic lower and upper bounds on the size of such cliques with respect to the order
of Steiner triple systems.

This is joint work with Franti\v{s}ek Fran\v{e}k and Vojta R\"odl.

Title: From the Circle method to the Circular Law

Speaker: Van Vu, Rutgers University

When: Friday, October 17, 4:30-5:30 (Note unusual place and time. This is a math department colloquium.)

Where: Wean 7500

Abstract:

Speaker: Van Vu, Rutgers University

When: Friday, October 17, 4:30-5:30 (Note unusual place and time. This is a math department colloquium.)

Where: Wean 7500

Abstract:

A starting point of the theory of random matrices is Wigner's semi-circle law obtained in the 1950s, which asserts that (after a proper normalization) the limiting distribution of the spectra of a random hermitian matrix with iid (upper diagonal) entries follows the semi-circle law. The non-hermitian case is the famous Circular Law Conjecture, which asserts that (after a proper normalization) the limiting distribution of the spectra of a random matrix with iid entries is uniform in the unit circle. Despite several important partial results (Ginibre-Mehta, Girko, Bai, Edelman, Gotze-Tykhomirov, Pan-Zhu etc) the conjecture remained open for more than 50 years.
This summer, with T. Tao we confirmed the conjecture in full generality. I am going to give an overview of this proof, which relies on rather surprising connections between various fields: combinatorics, probability, number theory and theoretical computer science. In particular, tools from additive combinatorics and Hardy-Littlewood circle method from analytic number theory play crucial roles.

Title: The Erdos-Heilbronn Problem for Finite Groups

Speaker: Jeffrey Wheeler

When: Thursday, October 30, 4:30-5:30

Where: Wean 5320

Abstract:

Speaker: Jeffrey Wheeler

When: Thursday, October 30, 4:30-5:30

Where: Wean 5320

Abstract:

The Erdos-Heilbronn Conjecture states that for any two nonempty
subsets A and B of Z/pZ we have |A \dot{+} B| \ge min(p, |A|+|B|-3), where A \dot{+} B is the set of
sums a+b mod p with a in A and b \in B and a \neq b. Dias
da Silva and Hamidounne established the result for the case A = B
in 1994, while Alon, Nathanson, and Ruzsa established the more
general result in 1995. We further generalize this result by
extending it from Z/pZ to arbitrary finite
(including non-abelian) groups.

Title: Domain Filtering Algorithms in Constraint Programming

Speaker: Willem-Jan van Hoeve

When: Thursday, November 6, 4:30-5:30

Where: Wean 5320

Abstract:

Speaker: Willem-Jan van Hoeve

When: Thursday, November 6, 4:30-5:30

Where: Wean 5320

Abstract:

In recent years, constraint programming has emerged as a powerful technology to model and solve combinatorial optimization
problems. It combines an expressive modeling language with powerful inference techniques and advanced search strategies.

One of the most important driving forces behind succesful commercial constraint programming solvers (such as ILOG CP Optimizer) are so-called domain filtering algorithms for global constraints. In this talk I will discuss domain filtering algorithms for several global constraints, including the (soft-)alldifferent constraint, the sequence constraint, and constraints over set variables.

Title: Pollard's Rho, Kangaroo and a Birthday Paradox

Speaker: Prasad Tetali, Georgia Institute of Technology

When: Thursday, November 13, 4:30-5:30

Where: Wean 5320

Abstract:

Speaker: Prasad Tetali, Georgia Institute of Technology

When: Thursday, November 13, 4:30-5:30

Where: Wean 5320

Abstract:

Motivated by the analysis of the Pollard Rho algorithm for
the discrete logarithm problem, we develop a birthday theorem regarding
self-intersections of Markov chains with uniform stationary distribution.
As an application we show that a collision occurs in \Theta(\sqrt{|G|})
steps of the Rho algorithm for finding the discrete log in a cyclic group G.
Time permitting, I will describe current work on extensions to the more
practically relevant Kangaroo algorithm.
This is based on joint papers with Jeong Han Kim, Ravi Montenegro,
and Yuval Peres.

Title: CUTOFF PHENOMENA FOR RANDOM WALKS ON RANDOM REGULAR GRAPHS

Speaker: Eyal Lubetzky, Microsoft Research

When: Thursday, November 20, 4:30-5:30

Where: Wean 5320

Abstract:

Speaker: Eyal Lubetzky, Microsoft Research

When: Thursday, November 20, 4:30-5:30

Where: Wean 5320

Abstract:

The cutoff phenomenon describes a sharp transition in the convergence of a family of ergodic finite Markov chains to equilibrium. Many
natural families of chains are conjectured to exhibit cutoff, yet establishing this fact is often extremely challenging. An important such
family of chains is the random walk on *G*(*n*,*d*), a random *d*-regular graph on *n* vertices. It is well known
that the spectral gap of this class of chains for *d* fixed is constant, implying a mixing-time of O(log *n*). According to a
conjecture of Peres, the simple random walk on *G*(*n*,*d*) for any fixed *d* should then exhibit cutoff *whp*. As a
special case of this, Durrett conjectured that the mixing time of the lazy random walk on a random 3-regular graph is *whp*
(6+o(1))log_{2} *n*.

In this work we confirm the above conjectures, and establish cutoff in total-variation, its location and its optimal window, both for simple
and for non-backtracking random walks on *G*(*n*,*d*). Namely, for any fixed *d*, the *simple* random walk on
*G*(*n*,*d*) *whp* has cutoff at [d/(d-2)]log_{d-1} *n* with window order sqrt{log *n*}.
Surprisingly, the *non-backtracking* random walk on *G*(*n*,*d*) *whp* has cutoff already at
log_{d-1} *n* with *constant* window order.

We further extend these results to *G*(*n*,*d*) for any *d*=*n*^{o(1)} (beyond which the mixing time is
O(1)), provide efficient algorithms for testing cutoff, as well as give explicit constructions where cutoff occurs.

Joint work with Allan Sly.

Title: The Power of Choice in a Generalized Polya Urn Model

Speaker: Gregory Sorkin (IBM Research, Yorktown Heights NY)

When: Tuessday, December 2, 4:30-5:30 (Note unusual place and time.)

Where: PPB 300

Abstract:

Speaker: Gregory Sorkin (IBM Research, Yorktown Heights NY)

When: Tuessday, December 2, 4:30-5:30 (Note unusual place and time.)

Where: PPB 300

Abstract:

We introduce a "Polya choice" urn model combining elements of the
well known "power of two choices" model and the "rich get richer"
model. From a set of $k$ urns, randomly choose $c$
distinct urns with probability proportional to the product of a power
$\gamma>0$ of their occupancies, and increment one with the smallest
occupancy. The model has an interesting phase transition. If
$\gamma \leq 1$, the urn occupancies are asymptotically equal with
probability 1. For $\gamma>1$, this still occurs with positive
probability, but there is also positive probability that some urns
get only finitely many balls while others get infinitely many.

Title: Counting matchings and independent sets of a fixed size

Speaker: David Galvin, University of Notre Dame

When: Thursday, December 4, 4:30-5:30

Where: Wean 5320

Abstract:

Speaker: David Galvin, University of Notre Dame

When: Thursday, December 4, 4:30-5:30

Where: Wean 5320

Abstract:

A matching in a graph is a collection of edges no two of which share
a vertex. An independent set is a collection of vertices no two of
which are spanned by an edge. Both matchings and independent sets
arise as configurations in well-studied studied statistical physics
models, namely the dimer model and the hard-core model. A theorem of
Bregman implies that among all $d$-regular, $N$-vertex bipartite
graphs, the one with the most matchings of size $N/2$ (the maximum
possible size) is the graph $K(N,d)$ composed of the disjoint union
of $N/2d$ complete $d$-regular bipartite graphs. Recently Friedland
has conjectured that among $d$-regular, $N$-vertex bipartite
graphs, $K(N,d)$ admits the most matchings of size $k$ for any $0
\leq k \leq N/2$. In this talk we report on work in progress using
methods from information theory to provide asymptotic evidence for
Friedland's conjecture, and its natural analog for independent sets.
Joint work with Teena Carroll (Norbert College) and Prasad Tetali
(Georgia Tech)

Title: Large induced trees in K_r-free graphs

Speaker: Po Shen Lo, Princeton University

When: Thursday, January 15, 4:30-5:30

Where: Wean 5302

Abstract:

Speaker: Po Shen Lo, Princeton University

When: Thursday, January 15, 4:30-5:30

Where: Wean 5302

Abstract:

For a graph G, let t(G) denote the maximum number of vertices in an
induced subgraph of G that is a tree. We study the problem of
bounding t(G) for graphs which do not contain a complete graph K_r on
r vertices. This problem was posed twenty years ago by Erdos, Saks,
and Sos. Substantially improving earlier results of various
researchers, we prove that every connected triangle-free graph on n
vertices contains an induced tree of order sqrt(n). When r > 3, we
also show that t(G) > (log n)/(4 log r) for every connected K_r-free
graph G of order n. Both of these bounds are tight up to small
multiplicative constants, and the first one disproves a recent
conjecture of Matousek and Samal.
Joint work with Jacob Fox and Benny Sudakov.

Title: A Generic Top-Down Dynamic-Programming
Approach to Prefix-Free
Coding

Speaker: Xiaoming Xu, Fudan University

When: Friday, January 16, 1:30-3:00 (note the unusual place and time)

Where: Cooper Auditorium, Posner Hall

Abstract:

Speaker: Xiaoming Xu, Fudan University

When: Friday, January 16, 1:30-3:00 (note the unusual place and time)

Where: Cooper Auditorium, Posner Hall

Abstract:

Given a probability distribution over a set of n words to be
transmitted, the Huffman Coding problem is to find a minimal-cost
prefix free code for transmitting those words. The basic Huffman
coding problem can be solved in O (n log n) time but variations are
more difficult. One of the standard techniques for solving these
variations utilizes a top-down dynamic programming approach. In this
paper we show that this approach is amenable to dynamic programming
speedup techniques, permitting a speedup of an order of magnitude for
many algorithms in the literature for such variations as mixed radix,
reserved length and one-ended coding. These speedups are immediate
implications of a general structural property that permits batching
together the calculation of many DP entries.

Title: Zed Yilma

Speaker: Maximizing Clique-free Edge 4-colorings

When: Thursday, January 29, 4:30-5:30

Where: Wean 5302

Abstract:

Speaker: Maximizing Clique-free Edge 4-colorings

When: Thursday, January 29, 4:30-5:30

Where: Wean 5302

Abstract:

For a graph G, let F(G,r,k) be the number of distinct r-colorings of
its edges which contain no monochromatic copy of a k-clique. A natural
question is to determine F(n,r,k), the maximum of F(G,r,k) taken over
all graphs of order n. A conjecture by Erdos and Rothschild that
$F(n,2,3) = 2^\lfloor n^2/4 \rfloor$ was proved by Yuster who further
conjectured that the k-1 partite Turan graph achieves the optima for
F(n,2,k) for all k. Alon, Balogh, Keevash and Sudakov confirmed this
while also showing it remains true for $r=3$. However, for r > 3, they
prove one can do significantly better. We show that the 4-partite and
9-partite Turan graphs are the unique graphs achieving the optima for
F(n,4,3) and F(n,4,4), respectively.

Title: Combinatorics of list decoding linear codes

Speaker: Venkatesan Guruswami, U. Washington & CMU

When: Thursday, February 5, 4:30-5:30

Where: Wean 5302

Abstract:

Speaker: Venkatesan Guruswami, U. Washington & CMU

When: Thursday, February 5, 4:30-5:30

Where: Wean 5302

Abstract:

We discuss some (not so recent) combinatorial results concerning the
asymptotic list decoding properties of *linear* codes. We will show
the best known existential bounds on the trade-off between
list-decodability and rate, which amounts to the following packing
question: What is the largest size of a subspace C of the hypercube
such that every Hamming ball of a certain radius contains at most L
vectors of C? We will also briefly discuss the relation to the code's
minimum distance: If every pair of vectors differ in at least a
fraction \delta of coordinates, what is the largest radius for which
every Hamming ball of that radius is *guaranteed* to have a small
(polynomially bounded) number of vectors in it?
The talk will be self-contained, and one of its principal objectives is to
present some basic (and approachable) open questions in this topic.

Title: Michael Krivelevich, Tel Aviv University

Speaker: Playing to retain the advantage

When: Thursday, February 12, 4:30-5:30

Where: Wean 5302

Abstract:

Speaker: Playing to retain the advantage

When: Thursday, February 12, 4:30-5:30

Where: Wean 5302

Abstract:

In 1998 Duffus, Luczak and Rodl posed the following question:
Is there an integer K such that for all graphs G with chromatic
number at least K, Maker has a strategy to choose an odd cycle in
the game, where Maker chooses one edge and Breaker two, in each
round?
(Actually, the DLR question was about the vertex claiming version of
the game, but the edge claiming version stated above is somewhat
more natural and at least equally interesting.)

The above problem is one (yet quite challenging!) example of a general setting of a two player biased game. The game is between Maker and Breaker, who take turns in claiming unoccupied edges of a graph G, the board of the game; Maker takes one edge at a time, while Breaker claims b>=1 edges. The graph G is assumed to be far from a monotone property P, in some well defined quantitative sense, and Maker wins iff by the end of the game his edges form a graph M that does not possess P.

In this talk I will discuss several problems and results of this sort. The aim of the talk is two-fold: to popularize the DLR problem and its relatives, and also to acquaint the audience with the circle of ideas and techniques surrounding this subject.

Joint work with Noga Alon (Tel Aviv) and Dan Hefetz (ETH Zurich).

Title: Negative correlation inequalities and log-concavity

Speaker: Mike Neiman, Rutgers

When: Thursday, March 19, 4:30-5:30

Where: Wean 5302

Abstract:

Speaker: Mike Neiman, Rutgers

When: Thursday, March 19, 4:30-5:30

Where: Wean 5302

Abstract:

Correlation inequalities are statements about how events in a
probability space positively or negatively reinforce each other. After
briefly discussing the better-understood theory of positive correlation, I
will talk about some negative correlation inequalities and a potential
relationship to celebrated conjectures of J. Mason about log-concavity
properties of certain sequences arising from graphs and matroids. Along
the way, I'll mention several interesting open problems.

Title: Compact Topological cliques in sparse graphs

Speaker: Tao Jiang, Miami University

When: Thursday, April 23, 4:30-5:30

Where: Wean 5302

Abstract:

Speaker: Tao Jiang, Miami University

When: Thursday, April 23, 4:30-5:30

Where: Wean 5302

Abstract:

Let $\epsilon$ be a positive number less than $1$.
Answering a question of Paul Erdos,
Kostochka and Pyber (1988) showed that for large $n$,
every $n$-vertex graph with at least $4^{t^2}n^{1+\epsilon}$
edges contains a subdivision of $K_t$ in which each edge
of $K_t$ is subdivided at most $c\log t/\epsilon$ times,
where $c$ is an absolute constant.
Here we prove a complementary (and in some sense stronger)
result by eliminating the dependency on $t$.
For each $t$ and sufficiently large $n$, we show that
every $n$-vertex graph with at least $a(t) n^{1+\epsilon}$ edges,
where $a(t)$ is a constant depending on $t$,
contains a subdivision of $K_t$ in which each edge of $K_t$
is subdivided at most $c\log (1/\epsilon)/\epsilon$ times,
where $c$ is an absolute constant. Note that the number of
times each edge is subdivided depends only on $\epsilon$
and does not depend on $t$.

PostScript Ghostview or GSview, Adobe Acrobat Reader, Sun StarOffice Impress or Microsoft PowerPoint Viewer.