Combinatorics Seminar - Fall 2001

Title:	Triangle-free triple systems
Speaker:	Profesor Zoltan Füredi [www], [e-mail]
	University of Illinois at Urbana-Champaign
Date:	August 29, 2001
Abstract:	A triangle in a hypergraph consists of 3 distinct edges F₁, F₂, F₃ such that for some 3 vertices v₁, v₂, v₃ the edge F_i contains v_i and v_i+1, (the indices are taken mod 3). There are 4 types of triangles formed by triples, namely: A = {124, 135, 236}, B = {124, 134, 235}, C = {124, 134, 234}, and D = {123, 134, 235}. The classical extremal function ex(n,H) is the maximum number of edges in a k-uniform hypergraph with n vertices that does not contain a configuration isomorphic to H. In 1974, Bollobás proved that ex(n,BC) = n₀n₁ n₂, where n_i = $\lfoor$ (n+i)/3 $\rfloor$ . This means that every triple system with more than n³/27 edges contains a copy of B or C. Here we review all 16 possibilities for avoiding triangles. For example, we show that for a completely triangle-free system ex(n,ABCD) = $\lfoor$ n²/8 $\rfloor$ and that ex(n,CD)= $\lfoor$ (n-1)²/4 $\rfloor$ (for sufficiently large n). (These results are joint work with G. Simonyi.)

Title:	Vertex list coloring by the semirandom method
Speaker:	Dr. Benjamin Sudakov [www], [e-mail]
	Princeton University and IAS
Date:	September 4, 2001
Abstract:	The semirandom method (Rödl Nibble) is the general approach to proving the existence of something by generating it through many iterations, applying probabilistic reasoning at each step. One area of Combinatorics where the semirandom method has had the greatest impact is graph coloring. In fact, many of the strongest result in graph coloring over the past decade are examples of this method. In this talk we will illustrate how the semirandom method works by proving the following result: Let G=(V,E) be a graph with the sets of lists S(v), one for each vertex v of G, and let d be an integer such that for every vertex \|S(v)\|=(1+o(1))d, and for each c in S(v), at most d neighbors of v have c in their lists. Then there exist a proper coloring of G from these lists. This result, which is asymptotically tight, is joint work with Bruce Reed.

Title:	On asymptotically good packings and coverings
Speaker:	Professor Nikolai Kuzjurin [www], [e-mail]
	Institute for System Programming, Russian Academy of Sciences, Moscow
Date:	September 11, 2001
Abstract:	In 1985, V.Rödl proved the long-standing conjecture of Erdös and Hanani about the existence of asymptotically good packings and coverings of l-subsets of an n-element set by k-subsets. In this talk we will consider the problem of finding threshold functions k=k(n) for the existence of such packings and coverings. It appears that the thresholds for packings and coverings differ.

Title:	Equitable list coloring for graphs with maximum degree 3
Speaker:	Michael Pelsmajer [www], [e-mail]
	University of Illinois at Urbana-Champaign
Date:	September 18, 2001
Abstract:	A graph is equitably list k-colorable if for every assigment of lists of size k to its vertices, there is a proper list coloring such that each color class has size at most $\lceil$ n/k $\rceil$ . We show that every graph with maximum degree 3 is equitably list 4-colorable.

Title:	On k-chromatic r-uniform hypergraphs with few edges
Speaker:	Professor Alexandr Kostochka [www], [e-mail]
	University of Illinois at Urbana-Champaign
Date:	September 25, 2001
Abstract:	Let m(r,k) denote the minimum number of edges in a (k+1)-chromatic r-uniform hypergraph. Erdös proved that 2^r-1< m(r,2) < r² 2^r. The best known lower bound now is due to Radhakrishnan and Srinivasan: For every c< 2^-1/2, there exists an r₀=r₀(c) such that for every r>r₀, m(r,2) > c2^r(r/ln r)^1/2. Erdös and Lovász said once ``perhaps the order of magnitude of m(r,2) is r2^r''. Repeating the argument of Erdös, one can see that for every k> 2, there exist r=r(k) and C=C(k) such that m(r,k) < Cr² k^r. The aim of this talk is to outline a proof that there exists an r₀ such that for every r > r₀, m(r,4)> c4^r (r / ln r)^2/3, where c=0.05. It seems that by elaborating the proof we can show that for every positive integer l, there exist r₀=r₀(l) and c=c(l) such that for every r>r₀, m(r,2^l) > c(2^l)^r (r / ln r)^{l / (l+1)}.

