Title:An introduction to mixed hypergraph colorings
Speaker:Professor Vitaly Voloshin [www], [e-mail]
 Moldovan Academy of Sciences
Date:January 22, 2002
Abstract: The Theory of Graph Coloring has existed for more than 150 years. It is a central part of discrete mathematics, with many contemporary generalizations and applications. Historically, graph coloring asks for the minimum number of colors needed to color the vertices so that adjacent vertices have different colors.

In the theory of coloring mixed hypergraphs, problems about both the minimum and maximum number of colors occur. Mixed hypergraphs consist of two families of (hyper)edges: classical edges and others that may be viewed as "anti-edges". In every proper coloring, classical edges have at least two vertices of distinct colors, while the "anti-edges" have at least two vertices of the same color. The interaction between edges and "anti-edges" constitutes the main feature of coloring of mixed hypergraphs. This interaction brings many new aspects to the theory of colorings, such as colorability, unique colorability, lower and upper chromatic numbers, perfection with respect to the upper chromatic number, and broken chromatic spectra.

In trying to establish a formal symmetry between the two types of constraints expressed by the edges and "anti-edges", we find deep asymmetries between the problems on minimum and problems on maximum number of colors. This asymmetry pervades the theory, methods, algorithms and applications of mixed hypergraph coloring. It leads to many new and challenging problems that should attract graduate students looking for thesis topics.

Further material on this topic appears at the Mixed Hypergraph Coloring Web Site at http://math.net.md/voloshin/mh.html.

Title:On non-z (mod k) dominating sets
Speaker:Professor Michael S. Jacobson [www], [e-mail]
 University of Louisville
Date:January 29, 2002
Abstract: Consider a graph G, an integer k greater than 1, and a nonnegative integer z with z < k and z \ne 1. A subset D of the vertex set V(G) is said to be a non-z (mod k) dominating set if D is a dominating set and for all x in V(G), |N[x] \cap D| is not congruent to z modulo k.

For the case k=2 it has been shown that such sets exist for all graphs; these could be called "odd dominating sets". The problem for k at least 3 is unsolved when k or z is odd (the existence when k and z are both even follows from the k=2 case.) In this talk we show that non-z ( mod k ) dominating sets exist when G is a tree, for all k and z. We also show that the answer is positive for unicyclic graphs when k and z are at least 4. We also give a few special cases of other families of graphs where the answer is always positive.

(This is joint work with Yair Caro.)

Title:Probabilistic Method and Ramsey Theory
Speaker:Dr. Benjamin Sudakov [www], [e-mail]
 Princeton University and IAS
Date:February 1, 2002
Abstract: "Ramsey Theory" refers to a large body of deep results in mathematics concerning partition of large collections. Its underlying philosophy is captured succinctly by the statement that "In large system complete disorder is impossible". Since the publication of the seminal paper of Ramsey in 1930, this subject has grown with increasing vitality, and is currently among the most active areas in Combinatorics. One of the most important factors in the development of Ramsey Theory was successful application of so called "Probabilistic Method". This method has been initiated more than fifty years ago by Paul Erdös and become one of the most powerful and widely used methods in Discrete Mathematics.

In this talk I will describe some classical results of Ramsey Theory together with the recent progress on some old questions of Erdös which was made using elegant probabilistic arguments.

Title:Non-amenability of Schreier coset graphs for subgroups of hyperbolic groups
Speaker:Professor Ilya Kapovich [www], [e-mail]
 University of Illinois at Urbana-Champaign
Date:February 5, 2002
Abstract: A connected graph of bounded degree is non-amenable if it has positive Cheeger isoperimetric constant or, equivalently, if the spectral radius of the simple random walk on the graph is less than one. Non-amenability is a useful property with numerous implications regarding the large-scale geometry of the graph. We will start with a non-technical introduction of the notion of non-amenability and discuss various equivalent definitions. The main result is that if G is a non-elementary Gromov-hyperbolic group and H is a quasiconvex (i.e. "nicely embedded") subgroup of infinite index in G, then the Schreier coset graph Y for G/H is non-amenable. Some of the corollaries include computing the Martin boundary of the simple random walk on Y and analyzing co-growth of H in G.

Title:On the chromatic number of the square of the Kneser graph K(2k+1,k)
Speaker:Seog-Jin Kim [www], [e-mail] and Kittikorn Nakprasit [e-mail]
 University of Illinois at Urbana-Champaign
