Princeton Discrete Mathematics Seminar [Announcement: Feed no longer available after November 18th, 2015. See https://goo.gl/EMDRqe]

<a href="http://www.math.princeton.edu/~aovetsky/">Alexandra Fradkin</a> (Princeton): The k edge-disjoint paths problem in digraphs with bounded independence number

2009-09-23T18:08:01.000Z

When: Thu Dec 17, 2009 2:15pm to 3:15pm EST

Where: Fine 224
Event Status: confirmed
Event Description: In 1980, Fortune, Hopcroft, and Wyllie showed that the following algorithmic problem (k-EDP) is NP-complete with k=2:

k Edge-Disjoint Paths (k-EDP)

Instance: A digraph G, and k pairs (s₁,t₁),...,(s_k,t_k) of vertices of G.

Question: Do there exist directed paths P₁,...,P_k of G, mutually edge-disjoint, such that P_i is from s_i to t_i for i=1,...,k?

In this talk we will present a polynomial time algorithm to solve k-EDP for fixed k in digraphs with independence number at most 2. We will also talk about progress made towards solving k-EDP in digraphs with independence number at most alpha, for fixed alpha. This is joint work with Paul Seymour.

<a href="http://dimacs.rutgers.edu/People/Postdocs/Kun.html">Gabor Kun</a> (IAS): Proof of the Bollobas-Catlin-Eldridge conjecture

2009-11-17T22:37:40.000Z

When: Thu Dec 10, 2009 2:15pm to 3:15pm EST

Where: Fine 224
Event Status: confirmed
Event Description: We say that two graphs G and H pack if G and H can be embedded into the same vertex set such that the images of the edge sets do not overlap. Bollobas and Eldridge, and independently Catlin conjectured that if the graphs G and H on n vertices with maximum degree M(G) and M(H), respectively, satisfy (M(G) + 1)(M(H) + 1) ≤ n + 1 then G and H pack.

Aigner and Brandt and, independently, Alon and Fischer proved this in the case M(G),M(H) < 3, Csaba, Shokoufandeh and Szemeredi proved the conjecture if M(G),M(H) < 4. Bollobas, Kostochka and Nakprasit settled the case when one of the graphs is degenerate. Kaul, Kostochka and Yu showed that if M(G)M(H) < 3/5n and the maximal degrees are large enough then G and H pack. We prove the conjecture for graphs with at least 10^8 vertices.

<a href="http://www.columbia.edu/~mc2775/">Maria Chudnovsky</a> (Columbia): A splitter theorem for induced subgraphs

2009-09-15T21:40:25.000Z

When: Wed Dec 2, 2009 2:15pm to 3:15pm EST

Who: Princeton Discrete Mathematics Seminar
Where: Fine 110
Event Status: confirmed
Event Description: A homogeneous set in a graph G is a subset X of V(G), such that no vertex of V(G)\X has both a neighbor and a non-neighbor in X. Let us say that a graph is prime if it has no homogeneous set X with 1<|X|<|V(G)|.

Seymour's well-known splitter theorem states that if G and H are 3-connected graphs, G is not a wheel, H is not the complete graph on four vertices, and H is a minor of G, then G can be built from H by undeleting or uncontracting one edge at a time, and so that all the graphs constructed along the way are 3-connected. We prove a similar result for the induced subgraph containment relation, replacing 3-connected with prime, undeleting and uncontracting with adding a vertex, and wheels with a certain family of bipartite graphs that we call B. We prove that if G and H are prime graphs, G is not in B, and H is an induced subgraph of G, then G can be built from H, adding one vertex at a time, and so that all the graphs constructed along the way are prime.

We then use this result to prove that every n-vertex prime claw-free graph has at most n+1 simplicial cliques (a clique C of G is simplicial if for every vertex c of C, the set of neighbors of c outside of C is a clique). This allows us to test in polynomial time if a claw-free graph has a simplicial clique, answering a question of Prasad Tetali.

This is joint work with Paul Seymour.

<a href="http://math.dartmouth.edu/~pw/">Peter Winkler</a> (Dartmouth): Scheduling, Percolation, and the Worm Order

2009-09-15T20:45:34.000Z

When: Thu Nov 19, 2009 2:15pm to 3:15pm EST

Where: Fine 224
Event Status: confirmed
Event Description: We show that in any submodular system there is a maximal chain that is minimal, in a very strong sense, among all paths from 0 to 1. The consequence is a set of general conditions under which parallel scheduling can be done without backward steps.

Among the applications are a fast algorithm for scheduling multiple processes without overusing a resource; a theorem about searching for a lost child in a forest; and a closed-form expression for the probability of escaping from the origin in a form of coordinate percolation.

Joint work in part with Graham Brightwell (LSE) and in part with Lizz Moseman (USMA).

<a href="http://www.columbia.edu/~ak3074/">Andrew King</a> (Columbia): Fractional total colourings of graphs of high girth

2009-09-10T19:59:38.000Z

When: Thu Nov 12, 2009 2:15pm to 3:15pm EST

Where: Fine 224
Event Status: confirmed
Event Description: The total graph T(G) has vertex set V(G) union E(G), in which two vertices of T(G) are adjacent precisely if they arise from (i) two adjacent vertices of G, (ii) two incident edges of G, or (iii) an edge of G and one of its endpoints. The (fractional) total chromatic number of G is the (fractional) chromatic number of T(G).

It is known that the fractional total chromatic number is between Delta+1 and Delta+2, where Delta is the maximum degree. Reed recently announced a conjecture that the fractional total chromatic number approaches Delta+1 as the girth of a graph increases (for fixed Delta); this would be yet another similarity between total colourings and edge colourings. We prove this conjecture using the approach of l-path decompositions and a randomized method for choosing total stable sets of G.

This is joint work with Tomas Kaiser and Dan Kral.

<a href="http://www.juliawolf.org/">Julia Wolf</a> (Rutgers): The minimum number of monochromatic 4-term progressions

2009-09-10T19:56:18.000Z

When: Thu Oct 29, 2009 2:15pm to 3:15pm EDT

Where: Fine 224
Event Status: confirmed
Event Description: It is not difficult to see that whenever you 2-color the elements of Z/pZ, the number of monochromatic 3-term arithmetic progressions depends only on the density of the color classes. The analogous statement for 4-term progressions is false. We shall analyse the reasons for this, and subsequently derive bounds on the minimum number of monochromatic 4-term arithmetic progressions in any 2-coloring of Z/pZ. In the process we touch upon the subject of quadratic Fourier analysis as well as a closely related question in graph theory studied by Thomason et al.: What is the minimum number of monochromatic K₄s in any 2-coloring of K_n?

<a href="http://people.cs.uchicago.edu/~wes/index.html">Wesley Pegden</a> (Rutgers): Applying a Local Lemma to Thue games

2009-09-16T15:09:25.000Z

When: Thu Oct 22, 2009 2:15pm to 3:15pm EDT

Where: Fine 224
Event Status: confirmed
Event Description: In this talk, I will discuss probabilistic proofs for the existence of winning strategies in sequence games where the goal is nonrepetitiveness. The technique involves a `one-sided' generalization of the Local Lemma, which allows us to ignore the dependencies on `future' events which would normally prevent this kind of proof from working. I will also discuss the extension of these results to graphs. Although many proofs about games are motivated by a probabilistic intuition, these results appear to represent the first successful applications of a Local Lemma to games.

<a href="http://www.sfu.ca/~mdevos/">Matt DeVos</a> (Simon Fraser): On the Schrijver-Seymour Conjecture

2009-09-23T18:06:12.000Z

When: Thu Oct 15, 2009 2:15pm to 3:15pm EDT

Where: Fine 224
Event Status: confirmed
Event Description: Two interesting classical results in combinatorial number theory are the Erdos-Ginzburg-Ziv Theorem and the Furedi-Kleitman Theorem. Fixing an abelian group G of order n, the former asserts that every sequence of 2n+1 elements of G has a length n subsequence which sums to 0, while the latter asserts that every edge-weighting of a complete graph of order n+1 with elements of G has a spanning tree of weight 0. Schrijver and Seymour established a fascinating common generalization of these problems by considering a matroid M with a weighting w:E(M)->G. In this framework, they conjectured a natural lower bound on the number of distinct weights of bases. In addition to generalizing the above results, their conjecture (if true) would generalize Kneser's addition theorem for abelian groups.
Schrijver and Seymour proved their conjecture in the special case when G has prime order, a result which implies the Erdos-Ginzburg-Ziv Theorem, among its numerous consequences. In this talk, I will discuss a proof of the Schrijver-Seymour conjecture in the special case when M is a matroid obtained from a uniform matroid by adding parallel elements. As I will detail, this result has numerous consequences for subsequence sums including two conjectures of Gao, Thangadurai, and Zhuang. This is joint work with B. Mohar and L. Goddyn.

<a href="http://www.cs.toronto.edu/~hamed/">Hamed Hatami</a> (Princeton): Graph norms and Erdos-Simonovits-Sidorenko's conjecture

2009-09-26T18:38:16.000Z

When: Thu Oct 8, 2009 2:15pm to 3:15pm EDT

Where: Fine 224
Event Status: confirmed
Event Description: I will prove some results in the direction of answering a question of Lovasz about the norms defined by certain combinatorial structures. Inspired by the similarity of the definitions of L_p norms, trace norms, and Gowers norms, we introduce and study a wide class of norms containing these, as well as many other norms. It will be proven that every norm in this class must satisfy a Cauchy-Schwarz-Gowers type inequality. I will show an application of this inequality to a conjecture of Erdos-Simonovits and Sidorenko about subgraph densities.

<a href="http://www.columbia.edu/~yz2198/"> Yori Zwols</a> (Columbia): Claw-free graphs with strongly perfect complements. Fractional and integral version.

2009-09-17T01:04:47.000Z

When: Thu Oct 1, 2009 2:15pm to 3:15pm EDT

Where: Fine 224
Event Status: confirmed
Event Description: Strongly perfect graphs have been studied by several authors (e.g. Berge, Duchet, Ravindra, Wang). This paper deals with a fractional relaxation of strong perfection. Motivated by a wireless networking problem, we consider claw-free graphs that are fractionally strongly perfect in the complement. We obtain a forbidden induced subgraph characterization and display graph-theoretic properties of such graphs. It turns out that the forbidden induced subgraphs that characterize claw-free fractionally co-strongly perfect graphs are precisely the cycle of length 6, all cycles of length 8 and longer, four particular graphs, and a collection of graphs that are constructed by taking two graphs, each a copy of one of three particular graphs, and joining them by a path of arbitrary length in a certain way. Wang gave a characterization of strongly perfect claw-free graphs. As a corollary of the results in this paper, we obtain a characterization of claw-free graphs whose complements are strongly perfect.

<a href="www.math.princeton.edu/~snorin">Sergey Norin</a> (Princeton): Counting flags in digraphs

2009-09-15T19:33:09.000Z

When: Thu Sep 24, 2009 2:15pm to 3:15pm EDT

Where: Fine 224
Event Status: confirmed
Event Description: Many results in asymptotic extremal combinatorics are obtained using just a handful of instruments, such as induction and Cauchy-Schwarz inequality. The ingenuity lies in combining these tools in just the right way. Recently, Razborov developed a flag calculus which captures many of the available techniques in pure form, and allows one, in particular, to computerize the search for the right combination.

In this talk we outline the general approach and describe its application to two problems in extremal digraph theory. We show that an n vertex digraph with minimum outdegree 0.3465n contains a directed triangle, obtaining a new bound in an important special case of the Caccetta-Haggkvist conjecture. We also show that the maximum number of induced directed two-edge paths in an n vertex digraph is n³/15 + o(n³), resolving a conjecture of Thomasse.

Based on joint work with Jan Hladky and Daniel Kral.

<a href="http://www.columbia.edu/~mc2775/">Maria Chudnovsky</a> (Columbia): Packing seagulls in graphs with no stable set of size three.

2009-02-18T17:17:48.000Z

When: Thu Apr 23, 2009 3:30pm to 4:30pm EDT

Event Status: confirmed
Event Description: Hadwiger's conjecture is a well known open problem in graph theory. It states that every graph with chromatic number k, contains a certain structure, called a "clique minor" of size k. An interesting special case of the conjecture, that is still wide open, is when the graph G does not contain three pairwise non-adjacent vertices. In this case, it should be true that G contains a clique minor of size t where t >= |V(G)|/2. This remains open, but Jonah Blasiak proved it in the subcase when |V(G)| is even and the vertex set of G is the union of three cliques. Here we prove a strengthening of Blasiak's result: that the conjecture holds if some clique in G contains at least |V(G)|/4 vertices. This is a consequence of a result about packing ``seagulls''. A seagull in G is an induced three-vertex path. It is not known in general how to decide in polynomial time whether a graph contains k pairwise disjoint seagulls; but we answer this for graphs with no stable sets of size three. This is joint work with Paul Seymour.

<a href="http://www.math.princeton.edu/~bbukh/">Boris Bukh</a> (Princeton and UCLA): Geometric selection theorems

2009-01-26T02:10:27.000Z

When: Thu Apr 16, 2009 2:15pm to 3:15pm EDT

Where: Fine 224
Event Status: confirmed
Event Description: In combinatorial geometry one frequently wants to select a point or a set of points that meets many simplices of a given family. The two examples are choosing a point in many simplices spanned by points of some P in R^d, and choosing a small set of points which meets the convex hull of every large subset of P (the weak epsilon-net problem). I will present a new class of constructions that yield the first nontrivial lower bound on the weak epsilon-net problem, and improve the best bounds for several other selection problems. Joint work with Jiří Matoušek and Gabriel Nivasch.

<a href="http://www2.isye.gatech.edu/~wcook/">William Cook</a> (Georgia Tech): Linear Programming Relaxations for the TSP

2009-02-18T17:19:17.000Z

When: Thu Apr 9, 2009 2:15pm to 3:15pm EDT

Where: Fine 224
Event Status: confirmed
Event Description: The most successful solution approaches to the traveling salesman problem are based on lower bounds obtained from linear programming relaxations. We will discuss a number of open problems concerning this approach, with emphasis on topics that could improve the practical performance of LP-based algorithms.

Jeff Kahn (Rutgers): The number of 3-SAT functions

2009-03-05T16:25:49.000Z

When: Fri Apr 3, 2009 2:15pm to 3:15pm EDT

Where: Fine 322
Event Status: confirmed
Event Description: We are interested in the number, say G(k,n), of k-SAT functions of n variables (a k-SAT function being a Boolean function representable by a k-SAT formula in, say, conjunctive normal form). We show that G(3,n) is asymptotic to 2^{n + {n \choose 3}}, a strong form of a conjecture of Bollobas, Brightwell and Leader. (The corresponding result for 2-SAT was conjectured by BB&L, and proved by Peter Allen and (independently but later) by the present authors. As usual, the case k=2 doesn't seem to shed much light on larger k, while one expects/hopes that k=3 is about as hard to handle as a general fixed k.) Joint with Liviu Ilinca

<a href="http://www.princeton.edu/~ploh/">Po-Shen Loh</a> (Princeton and UCLA): Avoiding small subgraphs in Achlioptas processes

2009-01-21T22:48:42.000Z

When: Thu Mar 26, 2009 2:15pm to 3:15pm EDT

Where: Fine 224
Event Status: confirmed
Event Description: Consider the following random process. At each round, one is presented with two random edges from the edge set of the complete graph on n vertices, and is asked to choose one of them. The selected edges are collected into a graph, which thus grows at the rate of one edge per round. This is known in the literature as an Achlioptas process, and has been studied by many researchers, mainly in the context of delaying or accelerating the appearance of the giant component. In our work, we investigate the classical small subgraph problem for Achlioptas processes. That is, given a fixed graph H, we study whether there is a deterministic online algorithm that substantially delays or accelerates a typical appearance of H, compared to its threshold of appearance in the random graph G(n,M). It is easy to see that one cannot accelerate the appearance of any fixed graph by more than a factor of 2, so we concentrate on the task of avoiding H. We determine thresholds for the avoidance of all cycles C_t, cliques K_t, and complete bipartite graphs K_{t,t}. Joint work with Michael Krivelevich and Benny Sudakov.

<a href="http://www.math.rutgers.edu/~vanvu/">Van Vu</a> (Rutgers): Inverse Littlewood-Offord theory, Smooth Analysis and the Circular Law

2009-01-29T14:57:55.000Z

When: Thu Mar 12, 2009 2:15pm to 3:15pm EDT

Where: Fine 224
Event Status: confirmed
Event Description: A corner stone 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. Last year, T. Tao and I 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, ideas from ADDITIVE COMBINATORICS play crucial roles.

<a href="http://www.math.ias.edu/~dvir/">Zeev Dvir</a> (IAS): New bounds on the size of Kakeya sets in finite fields.

2009-01-26T01:08:46.000Z

When: Thu Mar 5, 2009 2:15pm to 3:15pm EST

Where: Fine 224
Event Status: confirmed
Event Description: A Kakeya set is a set in (F_q)^n (the n dimensional vector space over a field of q elements) which contains a line in every direction. In this talk I will present a recent result which gives a lower bound of (q/2)^n on the size of such sets. This bound is tight to within a multiplicative factor of two from the known upper bounds. The proof extends the polynomial method used in [Dvir 08, Saraf Sudan 08] and uses polynomials of unbounded degree. If time allows I will also discuss the applications to the explicit construction of mergers that follow from our techniques. Joint work with Kopparty, Saraf and Sudan (arxiv paper: "Extensions to the Method of Multiplicities, with applications to Kakeya Sets and Mergers").

<a href="www.cs.nyu.edu/spencer/">Joel Spencer</a> (Courant Institute, NYU): Finding Lovasz's Needle in an Exponential Haystack

2009-01-26T01:05:56.000Z

When: Thu Feb 26, 2009 2:15pm to 3:15pm EST

Where: Fine 224
Event Status: confirmed
Event Description: The Lovasz Local Lemma is a subtle and far-reaching probability lemma. Roughly, given a large number of bad events which are "mostly" independent it sieves out an instance when none of the bad events occur. As an illustrative example, consider a huge family of 10-element sets, where each set overlaps at most 100 others. We color randomly red and blue and for each set e there is a bad event that e is monochromatic. The conclusion is the existence of a coloring where none of the e are monochromatic. In theory. But if there are n sets a random coloring only has exponentially small chance of succeeding. Finding a polynomial time algorithmic implementation has proven elusive. There were some results of Jozsef Beck and Noga Alon in the early 1990s but they had limited application. Very recently Robin Moser (ETH) has made a breakthrough, giving an amazingly simple probabilistic algorithm to find the coloring and a not quite so simple proof that the algorithm indeed works. We shall rephrase Moser's argument and give the entire argument.

<a href="http://www.math.ias.edu/~avi/">Avi Wigderson</a> (IAS): Randomness extractors - applications and constructions

2009-01-26T03:37:13.000Z

When: Thu Feb 19, 2009 2:15pm to 3:15pm EST

Where: Fine 224
Event Status: confirmed
Event Description: We will investigate the minimal requirements from a random source under which it is potentially useful for generating perfect randomness. The efficient procedures which utilize such sources, "randomness extractors", turn out to have amazing pseudorandomness properties and are useful in numerous contexts. We'll demonstrate applications in complexity theory, error correction and network design. We'll also describe some constructions of near optimal extractors, with tools from expander graphs and the recent proof of the Kakeya conjecture in finite fields.

<a href="http://kam.mff.cuni.cz/~hladky/">Jan Hladky</a> (Charles University & TU. Munich): Square-paths and square-cycles in graphs with high minimum degree

2009-02-09T14:30:47.000Z

When: Thu Feb 12, 2009 2:15pm to 3:15pm EST

Where: Fine 224
Event Status: confirmed
Event Description: We investigate under which minimum-degree condition does a graph G contain a square-path and a square-cycle of a given length. We give precise thresholds, assuming that the order of G is large. This extends results of Fan and Kierstead [J. Combin. Theory Ser. B, 67(2), 167-182, 1996] and of Komlos, Sarkozy, and Szemeredi [Random Structures Algorithms, 9(1-2), 193-211, 1996] concerning containment of a spanning square-path and a spanning square-cycle, respectively. Joint work with P. Allen and J. Bottcher.

<a href="http://www.math.rutgers.edu/~hoi/">Hoi Nguyen</a> (Rutgers): On simple additive configurations in random sets

2009-01-29T14:55:52.000Z

When: Thu Feb 5, 2009 2:15pm to 3:15pm EST

Where: Fine 224
Event Status: confirmed
Event Description: We show that with high probability a random subset of [n] of size \theta(n^{1-1/k}) contains two elements a and a+d^k, where d is a positive integer. As a consequence, we prove an analogue of the Sarkozy-Furstenberg theorem for a random subset of [n].

<a href="http://www.math.uni-hamburg.de/home/wollan/">Paul Wollan</a> (University of Hamburg): Packing cycles with modularity constraints

2008-11-05T15:42:51.000Z

When: Thu Dec 11, 2008 2:15pm to 3:15pm EST

Where: Fine 224
Event Status: confirmed
Event Description: Erdős and Posa proved that a there exists a function $f$ such that any graph either has $k$ disjoint cycles or there exists a set of $f(k)$ vertices that intersects every cycle. The analogous statement is not true for odd cycles - there exist numerous examples of graphs that do not have two disjoint odd cycles, and yet no bounded number of vertices intersects every odd cycle. However, Reed has given a partial characterization of when there does not exist a bounded size set of vertices intersecting every odd cycle. We will discuss recent work on when a graph has many disjoint cycles of non-zero length modulo $m$ for arbitrary $m$. When $m$ is odd, we see that again there exists a function $f$ such that any graph either has $k$ disjoint cycles of non-zero length modulo $m$ or there exists a set of at most $f(k)$ vertices intersecting every such cycle of non-zero length. When $m$ is even, no such function $f(k)$ exists. However, the partial characterization of Reed can be extended to describe when a graph has neither many disjoint cycles of non-zero length modulo $m$ nor a small set of vertices intersecting every such cycle.

<a href="http://www.math.gatech.edu/~thomas">Robin Thomas</a> (Georgia Tech): Coloring triangle-free graphs on surfaces

2008-11-11T15:52:35.000Z

When: Wed Dec 3, 2008 2:15pm to 3:15pm EST

Where: Fine 224
Event Status: confirmed
Event Description: Let S be a fixed surface, and let k and q be fixed integers. Is there a polynomial-time algorithm that decides whether an input graph of girth at least q drawn in S is k-colorable? This question has been studied extensively during the last 15 years. We will briefly survey known results. Then we will describe a solution to one of the two cases left open (the prospects for the other one are not bright). For every surface S we give a polynomial-time algorithm that computes the chromatic number of an input triangle-free graph G drawn in S. The new contribution here is deciding whether G is 3-colorable, and has two main ingredients. The first is a coloring extension theorem that makes use of disjoint paths in order to construct a coloring. The notion of "winding number" of a 3-coloring plays an important role. The second ingredient is a theorem bounding the number and sizes of faces of size at least four in 4-critical triangle-free graphs on a fixed surface, a generalization of a theorem of Thomassen. By developing more structure theory and using the notion of bounded expansion of Nesetril and Ossona de Mendez we were able to implement the algorithm to run in linear time. This is joint work with Zdenek Dvorak and Daniel Kral.

<a href="http://comet.lehman.cuny.edu/nathanson/">Melvyn Nathanson</a> (CUNY): Quasi-isometries, phase transitions, and other problems in additive number theory

2008-11-05T15:41:28.000Z

When: Fri Nov 21, 2008 2:15pm to 3:15pm EST

Where: Fine 1201
Event Status: confirmed
Event Description: This is a survey of recent work in combinatorial and additive number theory suggested by a problem of Richard Schwartz in metric geometry and geometric group theory. The central object is a group with an infinite set of generators, and the induced metric. Some results and many open problems will be discussed.