Title:Turán problems in extremal combinatorics
Speaker:Dr. Jacques Verstraete
 Microsoft Research
Date:January 22, 2003
Abstract: One of the major areas in combinatorics is extremal combinatorics. The fundamental questions consist in determining the maximum size of a family of objects which does not contain a prescribed configuration. For example, the Turan problem involves the determination of the maximum number of edges in a graph containing no copies of a prescribed subgraph. In this talk, I will discuss some simple extremal problems for families of sets, some recent advances in the field, as well as few of the connections to other branches of mathematics.


Title:Irreducible hypergraphs for Hall-type conditions and edge-minimal expanders
Speaker:Profesor Alexandr V. Kostochka
 University of Illinois at Urbana-Champaign
Date:January 28, 2003
Abstract: Hall's Condition for a system E of sets requires that the union of every family F of sets in E be at least as large as |F|. A more general Hall-type condition requires the size of the union to be at least r|F|+d. A system E is irreducible for this condition if the condition holds for E but fails whenever any element is removed from any set in E.

How large a set can an irreducible system contain? It is proved here that there is no upper bound when r is irrational. However, if r = p/q in lowest terms, then E can have no set with size more than max{p, p + \lceil d \rceil }. If d <0 then the bound p is sharp, but the bound p + \lceil d \rceil can be improved in some (perhaps most) cases when d >0 . We also give bounds on the minimum size of a set in E and the number of sets in which elements appear.

This is joint work with Douglas R. Woodall.



Title:On 1-factorizations of complete 3-uniform hypergraphs
Speaker:Professor Dmitry Fon-Der-Flaass
 University of Illinois at Urbana-Champaign
Date:February 4, 2003
Abstract: By Baranyai's Theorem, every complete 3-uniform hypergraph on 3k vertices can be partitioned into 1-factors. In 1991, I conjectured that there always exist such factorizations with a certain uniformity property, and I proved this for k=2 and k=3. I'll present a recent disproof of this conjecture for k=4 by Robert Johnson (a student of Imre Leader). For larger k, the problem remains open.


Title:On the k-dimension of products of posets
Speaker:Michael Baym
 University of Illinois at Urbana-Champaign
Date:February 11, 2003
Abstract: The dimension dim(P) of a poset P is the least t such that P is a subposet of the product of t chains. The k-dimension dimk(P) is the least such t when the chains in the product have size k. For posets P and Q that each have a unique maximal and unique minimal element, it is known that dim(PxQ) = dim(P)+dim(Q). It is conjectured that for all product posets, dim(PxQ) > dim(P)+dim(Q)-2. This is known for SmxSn, where Sn is the ``standard'' n-dimensional poset. In this talk, the computation of dimk(SmxSn) is described. In particular, dim2(SmxSn) = m+n = dim2(Sm)+dim2(Sn).


Title:Tree representations of Kn,n
Speaker:Dr. Jozef Skokan
 University of Illinois at Urbana-Champaign
Date:February 18, 2002
Abstract: A graph is chordal if and only if it is the intersection graph of some family of subtrees of a tree. Applying "tolerance" allows larger families of graphs to be represented. A graph G is in the family [D,d,t] if there is a tree with maximum degree D and subtrees corresponding to the vertices of G such that each subtree has maximum degree at most d and vertices of G are adjacent if and only if the subtrees corresponding to them have at least t common vertices.

It is known that [3,3,1] and [3,3,2] both equal the family of chordal graphs. Since a complete bipartite graph with partite sets of size at least 2 is not chordal, we study the minimum t such that Kn,n is in [3,3,t]. In this talk, we provide bounds for t in terms of n and discuss related problems.

This is joint work with N. Eaton, Z. Füredi, and A.V. Kostochka.



Title:Optimal decomposition of a complete graph into many parts
Speaker:Professor Douglas B. West
 University of Illinois at Urbana-Champaign
Date:February 25, 2003
Abstract: A k-decomposition of a graph G is a partition of its edge set to form k spanning subgraphs G1,...,Gk. The classical theorem of Nordhaus and Gaddum bounds the sum of the chromatic numbers over all 2-decompositions of Kn. For a graph parameter p, let p(k;G) denote the maximum of sumi p(Gi) over all k-decompositions of the graph G. We obtain upper and lower bounds on p(k;Kn) when p is the clique number, chromatic number, list chromatic number, or Szekeres-Wilf number (they all equal n+1 when k=2). The last three behave differently for large k. We also obtain bounds for the maximum of chi(k;G) over all graphs embedded on a given surface. The talk will present a portion of these results.

This is joint work with Zoltan Furedi, Alexandr Kostochka, Riste Skrekovski, and Michael Stiebitz.



Title:Minors in large graphs with large average degree
Speaker:Professor Alexandr V. Kostochka
 University of Illinois at Urbana-Champaign
Date:March 4, 2003
Abstract: The main result of this talk is the proof of the following conjecture of Mohar: There exist functions f and N such that every graph with average degree at least f(r) and order at least N(r,s) has a minor isomorphic to s disjoint copies of Kr or a minor isomorphic to Kr,s.

This result is joint work with Thomas Boehme.



Title:Free Index of Sturmian Sequences
Speaker:Weiting Cao
 University of Illinois at Urbana-Champaign
Date:March 11, 2003
Abstract: A word is a finite list, and a sequence is an infinite list. The number of letters in a word u is the length of u, denoted by |u|. Given a binary sequence F, the language complexity of length n is the number of words of length n appearing in F, denoted by pn(F). Clearly pn(F) < 2n. If pn(F)=n for some n, then F is eventually periodic. If pn(F)=n+1 for all n, then F is a Sturmian sequence. The Free Index of a sequence F, denoted FI(F), is the maximum of n+|v|/|u| such that there exist distinct words u and v, with v a prefix of u, such that F contains unv (n successive copies of u, followed by v). In this paper, we obtain a formula for FI(F) involving the continued fraction expansion of the ratio of the numbers of characters of the two types in F.

