Combinatorics Seminar - Spring 2001

Title:	On the chromatic number of simple hypergraphs
Speaker:	Professor Alexandr Kostochka [www], [e-mail]
	University of Illinois at Urbana-Champaign
Date:	January 23, 2001
Abstract:	A typical extremal problem in hypergraph coloring is to determine the minimum number of edges in a hypergraph of a given kind that is not k-colorable. Let m_k(r) denote the minimum number of edges in a simple r-uniform hypergraph that is not k-colorable, where a hypergraph is simple if no distinct edges share more than one vertex. Erdös and Lovász proved that m_k(r) is at least k^2r-4/[16r(r-1)²] and at most 1600r⁴k^2r+2. Grable, Phelps, and Rödl improved the upper bounds for every r and infinitely many k using Steiner systems. Our results improve this upper bound, and we also improve the bounds of Erdös and Lovász for sufficiently large k in terms of r. Asymptotically, we match the order of magnitude in the Grable-Phelps-Rödl upper bound by proving for each fixed r and sufficiently large k that m_k(r)> c k^2r-2ln² k, where c depends only on r. This is joint work with Dhruv Mubayi, Vojtech Rödl, and Prasad Tetali.

Title:	Packing and covering triangles in graphs.
Speaker:	Jeong-Hyun Kang [e-mail]
	University of Illinois at Urbana-Champaign
Date:	January 30, 2001
Abstract:	Let $\nu$ (G) be the maximum size of a set of pairwise edge-disjoint triangles of G, and let $\tau$ (G) be the minimum size of an edge-covering of the triangles of G. We want to bound $\tau$ (G) in terms of $\nu$ (G). Trivially, $\tau$ (G) < 3 $\nu$ (G). The graphs K₄ and K₅ show that $\tau$ (G) can be as large as 2 $\nu$ (G). In 1981, Tuza conjectured that 2 $\nu$ (G) is an upper bound for $\tau$ (G). He proved conjecture for planar graphs, K₅-free chordal graphs, and graphs with n vertices and at least 7n²/16 edges. Krivelevich proved that graphs without subdivisions of K_3,3 satisfy the conjecture, improving on planar graphs. Tuza also showed that $\tau$ (G) < 7 $\nu$ (G)/3 when G is tripartite, and Haxell and Kohayakawa improved this bound to $\tau$ (G) < (2- $\varepsilon$ ) $\nu$ (G) for a small positive constant $\varepsilon$ . In this seminar, we will show that $\tau$ (G) <(3- $\varepsilon$ ) $\nu$ (G) for an $\varepsilon$ that is at least 3/23. Thus $\tau$ (G)<2.8696 $\nu$ (G). This is the first nontrivial upper bound for general graphs, shown by Haxell in 1999.

Title:	On Coins and Cones
Speaker:	Dr. Van Vu
	Microsoft Research [www], [e-mail]
Date:	February 2, 2002
Abstract:	Given n coins of two possible weights (light and heavy) and a regular balance, we want to know whether all the coins have the same weight. How long will this take? (We suggest that the reader find the answer for small n, say n=10). We have discovered that this apparently harmless puzzle is actually equivalent to a more serious and beautiful question in linear algebra. Solving this question helps us answer severl other open problems in various areas. (This work is partially joint with N. Alon and D. Kozlov.)

Title:	Hamiltonian paths in a special family of graphs
Speaker:	Professor Douglas West [www], [e-mail]
	University of Illinois at Urbana-Champaign
Date:	February 6, 2001
Abstract:	A "combinatorial Gray code" is a listing of a family of combinatorial structures in an order so that each is obtained from the previous one by a small change of a specified type. For example, consider the subsets of [n], and allow changes that introduce or delete the element 1 or enlarge or delete one element of the subset. These allowed adjacencies define a graph on the subsets of [n], and our problem is to find a spanning path. The graph happens to be the cover graph of a special poset that arises in other contexts. We prove that the graph has a spanning path if and only if (n+1)n/2 is odd and n does not equal 5.

Title:	Expanders, Eigenvalues, and related topics
Speaker:	Professor Joel Friedman [www], [e-mail]
	University of British Columbia, Canada
Date:	February 13, 2001
Abstract:	The topics of "expanders" and "graph eigenvalues" attract computer scientists, mathematicians, and physicists; these topics, while intrinsically interesting, also provide surprising and compelling connections between The diverse fields. An "expander" is a type of graph with good connectivity properties. We shall explain what "expanders" are and how the eigenvalues of a graph's adjacency matrix relate to "expansion." The study of "expanders" and "graph eigenvalues" includes connections to many related topics. We shall explain a connection to obtaining upper bounds on error-correcting codes. Our discussion will be quite non-technical and will not assume prior knowledge about expanders, eigenvalues, or error-correcting codes.

Title:	Distributed graph algorithms
Speaker:	Professor Michal Karonski [www], [e-mail]
	Adam Mickiewicz University, Poznan, Poland and Emory University