Date:February 12, 2002
Abstract: The Kneser graph K(n,k) is the graph whose vertices are the k-element subsets of an n-element set, with two vertices adjacent if the sets are disjoint. The chromatic number of the Kneser graph K(n,k) is n-2k+2. Zoltan Füredi raised the question of determining the chromatic number of the square of the Kneser graph, where the square of a graph is the graph obtained by adding edges joining the vertices at distance 2.

We prove that \chi(K2(2k+1,k)) < 4k when k is odd and \chi(K2(2k+1, k)) < 4k+2 when k is even. Also, we use intersecting families of sets to prove lower bounds on \chi(K2(2k+1,k)), and we find the exact maximum size of an intersecting family of 4-sets in a 9-element set such that no two members of the family share three elements.

Title:Subdivisions of large complete bipartite graphs and long induces paths in k-connectd graphs
Speaker:Professor Thomas Böhme [ www], e-mail]
 University of North Texas
Date:February 19, 2002
Abstract: The following recent result is joint work with Bojan Mohar, Riste Skrekowski (Ljubljana, Slovenia) and Michael Stiebitz (Ilmenau, Germany). For every positive integers k, r and s there exists an integer N(k,r,s) such that every k-connected graph G with at least N(k,r,s) vertices contains either an induced path of length s or a subdivision of the complete bipartite graph Kk,r .

Title:Quasi-randomness for graphs
Speaker:Dr. Jozef Skokan [www], [e-mail]
 University of Illinois at Urbana-Champaign
Date:February 26, 2002
Abstract: The subject of quasi-random graphs was introduced in the eighties by Thomason and Chung, Graham, and Wilson. They realized the surprising fact that several important properties shared by almost all graphs are asymptotically equivalent in a deterministic sense.

In this talk, we will discuss these results, some open problems, and some recent developments in the case of dense graphs. If time permits, we will turn our attention to the study of quasi-randomness for graphs with the vanishing density.

Title:Methods in Modern Combinatorics
 (Arthur B. Coble Memorial Lectures)
Speaker:Professor Noga Alon [www], [e-mail]
 Tel Aviv University and Institute for Advanced Study
Date:March 5-7, 2002
Abstract: Combinatorics is an essential component of many mathematical areas, and its study has experienced an impressive growth in recent years. These lectures will discuss two of the main general techniques that played a crucial role in the development of modern combinatorics; algebraic methods and probabilistic methods. Both techniques will be illustrated by examples, where the emphasis is on the basic ideas and the connection to other areas.

1. Dimension, Distances, and Information Theory

Extremal problems in Discrete Mathematics can often be studied by considering the dimensions of appropriately constructed linear spaces. This will be illustrated by several representative examples in Combinatorial Geometry and in Information Theory.

2. Polynomials, Addition, and Coloring

The lecture will describe a general technique, called "Combinatorial Nullstellensatz", that is based on some simple properties of polynomials. Some of its applications in Additive Number Theory and in Graph Theory will be presented.

3. The Probabilistic Method

The discovery that deterministic statements can be proved by probabilistic reasoning led more than fifty years ago to several striking results in Analysis, Number Theory, Combinatorics and Information Theory. It soon became clear that the method, which is now called the probabilistic method, is a very powerful tool for proving results in Discrete Mathematics. The basic approach will be described, focusing on some recent applications as well as on the algorithmic aspects.

Title:Multiplicity problems in Ramsey Theory
Speaker:Vijaya Lakshmi Venkatajalam [e-mail]
 Bombay University, India
Date:March 12, 2002
Abstract: In 1959, Goodman gave a precise formula for the least number of monochromatic triangles when the edges of a complete graph are colored in two colors. We ask the same question for other families of graphs, such as those obtained by removing disjoint edges from a complete graph. This talk focuses on obtaining precise lower bounds on the number of monochromatic triangles in edge-colorings of several interesting classes of graphs. Besides removal of disjoint edges, these classes also include removal of paths and Hamilton cycles from complete graphs. We will also discuss the nonisomorphic ways of coloring K7 with the least number of monochromatic triangles.

Title:Alternating Sign Matrices (colloqium)
Speaker:Professor David Bressoud [www], [e-mail]
 Macalester College, St. Paul, MN
