# The ACO Seminar (2007-2008)

All talks on a combinatorial/discrete math/theoretical CS/not so theoretical CS/OR theme are welcome!

the organizers: Dhruv Mubayi ( mubayi@math.uic.edu )and Oleg Pikhurko ( pikhurko@andrew.cmu.edu ).

Subscribe to the ACO seminar mailing list

## Past Schedule:

1995-96 1996-97 1998-99 1999-00 2000-01 2001-02 Fall 02 Spring 04 2004-05 2005-06 2006-07

## Current Schedule - Academic year 2007/8:

Title:Packing in Multipartite Graphs
Speaker: Ryan Martin, Iowa State
When: May 2, 11:30-12:30 (IRREGULAR DAY AND TIME)
Where: HBH 237 (IRREGULAR PLACE)
Abstract:
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.

Title: Scarf's Lemma and the Stable Paths Problem
Speaker: Penny Haxell, Waterloo
When: May 1, 12:30-13:30
Where: Porter Hall 125B
Abstract:
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.

Title: The formulation complexity of minimum cut
Speaker: Ojas Parekh, Emory University
When: April 24, 12:30-13:30
Where: Porter Hall 125B
Abstract:
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.

Title: A Polynomial Bound on Vertex Folkman Numbers
Speaker: Andrzej Dudek, Emory University
When:Tuesday April 15, 12:30-13:30 (IRREGULAR DAY)
Where: Wean Hall 5304 (NEW ROOM)
Abstract:
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.

Title: Digraph limits
Speaker: David Offner, CMU
When: April 10, 12:30-13:30
Where: Porter Hall 125B
Abstract:
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.

Title: Two results in Discrete Differential Geometry
Speaker: Aaron Trout, Chatham University
When: April 3, 12:30-13:30
Where: Porter Hall 125B
Abstract:
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.

Title:Intersection Cuts in 2 Dimensions
Speaker: Francois Margot, CMU
When: March 27, 12:30-13:30
Where: Porter Hall 125B
Abstract:
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.

Title: Coloring triangle-free graphs on surfaces
Speaker: Robin Thomas, Georgia Tech
When: February 28, 12:30-13:30
Where: Porter Hall 125B
Abstract:
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.

Title: An Erdos-Stone type theorem for spanning subgraphs
Speaker: Anusch Taraz
When: February 21, 12:30-13:30
Where: Porter Hall 125B
Abstract:
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.

Title: Avoiding small subgraphs in Achlioptas processes
Speaker: Michael Krivelevich, Tel Aviv University
When: February 14, 12:30-13:30
Where: Porter Hall 125B
Abstract:
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}.

Title: Lehman Matrices
Speaker: Gerard Cornuejols
When: February 7, 12:30-13:30
Where: Porter Hall 125B
Abstract:
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.

Title:On conditional sorting
Speaker: Victor Grinberg
When: January 31, 12:30-13:30
Where: Porter Hall 125B
Abstract:
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).

Title: Packing cubes in a torus
Speaker: Tom Bohman
When: January 24, 12:30-13:30
Where: Doherty Hall 4303
Abstract:
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.

Title: Induced subgraphs with distinct size or order
Speaker: Alexander Kostochka, University of Illinois at Urbana-Champaign
When: December 6, 16:30-17:30
Where: Wean Hall 5302
Abstract:

Title: Log-Concave Random Graphs
Speaker: Alan Frieze
When: November 29, 16:30-17:30
Where: Wean Hall 5302
Abstract:
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

Title: On subword containment
Speaker: Irina Gheorghiciuc
When: November 15, 16:30-17:30
Where: Wean Hall 5302
Abstract:
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.

Title: Local anti-Ramsey numbers
Speaker: Tao Jiang (Miami University, Oxford, OH)
When: November 8, 16:30-17:30
Where: Wean Hall 5302
Abstract:
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.

Title: Graphs containing triangles are not 3-common
Speaker: Michael Young
When: November 1, 16:30-17:30
Where: Wean Hall 5302
Abstract:
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.

Title: The Directed Orienteering Problem
Speaker: Viswanath Nagarajan
When: October 25, 16:30-17:30
Where: Wean Hall 5302
Abstract:
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.

Title: On a random graph evolving by degrees
Speaker: Boris Pittel (Ohio State University)
When: October 19, 15:30-16:30 !! Non-standard day/time !!
Where: Wean Hall 5302
Abstract:

Title: The Typical Structure of Graphs without Given Excluded Subgraphs
Speaker: Jozsi Balogh, University of Illinois at Urbana-Champaign
When: October 11, 16:30-17:30
Where: Wean Hall 5302
Abstract:
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.

Title: Eigenvalues and discrepancy
Speaker: Amin Coja-Oghlan (Humboldt University, Berlin)
When: October 4, 16:30-17:30pm
Where: Wean Hall 5302
Abstract:
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.

Title: Hamilton cycles and perfect matchings in hypergraphs
Speaker: Andrzej Rucinski (Adam Mickiewicz University, Poznan)
When: September 27, 16:30-17:30pm
Where: Wean Hall 5302
Abstract:
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.

Title: PageRank and the Random Surfer Model
Speaker: Páll Melsted
When: September 20, 16:30-17:30pm
Where: Wean Hall 5302
Abstract:
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.

Speaker: Dhruv Mubayi
When: September 13, 16:30-17:30pm
Where: Wean Hall 5302
Abstract:
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.

Title: Two applications of Szemeredi's Regularity Lemma
Speaker: Oleg Pikhurko
When: September 6, 15:30-16:30pm
Where: Wean Hall, Room 5310
Abstract:
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.

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