The ACO Seminar (2007-2008)

We present some results on packing graphs in dense multipartite graphs. This is a question very similar to the Hajnal-Szemer\'edi theorem, which gives sufficient minimum-degree conditions for an $n$-vertex graph to have a subgraph consisting of $\lfloor n/r\rfloor$ vertex-disjoint copies of $K_r$. This is a packing, or tiling, of the graph by copies of $K_r$. The Hajnal-Szemer\'edi theorem has been generalized to finding minimum-degree conditions that guarantee packings of non-complete graphs, notably by Alon and Yuster and by K\"uhn and Osthus. We consider a multipartite version of this problem. That is, given an $r$-partite graph with $N$ vertices in each partition, what is the minimum-degree required of the bipartite graph induced by each pair of color-classes so that the graph contains $N$ vertex-disjoint copies of $K_r$? The question has been answered for $r=3,4$, provided $r$ is sufficiently large. When $r=3$ and $N$ is sufficiently large, a degree condition of $(2/3)N$ is sufficient with the exception of a single tripartite graph when $N$ is an odd multiple of $3$. When $r=4$ and $N$ is sufficiently large, a degree condition of $(3/4)N$ is sufficient and there is no exceptional graph. There are also bounds on the degree condition for higher $r$ by Csaba and Mydlarz. This question has also been generalized to finding minimum-degree conditions for packings of some arbitrary $r$-colorable graph in an $r$-partite. The case $r=2$ is highly nontrivial for packing arbitrary bipartite graphs and was answered very precisely by Zhao. The case $r=3$ is even more complex and we provide some tight bounds on the required degree condition. This talk includes joint work with Cs. Magyar, with E. Szemer\'edi and with Y. Zhao.

We address a question in graphs called the stable paths problem, which is an abstraction of a network routing problem concerning the Border Gateway Protocol (BGP). The main tool we use is Scarf's Lemma. This talk will describe Scarf's Lemma and how it is related to other results more familiar to combinatorialists, and then will explain its implications for the stable paths problem.

Our focus in this talk will be the size of linear programming formulations of combinatorial optimization problems. We may view this parameter as akin to traditional measures of complexity, such as computational time and space. We will focus on problems in P, in particular the minimum cut problem. For a graph $(V,E)$, existing linear formulations for the minimum cut problem require $\Theta(|V||E|)$ variables and constraints. These formulations can be interpreted as a composition of $|V|-1$ polyhedra for minimum $s$-$t$ cuts paralleling early algorithmic approaches to finding globally minimum cuts, which relied on $|V|-1$ calls to a minimum $s$-$t$ cut algorithm. We present the first formulation to beat this bound, one that uses $O(|V|^2)$ variables and $O(|V|^3)$ constraints. Our formulation directly implies a smaller compact linear relaxation for the Traveling Salesman Problem that is equivalent in strength to the standard subtour relaxation.

In 1970, Folkman proved that for a given integer r and a graph G of order n there exists a graph H with the same clique number as G such that every r coloring of vertices of H yields at least one monochromatic copy of G. His proof gives no good bound on the order of graph H, i.e., the order of H is bounded by an iterated power function of n. In this talk we will give an alternative proof of Folkman's theorem with the relatively small order of H bounded from above by O(n^3\log^3 n). This is joint work with Vojtech Rodl.

In 2004 Lovasz and Szegedy introduced "graph limits" as follows: "If a sequence of dense graphs G_n has the property that for every fixed F the number of copies of F in G_n tends to a limit, it is possible to define a limit object, namely a symmetric measurable function W:[0,1]2 --> [0,1] called a graphon." In a 2007 paper, Borgs, Chayes, Lovasz, Sos, and Vesztergombi proved that the space of graphons has a number of nice properties. The main work involved showing that if two graphons are close in the so-called cut norm then their subgraph densities are close, and vice-versa. In the talk we define a corresponding limit object for directed graphs and show that some analogous theorems hold for these objects.