Date:	February 20, 2001
Abstract:	In our talk we are concerned with distributed graph algorithms, where a synchronous, message-passing network without shared memory is to compute a function of its own topology. In such a distributed network, the cost of sending a message between two nodes is proportional to their distance in the network. Since sending messages to far-away nodes is expensive, it is desirable that computation be based only on information available locally. This locality constraint can be quite severe when one must compute a global function of input data that are spread across the network; it represents a challenge for algorithmic design. This communication problem is completely neglected in the popular PRAM model. There, the existence of a shared memory which can be accessed in unit time allows fast collection and dissemination of data among the processors. Once this assumption is removed and the cost of communication is taken into consideration, several computational problems which were easily solvable suddenly become hard or unsolvable efficiently, especially if one is seeking deterministic solutions. Here we focus on computing maximal matchings and f-matchings and also on graph coloring problems.

Title:	Perfect Matchings and Hamiltonian Cycles in Random Graphs (colloqium)
Speaker:	Professor Michal Karonski [www], [e-mail]
	Adam Mickiewicz University, Poznan, Poland and Emory University
Date:	February 22, 2001
Abstract:	In the first part of my talk, an overview of some results dealing with the existence of perfect matchings and hamiltonian cycles in various types of random graphs shall be given, starting with the classical results of Erdös and Rényi. The main part of the talk however will be devoted to the presentation of a joint recent result with Boris Pittel (Ohio State University) concerned with the existence (with high probability) of a perfect matching in a union of dependent random mappings. We shall discuss briefly basic proof techniques as well as explain motivations arising from a combinatorial optimization problem, known as a random assignment problem.

Title:	Embedding arbitrary graphs into strongly regular and distance regular graphs
Speaker:	Professor Dimitry Fon-Der-Flaass [e-mail]
	Sobolev Institute of Mathematics, Novosibirsk, Russia
Date:	February 27, 2001
Abstract:	We show that every simple graph with n vertices is an induced subgraph of some strongly regular graph with fewer than 4n² vertices. Up to a constant factor, this coincides with the existing lower bound. We also show that every simple graph with n vertices is an induced subgraph of some distance regular graph of diameter 3 with fewer than 8n³ vertices.

Title:	Reducible configurations for the pancake problem
Speaker:	William Cuckler [www], [e-mail]
	University of Illinois at Urbana-Champaign
Date:	March 6, 2001
Abstract:	The pancake problem is the problem of finding f(n), the worst-case number of prefix reversals required to sort a permutation of n integers (a permutation is sorted if its elements are in increasing order). The problem is open; the known bounds are 15n/14 < f(n) < (5n+5)/3. We introduce a concept of $\alpha$ -reducible configuration and show that if every permutation of [n] lacking at least r adjacencies contains an $\alpha$ -reducible configuration, then f(n) < $\alpha$ n+c_r for some constant c_r. Here an "adjacency" is a contiguous appearance of successive values in the permutation. We present some configurations that are 13/8-reducible, seeking an asymptotic improvement in the upper bound. Say that two blocks (strings of adjacent elements) are "successive" if the largest element of one block and the smallest of the other are successive in the size order. We show that every configuration having eight successive blocks, two sets of seven successive blocks, or four sets of five successive blocks is 13/8-reducible. We also put severe restrictions on permutations that have no strictly 5/3-reducible configuration.

Title:	An Extension of a Theorem of Alon and Yuster in Extremal Graph Theory
Speaker:	Professor Yoshiyasu Ishigami [www], [e-mail]
	University of Electro-Communications, Tokyo, Japan and University of Illinos at Urbana-Champaign
Date:	March 20, 2001
Abstract:	Alon and Yuster [1992] proved the following theorem about packing of graphs. Let H be a fixed r-chromatic graph, and let G be a graph of order n. Their theorem asserts that if n is sufficiently large and G has minimum degree at least (1-1/r)n, then G contains vertex-disjoint copies of H covering almost all vertices of G (all but $\varepsilon$ n). When H=K_r, the theorem gives an asymptotic version of the Hajnal-Szemerédi Theorem [1970]. We improve the theorem by showing that the conclusion still holds whenever H has order at most clog n, where c is independent of n (it depends on r and $\varepsilon$ ). This magnitude of \|H\| is best possible. Our proof method is quite different from the original proof of 1992. We will also present related results, including a common extension of the Erdös-Stone Theorem and the Alon-Yuster Theorem.

Title:	The Regularity Lemma and its applications (Part I: the graph case)
Speaker:	Dr. Jozef Skokan [www], [e-mail]
	University of Illinois at Urbana-Champaign
