Seminars & Events for Discrete Mathematics Seminar

September 24, 2009
2:30pm - 4:30pm
Counting flags in digraph

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.

Speaker: Sergey Norin, Princeton University
Location:
Fine Hall 224
October 1, 2009
2:30pm - 4:30pm
Claw-free graphs with strongly perfect complements. Fractional and integral version

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.

Speaker: Yori Zwols, Columbia University
Location:
Fine Hall 224
October 8, 2009
2:30pm - 4:30pm
Graph norms and Erdos-Simonovits-Sidorenko's conjecture

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.

Speaker: Hamed Hatami, Princeton University
Location:
Fine Hall 224
October 15, 2009
2:00pm - 4:30pm
On the Schrijver-Seymour Conjecture

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.

Speaker: Matt DeVos, Simon Fraser University
Location:
Fine Hall 224
October 22, 2009
2:00pm - 4:30pm
Applying a Local Lemma to Thue games

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.

Speaker: Wesley Pegden, Rutgers University
Location:
Fine Hall 224
October 29, 2009
2:00pm - 4:30pm
The minimum number of monochromatic 4-term progressions

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_4$s in any 2-coloring of $K_n$?

Speaker: Julia Wolf, Rutgers University
Location:
Fine Hall 224
November 12, 2009
2:00pm - 4:30pm
Fractional total colourings of graphs of high girth

The total graph $T(G)$ has vertex set $V(G) \cup 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$.

Speaker: Andrew King, Columbia University
Location:
Fine Hall 224
November 19, 2009
2:00pm - 4:30pm
Scheduling, Percolation, and the Worm Order

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).

Speaker: Peter Winkler, Darthmouth College
Location:
Fine Hall 224
December 2, 2009
2:30pm - 4:30pm
A splitter theorem for induced subgraphs

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)|$.

Speaker: Maria Chudnovsky, Columbia University
Location:
Fine Hall 110
December 10, 2009
2:30pm - 4:30pm
Proof of the Bollobas-Catlin-Eldridge conjecture

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.

Speaker: Gabor Kun, IAS
Location:
Fine Hall 224
December 17, 2009
2:00pm - 4:30pm
The k edge-disjoint paths problem in digraphs with bounded independence number

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_1,t_1),...,(s_k,t_k)$ of vertices of $G$.

Question: Do there exist directed paths $P_1,...,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.

Speaker: Alexandra Ovetsky Fradkin, Princeton University
Location:
Fine Hall 224
February 11, 2010
2:30pm - 4:30pm
Graph/Group Random Elements and Applications to Group-Based Cryptanalysis

We introduce the notion of the mean-set (expectation) of a graph-(group-) valued random element $\xi$, generalize the strong law of large numbers to graphs and groups, and consider analogues of Chebyshev and Chernoff type bounds. In addition, we discuss several results about configurations of mean-sets in graphs and reflect on an algorithm for computing sample mean-sets. Finally, we show that our new theoretical tools provide a framework for practical applications; in particular, they have implications for cryptanalysis of group-based authentication protocols. In this talk, we will, among other things, look at the idea of such analysis for a certain existing identification protocol, using our results, and conclude that this protocol is not, in fact, secure. Results of actual experiments supporting our conclusions will be provided.

Speaker: Natalia Mosina, The City University of New York, LaGuardia
Location:
Fine Hall 224
February 18, 2010
2:15pm - 4:15pm
Friedgut's theorem for the continuous cube

A celebrated theorem of Friedgut says that every boolean function on the discrete cube can be approximated by a function which depends only on a number of variables that depends on the sum of the influences of the variables of f. Dinur and Friedgut conjectured an analogue of this theorem for the continuous cube. I disprove their conjecture, and then prove the correct version of Friedgut's theorem for the continuous cube.

Speaker: Hamed Hatami, Princeton University
Location:
Fine Hall 224
March 4, 2010
2:00pm - 4:30pm
Algorithmic metatheorems for sparse classes of combinatorial structures