Date:March 14, 2002
Abstract: This talk will be an overview of what is known and what is conjectured about Alternating Sign Matrices, a combinatorial structure with ties to partition theory, representation theory, and statistical mechanics. The talk will include an overview of the story of the Alternating Sign Matrix Conjecture, a tale that begins with a Lewis Carroll algorithm for evaluating determinants and ends with Kuperberg's realization that the 6-vertex model of Izergin and Korepin held the key to the solution.

Editorial note: An alternating sign matrix is a square matrix with entries in {0,1,-1} such that along each row and column the nonzero entries alternating in sign, beginning and ending with +1. Every permutation matrix is an alternating sign matrix, as is the matrix of order 3 with 0s on the corners, -1 in the middle, and 1s in the other four places. The Conjecture concerns the enumeration of these matrices.

Title:Algorithmic aspects of the upper chromatic number
Speaker:Professor Vitaly Voloshin [www], [e-mail]
 Moldovan Academy of Sciences
Date:March 26, 2002
Abstract: We will discuss greedy algorithms for the upper chromatic number and will show that, in contrast to the lower chromatic number, in general backtracking is unavoidable. Some related issues concerning C-perfection and consequences also will be considered.

Title: Partitions of graphs
Speaker:Professor Michael Stiebitz [ www], [e-mail]
 Technical University Ilmenau
Date:April 2, 2002
Abstract: Consider a party of tourists. Each member has at least 2d+1 friends in the party. One day the group stays overnight in two different hotels. Each member would like to have at least d friends sleeping in the same hotel. Is this always possible?

Let p be a graph parameter, and let s and t be positive integers. We ask whether there always exists f(s,t) such that every graph G with p(G) at least f(s,t) has a vertex partition into sets A and B such that p(G[A])>s and p(G[B])> t. (Similarly, we ask whether there exists g(s,t) such that p(G)< g(s,t) yields a partition with p(G[A])< s and p(G[B])< t.) In this talk we will discuss these questions for several graph parameters.

Title:Graph Coloring Extensions: Recent Results and Open Problems
Speaker:Professor Michael O. Albertson [www], [e-mail]
 Smith College
Date:April 9, 2002
Abstract: A graph coloring extension problem asks when an arbitrary precoloring of a set P in V(G) extends to an optimal coloring of all of G. Typically this problem is NP-complete. One might hope that if the components of G[P] are far apart or extra colors are available, then there is enough flexibility to extend the coloring. Let d(P) denote the minimum distance between components of G[P]. We seek results of the following form: For a specified family F of graphs, there is a constant dF such that for G in F and d(P) > dF, every proper t-coloring of G[P] extends to a proper t-coloring of all of G.

Intense work on coloring extension theorems began after Thomassen asked whether a proper 5-coloring of a vertex set P in a planar graph G would always extend to a proper 5-coloring of G when P is an independent set with d(P) > 100. The answer is yes in a strong sense. Albertson and Hutchinson showed that if \chi(G) < r and \chi(G[P]) < s and d(P) > 4, then every proper (r+s)-coloring of G[P] in which each component of G[P] is s-colored extends to a proper (r+s)-coloring of G. This is best possible both with respect to the distance constraint and the number of colors needed. However, one can do better if we assume that G is in a special family, such as planar graphs. This talk will look at some recent coloring extension theorems as well as some natural instances where we don't know whether such a theorem exists.

Title:Probabilistic combinatorics in symmetric groups
Speaker:Professor Ákos Seress [www], [e-mail]
 The Ohio State University
Date:April 9, 2002
Abstract: Our recent work on recognition algorithms for matrix groups and on Magnus's conjecture about a residual property of free groups led to various combinatorial and probabilistic problems in finite simple groups. We discuss some of these problems in the case of alternating and symmetric groups, including the following two:

1) Given a permutation s in Sn, and a random conjugate t of it, what is the probability that s and t commute?

2) Given a word w(X,Y) using two symbols, what is the probability that two random elements x and y in Sn satisfy w(x,y)=1?

The talk assumes no group theoretic background, and the methods we use are entirely combinatorial.

Title:Coloring Graphs on Surfaces, Act II (colloqium)
Speaker:Professor Michael O. Albertson [www], [e-mail]
 Smith College