We will discuss two results in discrete differential geometry: 1) A combinatorial 3-manifold with edges of degree at most five has edge-diameter at most five. 2) Suppose such a combinatorial 3-manifold $M$ has vertices $v$ and $w$ at the maximum edge-distance. Then, $M$ is a 3-sphere whose triangulation is completely determined by the star of $v$. These theorems are analogous to two important results in the differential geometry of positively curved spaces. The first is analogous to the Bonnet-Myers theorem, which bounds the diameter of Riemannian manifolds whose Ricci curvature is everywhere greater than a fixed positive constant. The second result is a discrete version of the Toponogov-Cheng rigid-sphere theorem, which shows that the maximum diameter allowed by the Bonnet-Myers theorem is achieved only for the standard sphere. The proofs we present are entirely combinatorial in nature, use only elementary arguments, and follow closely the proofs of the corresponding classical results. We will also talk about some enumeration algorithms which can be used to investigate the geometry of combinatorial manifolds. This talk is based on my Ph.D. thesis, which was done at Rice University under the direction of Robin Forman.

When solving Mixed Integer Linear Programs (MILP) with branch-and-cut algorithms a variety of cuts can be generated. The best known cuts are probably Gomory mixed integer cuts, obtained from a single row of the optimal simplex tableau for the linear relaxation of the MILP. Recently, results on generating cuts using information from two rows of the tableau have appeared. In particular, Andersen, Louveaux, Wolsey and Weismantel (2007) investigate the facets of a particular relaxation of the MILP to a problem with two integer variables and two constraints. They show that all facets are then split inequalities or intersection cuts obtained from triangles or quadrilaterals. We give the converse, determining which of these splits, triangles and quadrilaterals actually give facets. We also give the corresponding characterization for an infinite-dimensional relaxation of the relaxation of Andersen et al., similarly to the relaxation used by Gomory and Johnson in their study of the group problem. Joint work with Gerard Cornuejols.

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. In the first part of the talk we will survey known results. In the second part of the talk we 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 is obtained using a coloring extension theorem that in turn makes use of disjoint paths in order to construct a coloring. The notion of "winding number" of a 3-coloring plays an important role. This is joint work with Zdenek Dvorak and Daniel Kral.

In this talk we discuss the proof of the following conjecture by Bollobas and Komlos: Suppose that G and H are both graphs on n vertices, H has bounded maximum degree, chromatic number r, and bandwidth o(n), G has minimum degree at least ((r-1)/r + eps)n, and n is sufficiently large. Then G must contain a copy of H. This is joint work with Julia Boettcher and Mathias Schacht.

Consider the following model of random graphs. We are given a monotone graph property P (Hamiltonicity, non-3-colorability, containment of a copy of a fixed graph H etc.) and an integer parameter r>=1. At each round, we are presented with r random edges from the set of edges of the complete graph K_n on n vertices and are asked to choose one of them. The task is to design an online edge choice algorithm that will be able to postpone (avoid) or to facilitate (embrace) almost surely the appearance of P. This model is sometimes called the Achlioptas process, after Dimitris Achlioptas who suggested it for the case r=2 and the property P being the existence of a linear sized connected component (the so called giant component) in the graph. The latter setting is essentially the only one that has been studied extensively so far. In the work to be presented, we were able to achieve a satisfactory solution for the case where the task is to avoid the appearance of a fixed graph H, and H is either a cycle, or a complete graph, or a complete bipartite graph. The answer is quite surprising and depends heavily on the parameter r. For example, the threshold for avoiding K_4 in the Achlioptas process with parameter r=2 is n^{28/19}.

A pair of square $0,1$ matrices $A,B$ such that $AB^T=E+kI$ (where $E$ is the $n \times n$ matrix of all 1s and $k$ is a positive integer) are called {\em Lehman matrices}. These matrices figure prominently in Lehman's seminal theorem on minimally nonideal matrices. There are two choices of $k$ for which this matrix equation is known to have infinite families of solutions. When $n=k2+k+1$ and $A=B$, we get point-line incidence matrices of finite projective planes, which have been widely studied in the literature. The other case occurs when $k=1$ and $n$ is arbitrary, but very little is known in this case. This talk discusses this class of Lehman matrices and classifies them according to their similarity to circulant matrices. The work is joint with Betrand Guenin and Levent Tuncel.