Title:	Saturated chains, paths in posets, and combinatorial geometry
Speaker:	Professor Peter Hamburger [www], [e-mail]
	Indiana-Purdue University at Fort Wayne
Date:	October 2, 2001
Abstract:	We will study the structure of saturated chains and edge-disjoint paths in partially ordered sets. Using this study, we will learn how to create pretty symmetrical drawings. In this journey, there will be some geometry, number theory, and group theory, and combinatorial topics such as codes, dual graphs, and symmetric, saturated, and maximal chains. The results will answer a conjecture of B. Grünbaum that goes back to D. W. Henderson.

Title:	Critical sets in Latin squares
Speaker:	Professor Abdollah Khodkar [www], [e-mail]
	University of Queensland, Australia
Date:	October 9, 2001
Abstract:	A Latin square L of order n is an n×n square array in which each cell is occupied by one symbol from a fixed set S of n symbols, so that each symbol occurs exactly once in each row and each column. A critical set in a Latin square is a subset of positions containing just enough information to determine the complete Latin square (similarly, a partly completed crossword puzzle might have a unique completion, even without a list of "clues" for the words). It has been conjectured that the smallest possible critical set in a Latin square has size n²/4. If so, then it may always be possible to partition a Latin square L into at most four disjoint critical sets in L. We show that Latin squares in a particular class called back-circulant Latin squares can be partitioned into four disjoint critical sets.

Title:	Sum-free sets (colloqium)
Speaker:	Professor Tomasz Luczak [www], [e-mail]
	Adam Mickiewicz University, Poznan, Poland
Date:	October 11, 2001
Abstract:	A subset of a semigroup is sum-free if it contains no solutions to the equation x+y=z. In this talk, we present some open problems and recent results concerning the structure and the number of sum-free subsets of natural numbers and abelian groups.

Title:	On the number of partial Steiner systems
Speaker:	Professor Nikolai Kuzjurin [www], [e-mail]
	Institute for System Programming, Russian Academy of Sciences, Moscow
Date:	October 16, 2001
Abstract:	A partial Steiner system is a family F of k-subsets of an n-element set such that each l-subset of the n-set is contained in at most one k-subset belonging to F Let N(l,k,n) be the number of such partial Steiner systems. We give a short probabilistic proof of the following result: If l and k are fixed, with l<k, then N(l,k,n)=n^{(1-o(1))(k-l)n^l/(k)_l}, where n tends to infinity and (k)_l=k(k-1)...(k-l+1).

Title:	Bandwidth of Hamming Graphs
Speaker:	Professor Tanya Berger-Wolf [www], [e-mail]
	Computer Science Department, University of Illinois
Date:	October 23, 2001
Abstract:	A labeling of a graph is an injective assignment of numbers 1,...,n to its vertices (an ordering of the vertices). The bandwidth of a labeling is the maximum (over all edges) of the difference of the labels on an edge. The bandwidth minimization problem for a graph is to find a labeling with smallest bandwidth. We discuss the bandwidth minimization problem for Hamming graphs; these are the cartesian products of cliques (the hypercube is a special case). We present a lower bound and a nearly optimal labeling for arbitrary Hamming graphs. This work is joint with Lawrence Harper and Mitch Harris.

Title:	Critical sets and latin trades
Speaker:	Professor Diane Donovan [www], [e-mail]
	University of Queensland, Australia