Date:April 11, 2002
Abstract: Suppose that a graph G is embedded on the surface with g handles, where g>0. In 1890, Heawood showed by Euler's Formula that G can be properly colored with at most (the floor of) (7+(1+48g)1/2)/2 colors. The proof that this is best possible was completed by Ringel and Youngs in the late 1960s. In the mid 1970s, Appel and Haken proved the Four Color Theorem, which was the missing case (g=0) in Heawood's result. This was the end of one story but the beginning of another. The proof of the 4CT proceeds inductively by altering a coloring on small patches of a graph. Consequently, if a graph embedded on a given surface looks planar in small patches, it is natural to ask if it is 4-colorable. We will see that the answer is no. However, these locally planar. graphs are 5-colorable. Actually, much more is true. Many coloring theorems about planar graphs are proved using local modification. Most of these have analogues for locally planar graphs. In several contexts the conclusions for planar and locally planar graphs are identical. Of course, there remain some simply stated though probably nasty open problems. This talk will be a tour of the highlights of what we know about coloring locally planar graphs.

Title:Designer Dice
Speaker:Professor Hal Kierstead [ www], [e-mail]
 Arizona State University
Date:April 16, 2002
Abstract: Consider a set D of fair dice with each face having a number, but each number appearing on at most one face among all the dice. There are two players: the pigeon Paul and the gambler George. Paul picks a die in D and then George picks one of the remaining dice in D. The players then roll their dice, and the player with the highest number wins. Call the set D *good* if George has a winning strategy, meaning that no matter what Paul chooses, George can choose another die from D and have probability greater than 1/2 of winning. There is a good set consisting of three six-sided dice.

Now consider a generalization with k pigeons and one gambler. One by one, each pigeon picks a die from D. The gambler then wins if he can pick a die that for each pigeon wins the bet with probability more than 1/2. The set is *k-good* if George wins no matter what dice the pigeons choose. Let f(k) be the minimum s such that there exists a k-good set of s-sided dice. We shall make a start towards understanding f by showing that f(2)=3 and f(k) < 6k lgk.

Title:Aster Tolerance Representations of Graphs
Speaker:Professor Nancy Eaton [www], [e-mail]
 University of Rhode Island
Date:April 23, 2002
Abstract: An aster is a tree which can be thought of as one which can be obtained by identifying an end vertex of a path with some vertex of another path. An aster tolerance representation of a graph G with tolerance t is an assignment of subtrees of the aster to the vertices of G so that two vertices of G are adjacent if and only if the corresponding subtrees intersect in at least t nodes.

We address the open question: Given t, exactly which graphs are aster representable with tolerance t? We give a characterization of trees which have aster tolerance representations with tolerance t, for t=1,2, and 3. Also, we present bounds on the maximum size of a cycle which has a tolerance t representation by an aster. Other results related to the characterization of graphs which have tolerance 1 representations by asters will be given.

More generally, if a graph G has a tree representation with tolerance t such that the host tree has maximum degree h and for each vertex of G, the subtree assigned to it has maximum degree s, we say G is in the set [h,s,t]. There is an open conjecture of Jamison and Mulder which states that [h,s,t] \subset [h,s,t+1]. We present a related theorem which says that if G is aster representable with tolerance t then it is also aster representable with tolerance t+1.

Title:Equitable colorings of k-degenerate graphs
Speaker:Professor Sriram V. Pemmaraju [www], [e-mail]
 The University of Iowa
Date:April 30, 2002
Abstract: An equitable coloring of a graph is a proper vertex coloring in which the color classes have sizes within one of each other. One motivation for studying equitable colorings is that existence of small palette equitable colorings implies sharp Chernoff-Hoeffding type bounds even in the presence of positive correlations between random variables. In this talk I will describe a recent result of mine that shows that any n-vertex, k-degenerate graph G with \Delta(G) < n/3 can be partitioned into three (k-1)-degenerate graphs whose sizes are within one of each other. This implies that any k-degenerate graph G can be equitably 3k-colored, provided \Delta(G) < n/3k+1. Since planar graphs are 5-degenerate, an instance of this result is that there are constants c and k such that any planar graph G can be equitably k-colored if \Delta(G) < n/c. This work generalizes a result by Bollábas and Guy for trees (1-degenerate graphs) and by Pemmaraju for outerplanar graphs (2-degenerate graphs).

© Jozef Skokan, 2002