Let P be a finite poset and s(P) the minimal number of pairwise comparisons, which will suffice to sort P in the worst case. A sorting procedure can be viewed as a game, where a PLAYER chooses a pair of non-comparable elements, and an ORACLE responds which one is smaller. The game ends when a linear order is achieved. The PLAYER tries to minimize the number of questions, the ORACLE --- to maximize it. s(P) is the price of this game. Conditional sorting is a generalization of this (conventional) sorting. In it, the ORACLE is restricted in his answers: they must comply with a given poset Q that is an extension of P. Let s(P/Q) be the price of this game. Clearly, s(P/P)=s(P) and s(Q){\leq} s(P/Q){\leq} s(P). Conditional sorting can be used to obtain nontrivial lower bounds for conventional sorting (an old idea of D. Knuth). For the case when P is an extension of 2 chains (merging), we demonstrate an intimate connection between conditional and conventional sorting. In this case, for any extension Q an "intermediate" poset R can be effectively found such that s(P/Q)=s(R).

We consider the following packing problem. How many d-dimensional cubes of side length 2 can we pack into a d-dimensional torus of odd side length? In this talk we present some of the best known constructions, detail the connection between this packing problem and the problem of determining the Shannon capacities of graphs, and discuss some recent techniques for establishing upper bounds. Some related open questions on graph products will also be discussed.

Click here

We propose the following model of a random graph on n vertices. Let F be a distribution in R_+^{n(n-1)/2} with a coordinate for every pair ij with 1 \le i,j \le n. Then G_{F,p} is the distribution on graphs with n vertices obtained by picking a random point X from a distribution with a log-concave density f and defining a graph on n vertices whose edges are pairs ij for which X_{ij} \le p. The standard Erdos-Renyi model is the special case when F is the indicator function for the We thus obtain an interesting connection between convex geometry and random graphs.

When f is down-monotone we can determine the connectivity and matching thresholds up to a constant factor. When f is the indicator function for a right simplex then we can obtain more precise results on connectivity and the diameter.

If X is used to define weights for an optimization problem and f is "column independent" then we can whp solve the ATSP asymptotically.

Joint work with Santosh Vempala and Juan Vera

We consider words with letters from a q-ary alphabet A. The k-th subword complexity of a word w in A* is the number of distinct subwords of length k that appear as contiguous subwords of w.

We analyze subword complexity from both combinatorial and probabilistic viewpoints. Our first main result is a precise analysis of the expected k-th subword complexity of a randomly-chosen word w in A^n. Our other main result describes, for w in A*, the degree to which one understands the set of all subwords of w, provided that one knows only the set of all subwords of some particular length k. This is joint work with Mark Ward.

Anti-Ramsey problems usually refer to the study of rainbow subgraphs in an edge-colored host graph, where a subgraph is rainbow if all of its edges have different colors. The anti-Ramsey number of a graph H for a given integer n, denoted by AR(n,H), is the maximum number of colors of an edge-coloring of the complete graph K_n that contrains no rainbow copy of H. The idea is that as one increases the overall number of colors used on K_n, eventually one must force a rainbow copy of H. This can be viewed as Turan analogue for edge-colorings. The anti-Ramsey numbers were introduced by Erdos, Simonovits, and Sos in the 1970's. Many news results were obtained in recent years.
Axenovich, Jiang, Tuza introduced the notion of local anti-Ramsey numbers. The goal is to study the threshold on the number of colors appearing at each vertex beyond which a rainbow copy of H is forced. They also considered properly colored copy of H. Several problems they raised remain unsolved. The main difficulty seems to be that when one imposes a condition on the color degree (the number of different colors appearing at a vertex) it has little global effect, and often one gets closer to extremal values by using highly unbalanced colorings. So, most techniques based on counting seem to fail. In this seminar talk, we review these problems and the partial results. We answer one of the conjectures raised by them affirmatively. That is, for every k, there exists an absolutely constant lambda_k such that in every edge-coloring of K_n in which the color degree of each vertex is at least lambda_k, there exists a properly cycle of length exactly k.