A classic result of Courcelle asserts that every monadic second order logic (MSOL) formula can be decided in linear time for graphs with bounded tree-width. This result unified most of algorithmic results for graphs with bounded tree-width and was followed by many results of the same favor.

Speaker: Daniel Kral, Charles University, Prague
Location:
Fine Hall 224
March 11, 2010
2:30pm - 4:30pm
Tree packing conjectures; Graceful tree labeling conjecture

A family of graphs $H_1,...,H_k$ packs into a graph $G$ if there exist pairwise edge-disjoint copies of $H_1,...,H_k$ in $G$. Gyarfas and Lehel conjectured that any family $T_1, ..., T_n$ of trees of respective orders $1, ..., n$ packs into $K_n$. A similar conjecture of Ringel asserts that $2n$ copies of any trees $T$ on $n+1$ vertices pack into $K_{2n+1}$.

Speaker: Jan Hladky, University of Warwick
Location:
Fine Hall 224
March 25, 2010
2:30pm - 4:30pm
Geometry of the restricted Boltzmann machine

The restricted Boltzmann machine is a graphical model for binary random variables. Based on a complete bipartite graph separating hidden and observed variables, it is the binary analog to the factor analysis model. We study this graphical model from the perspectives of algebraic statistics and tropical geometry, starting with the observation that its Zariski closure is a Hadamard power of the first secant variety of the Segre variety of projective lines. We derive a dimension formula for the tropicalized model, and we use it to show that the restricted Boltzmann machine is identifiable in many cases. Our methods include coding theory and geometry of linear threshold functions.

Speaker: Jason Morton, Pennsylvania State University
Location:
Fine Hall 224
April 2, 2010
4:00pm - 6:00pm
Overlap properties of geometric expanders

If $G=(V,E)$ is an expander graph then for every embedding $f:V\to R$ that is extended linearly from the vertices $G$ to its edges, there must be a point $p\in R$ such that the pre-image $f^{-1}(p)$ has cardinality at least a constant multiple of the total number of edges $|E|$ (just take $p$ to be the median of $f(V)$). This property of expanders motivated Gromov to define a higher dimensional version of expansion: say that a d-dimensional simplicial complex $S$ is "expander like" if for every embedding $f:S\to R^d$ that is extended affinely from the vertices of $S$ to its d-faces, there must be a point $p\in R^d$ such that the cardinality of $f^{-1}(p)$ is at least a constant multiple of the total number of d-faces of $S$.

Speaker: Assaf Naor, Courant Institute, NYU
Location:
Fine Hall 224
April 8, 2010
2:30pm - 4:30pm
Spectral Algorithms for Unique Games

Khot's Unique Games Conjecture (UGC) is one of the most central open problems in computational complexity theory. UGC asserts that for a certain constraint satisfaction problem, it is NP-hard to decide whether there is a labeling that satisfies almost all the constraints or, for every labeling, the fraction of the constraints satisfied is very small. Since its origin, the UGC has been applied with remarkable success to prove tight hardness of approximation results for several important NP-hard problems such as Vertex Cover, MAXCUT.

Speaker: Alexandra Kolla, IAS
Location:
Fine Hall 224
April 14, 2010
2:30pm - 4:30pm
Eigenvalues, connectivity and matchings in regular graphs

The spectrum of a graph contains a lot of relevant information regarding its structure. In this talk, I will describe some relationships between the eigenvalues of a regular graph, its matching number and connectivity.

Speaker: Sebastian Cioaba, University of Delaware
Location:
Fine Hall 224
April 22, 2010
2:30pm - 4:30pm
The circumference of color-critical graphs

A graph is k-critical if every proper subgraph is (k-1)-colorable, but the graph itself is not. We prove that every k-critical graph on n vertices has a cycle of length at least log n/(100 log k). Examples show the bound cannot be improved to exceed 2(k-1)log n/log(k-2). This is joint work with A. Shapira.

Speaker: Robin Thomas, Georgia Institute of Technology
Location:
Fine Hall 224

Pages