Date:	March 27, 2001
Abstract:	While proving his famous Density Theorem, Szemerédi invented an auxiliary lemma which later proved to be a powerful tool in extremal graph theory. This ``Regularity Lemma'' states that all sufficiently large graphs can be approximated by ``random-like'' graphs. This feature is especially useful in situations when the desired result is easier to prove for random graphs. One such situation is that of counting copies of a given small graph H in another graph. Although this problem is very hard in general, there is a simple counting argument that counts these copies of H in the approximation produced by the Regularity Lemma. In this talk, we present the Regularity Lemma and outline its proof. We also discuss some applications of this lemma and the counting argument mentioned above.

Title:	The Regularity Lemma and its applications (Part II: the hypergraph case)
Speaker:	Dr. Jozef Skokan [www], [e-mail]
	University of Illinois at Urbana-Champaign
Date:	April 3, 2001
Abstract:	In this talk, we point out difficulties in generalization of the Regularity Lemma from graphs to hypergraphs. In particular, we show that the concept of regularity used in the graph case is not sufficient in the hypergraph case. We present the concept of ( $\delta$ ,r)-regularity introduced by Frankl and Rödl, which yields a regularity lemma and a counting argument that allows us to find all small hypergraphs in sufficiently large hypergraphs. If time permits, we also show how this regularity lemma for hypergraphs can be used to deduce results similar to the original Regularity Lemma of Szemerédi.

Title:	New types of coding problems
Speaker:	Professor Gyula O.H. Katona [www], [e-mail]
	R\'enyi Institute, Budapest, Hungary, and University of Memphis
Date:	April 10, 2001
Abstract:	Let X be an n-set, and let k be a positive integer less than n/2. Suppose that (A₁, B₁) and (A₂, B₂) are pairs of disjoint k-element subsets of X. Define the distance between them by d((A₁, B₁), (A₂, B₂))=min { \|A₁ - A₂\| + \| B₁ - B₂\|, \|A₁-B₂\|+\|B₁-A₂\|} . This is a metric on the space of such pairs. H. Enomoto and the author proved that the family of all k-subsets of X can be paired (omitting one if their number is odd) in such a way that the distance for each pair is at least k. The proof used a Hamiltonian theorem. It does not answer however the coding question ``what is the maximum number of pairs with pairwise distance at least k'' since here every k-element set can be used only once. Now we give some lower and upper bounds on the maximum size of such ``codes'' with distance d. Other coding type questions are also posed.

Title:	On the Erdös-Simonovits-Sós Conjecture about the anti-Ramsey number of a cycle
Speaker:	Professor Douglas West [www], [e-mail]
	University of Illinois at Urbana-Champaign
Date:	April 17, 2001
Abstract:	The anti-Ramsey number f(n,H) of a graph H is the maximum number of colors in an edge-coloring of K_n such that no copy of H has distinct colors on its edges. Let f_k(n) denote the anti-Ramsey number of the cycle C_k. Erdös, Simonovits, and Sós provided a construction for each k that they conjectured to be optimal within an additive constant as n grows. Alon proved the conjecture for k<4 and proved a general upper bound about twice the conjectured value. We prove the conjecture for k<6 and improve the general upper bound by almost a factor of 2. (Joint work with Tao Jiang)

Title:	Triangle Packing and Covering
Speaker:	Professor Penny Haxell [e-mail]
	University of Waterloo, Canada
Date:	April 24, 2001
Abstract:	For a graph G, let $\nu$ (G) denote the maximum size of a set of pairwise edge-disjoint triangles in G. A transversal of (the triangles in) G is a set of edges C of G such that every triangle of G contains at least one edge from C. We denote by $\tau$ (G) the minimum size of a transversal of G. It is clear that $\tau$ (G) < 3 $\nu$ (G) for every graph G. A conjecture of Tuza states that $\tau$ (G) < 2 $\nu$ (G) for every graph G. We discuss what is known about this conjecture, and in particular that it is approximately true for large dense graphs.

Title:	Julius Petersen - the Man, the Myth, the Legend
Speaker:	Profesor Bjarne Toft [www], [e-mail]
	University of Southern Denmark, Odense, Denmark
Date:	May 1, 2001
Abstract:	The emergence of graph theory at the end of the nineteenth century is closely linked to the work of two mathematicians, James Joseph Sylvester in the United States and England and Julius Petersen in Denmark. They met in 1889 in Copenhagen and in 1890 in Oxford and together they created graph factorization theory. Petersen and his colleague Zeuthen, the two professors at the University of Copenhagen, established a mathematical tradition in Denmark almost out of nothing. Both are still remembered for their geometry, but Zeuthen also as a historian of mathematics and Petersen for the graph theory. Petersen did pioneering work in several fields, including algebra, combinatorics, cryptography, economics, function theory, geometry, mathematical physics and the teaching of mathematics. But both his graph theory and some of the other brilliant pieces went unnoticed or met with outright rejection in his own time. This is not to imply that his life was one of disappointment - far from it. He was the embodiment of the best sense of humour and the most vigorous joy in life.

© Jozef Skokan, 2002