Jagger, Stovicek and Thomason defined the class of k-common graphs, and showed among other results that every graph containing K_4 as a subgraph is not 2-common. We prove that every graph containing K_3 as a subgraph is not 3-common.

We consider the orienteering problem on asymmetric metrics: given a directed metric (V,d), a starting vertex s, an ending vertex t, and a length bound D, find an s-t path having length at most D that maximizes the number of vertices covered. We give an approximation algorithm for this problem achieving a guarantee of O(log^2 n). The previously best known result was an O(log n)-approximation algorithm that runs in quasi-polynomial time (Chekuri & Pal '05). For the undirected special case of this problem, a 3-approximation algorithm was known (Bansal et al. '04). Our result answers positively the question of poly-logarithmic approximability of the directed orienteering problem (Blum et al. '03). This is joint work with R. Ravi.

Click here

Let L be a finite family of graphs. We describe the typical structure of L-free graphs, improving our earlier results on the Erdos-Frankl-Rodl theorem, by proving our conjecture from our earlier paper. Let p=p(L)=min{F\in L:\chi(F)-1}. We shall prove that the structure of almost all L-free graphs are very similar to the Turan graph T_{n,p}, where ``similarity'' is measured in terms of graph theoretical parameters of L. Some more recent developements will be discussed as well. Joint work with B. Bollobas and M. Simonovits.

A graph G has ``low discrepancy'' if the global distribution of the edges of G resembles the edge distribution of a random graph of the same density. Moreover, G has a ``large spectral gap'' if the second largest eigenvalue of the adjacency matrix of G (or another suitable matrix representation of G) is significantly smaller than the average degree. It is well known (and easy to see) that a graph with a large spectral gap has low discrepancy. In this talk I will investigate the converse implication in the case of sparse graphs. The main result is that low discrepancy implies that G ``essentially'' has a large spectral gap. The talk is based on a joint paper with Noga Alon, Hiep Han, Mihyun Kang, Vojtech Rodl, and Mathias Schacht.

A classic theorem of Dirac states that a sufficient condition for an n-vertex graph to be hamiltonian is that the minimum degree is at least n/2. In my talk I will present recent results on Dirac type problems for k-uniform hypergraphs, obtained jointly with V. Rödl and E. Szemerédi.

In recent years there has been considerable interest in analyzing random graph models for the Web. We consider two such models - the Random Surfer model introduced by Blum et al. and the PageRank-based selection model proposed by Pandurangan et al.. It has been observed that search engines influence the growth of the Web. The PageRank-based selection model tries to capture the effect that these search engines have on the growth of the Web by adding new links according to Pagerank. The PageRank algorithm is used in the Google search engine for ranking search results.

We show the equivalence of the two random graph models and carry out the analysis in the Random Surfer model, since it is easier to work with. We analyze the expected in-degree of vertices and show that it follows a powerlaw. We also analyze the expected PageRank of vertices and show that it also follows the same powerlaw as the expected degree.

We show that in both models the expected degree and the PageRank of the first vertex, the root of the graph, follow the same powerlaw. However the power undergoes a phase-transition as we vary the parameter of the model. This peculiar behavior of the root has not been observed in previous analysis and simulations of the two models.

This is joint work with Prasad Chebolu.

What is the maximum number of edges in a k-uniform hypergraph on n vertices whose neighborhoods are all independent sets? When k=2 the answer is n^2/4 and this was proved by Mantel in 1907. The next case k=3 was solved by Furedi-Pikhurko-Simonovits in 2003. I will present a proof for the case k=4. This is joint work with Zoltan Furedi and Oleg Pikhurko.

I will present two (short and unrelated) applications of Szemeredi's Regularity Lemma.

In one (joint work with Benny Sudakov) we prove, for all large n, the conjecture of Lazebnik (1989) that among all graphs with n vertices and m < n^2/4 edges the maximum number of 3-colorings is achieved by a semi-complete biparite graph.

Another application proves the conjecture of Aigner, Triesch, and Tuza (1995) that one can find an unknown acyclic orientation of any given graph of order n by quering at most (1/4+o(1))n^2 edges.