The paper can be downloaded from http://www.math.uiuc.edu/~wcao1/cao.ps.



Title:A combined logarithmic bound on the chromatic index of multigraphs
Speaker:Michael Plantholt
 Illinois State University
Date:March 18, 2003
Abstract: For any multigraph G, the integer round-up phi(G) of the fractional chromatic index fr(G) yields the best general lower bound for the chromatic index chi'(G). For an upper bound, Kahn showed that for any positive constant c there exists a positive integer N such that chi'(G) < (1+c) fr(G) whenever fr(G) > N. We show that for any multigraph G with order n and at least one edge, chi'(G) < phi(G) + log3/2 ( min {n+1 , phi(G)} ). Kahn's result follows as a corollary.


Title:Induced Ramsey numbers
Speaker:Naeem Sheikh
 University of Illinois at Urbana-Champaign
Date:April 1, 2003
Abstract: The induced Ramsey number IR(G,H) is the least number of vertices in a graph F such that every red/blue coloring of E(F) produces a red copy of G or a blue copy of H as an induced subgraph. This talk will present some results on induced Ramsey numbers from the paper "On induced Ramsey numbers" by Gorgol and Luczak, especially the result that floor{3n/2} < IR(P3,Pn) < 2n-1. If time permits, a very small improvement in this lower bound will also be presented.


Title:Variants of the Crossing Number Problem
Speaker:László Székely
 NCBI/NLM/NIH and University of South Carolina
Date:April 8, 2003
Abstract: A drawing of a finite graph G on the plane consists of placing the vertices of G on the plane and drawing each edge of G as a continuous curves in the plane connecting the points representing its endpoints, such that no curve has a vertex as an internal point and no point is an internal point of 3 curves. The crossing number cr(G) of a graph G is the minimum number of intersection points among the curves representing edges, over all possible drawings of the graph. I will discuss the history of Turán's Brick Factory Problem, which asks

"What is the crossing number of the complete bipartite graph Kn,m"?

I'll overview old and recent results on many variations of the crossing number problem, along the following lines:
(a) restricting the type of curve that we can use;
(b) in addition, restricting what can be a vertex location;
(c) modifying the concept of what counts as crossing.



Title:Gallai's conjecture on path number of a graph
Speaker:Jeong-Ok Choi
 University of Illinois at Urbana-Champaign
Date:April 15, 2003
Abstract: The path number p(G) of a graph G is the minimum number of paths needed to partition E(G). Gallai conjectured that p(G) < (n+1)/2 for every connected graph G of order n. We will present results from a paper by Dean and Kouider [2000] about the corresponding problem for disconnected graphs. If G is disconnected, then p(G) < 2n/3, which is sharp. Furthermore, p(G) < u/2 + 2g/3, where u is the number of odd-degree vertices and g is the number of nonisolated even-degree vertices in G.


Title:Disjoint cycles in digraphs
Speaker:Hailong Hu
 University of Illinois at Urbana-Champaign
Date:April 22, 2003
Abstract: In this talk, we will survey some results on the existence of k disjoint cycles in a strict digraph G. We will focus on the following conjecture of Thomassen: If each vertex of G has outdegree at least 2k-1, then G contains k disjoint cycles. This has been proved for k=1 and k=2.


Title:Small-world graphs - new random graph models
Speaker:Hemanshu Kaul
 University of Illinois at Urbana-Champaign
Date:April 29, 2003
Abstract: We are interested in two basic parameters of a graph G: lG is the average distance between two vertices in the graph, and CG (the clustering coefficient) is the average density of the subgraphs induced by vertex neighborhoods. Naturally evolving massive networks like the social networks of acquaintances (used to model the spread of diseases, rumors, etc.), the internet, the power grid, airline traffic, etc., share common characteristics like short average distance and high clustering coefficient.

In the past, these networks have been modelled by the classical random graphs Gn,p, but Gn,p does not show any local clustering, making it a bad model for these networks. Recently, several random graph models have been proposed to incorporate the "small world effect" - average distance like that of the random graph, but much higher clustering coefficient. We will discuss some of these models and their properties.

In addition to the small world effect, some of the above mentioned networks, like the internet and telephone call graphs, have been observed to have the property that the number of vertices of degree k is proportional to k-c for some constant c > 0. Graphs having this property are called power law graphs. If time permits, we will also discuss some variations on Gn,p whose degree distribution follows the power law.



Title:Covering Euclidean n-space by translates of a convex body
Speaker:Jeong-Hyun Kang
 University of Illinois at Urbana-Champaign
Date:May 6, 2003
Abstract: Rogers [1957] proved that for every closed convex body C in Rn, there is a covering of Rn, by translates of C that has density at most O(nlnn). However, a covering with low global density can have high multiplicity, where the multiplicity is the maximum number of copies of C covering a single point. Erdös and Rogers [1962] showed that, for sufficiently large n, there is a covering of Rn, by translates of C that has density at most O(nlnn) and multiplicity at most O(nlnn). In this talk, we give a combinatorial proof of this using the Local Lemma.

We also give an application of this theorem. Let G be the graph on Rn, in which points are adjacent if their distance is 1 in the lp norm. Kang and Füredi proved that G has chromatic number between (1.067)n and (p/(2\pin))1/2(5(ep)1/p)n. We apply the theorem above to obtain an upper bound of c(nlnn)5n on the chromatic number of G, independent of p. This simplifies the previous upper bound argument and improves the upper bound when p is not too large.

These results are joint work with Zoltán Füredi.



© Jozef Skokan, 2003