Date:	October 30, 2001
Abstract:	Let L be a latin square of order n, and let T be a partial latin square contained in L. If there is a latin square M of order n distinct from L such that L $\cap$ M=T, then L\ T is said to be a latin trade. For a given latin square L, it is possible to identify a subset of entries, termed a critical set, that intersects all latin trades in L and is minimal with respect to this property. In this talk I shall review known results on the sizes of critical sets and techniques used to construct critical sets. Stinson and van Rees showed that under certain circumstances, critical sets in latin squares R and S can be used to identify critical sets in the direct product R× S. In the later part of this talk I will discuss generalizations of their results.

Title:	Explicit constructions and derandomization techniques
Speaker:	Professor Nikolai Kuzjurin [www], [e-mail]
	Institute for System Programming, Russian Academy of Sciences, Moscow
Date:	November 6, 2001
Abstract:	When we have a proof by the probabilistic method that some combinatorial structure exists, we can be interested in finding such a structure efficiently, that is, by a deterministic polynomial time algorithm. Intensive study in recent years led to the development of different techniques for derandomizing probabilistic existence proofs. In my talk I intend to give brief survey of these techniques and describe explicit construction of asymptotically good packings. The existence of such packings was proved by Rödl (1985) by the probabilistic method.

Title:	New Results in Macaulay Theory
Speaker:	Sergei Bezrukov [www], [e-mail]
	University of Wisconsin at Superior
Date:	November 13, 2001
Abstract:	We present several new directions in Macaulay Theory. This theory studies properties of the shadow function in graded posets, i.e. the relations between the cardinality of a subset of level i of a poset and the size of its shadow in level i-1 for i > 0. Informally, a poset is called Macaulay if the shadow function satisfies two natural conditions. Macaulay posets have many applications in different disciplines. The emphasis of this talk is on deriving product theorems for Macaulay posets. The new results include several general constructions, specification of posets that are Macaulay for particular orders, and relations to some other extremal graph and poset problems. We also present several new families of Macaulay posets.

Title:	Graphs with small Ramsey numbers
Speaker:	Professor Alexandr Kostochka [www], [e-mail]
	University of Illinois at Urbana-Champaign
Date:	November 27, 2001
Abstract:	For a graph G, the Ramsey number R(G,G) is the minimum positive integer N such that in every 2-coloring of edges of the complete graph K_N there is a monochromatic copy of G. A family F of graphs is linear Ramsey if there is a constant C such that R(G,G) < C \|V(G)\| for every G in F. Burr and Erdös conjectured that for every d, the family D_d of d-degenerate graphs is linear Ramsey, where a graph is d-degenerate if each subgraph has a vertex of degree at most d. Kostochka and Rödl proved recently that at least D_d is `polynomial Ramsey'. For n > d, we say that a graph H is (d,n)-common if every set of d vertices in H has at least n-d common neighbors in H. Every (d,n)-common graph contains every d-degenerate graph on n vertices. In view of this, Frieze and Reed asked whether for every positive integer d, there is a constant C such that for every graph H on Cn vertices, either H or its complement contains a (d,n)-common subgraph. A positive answer would imply the Burr-Erdös Conjecture. In this talk we show that the answer to the original question of Frieze and Reed question is `No', but we prove a `Yes' answer for the following polynomial approximation to it. For every e > 0 and positive integer d, there a constant C such that for every positive integer n and every graph H with Cn^1+e vertices, either H or it complement contains a (d,n)-common subgraph. This is a joint work with B. Sudakov.

Title:	Nowhere-zero 4-flows and simultaneous edge-colorings.
Speaker:	Rong Luo [www], [e-mail]
	West Virginia University
Date:	December 4, 2001
Abstract:	It is proved that every bipartite graphic sequence with minimum degree at least 2 has a realization that admits a nowhere-zero 4-flow. This result implies a conjecture originally proposed by Keedwell in 1993 and reproposed by Cameron in 1999 about simultaneous edge-colorings and critical partial Latin squares. This is joint work with Wenan Zang and Cunquan Zhang.

© Jozef Skokan, 2002