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 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] 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 (K^{2}(2k+1,k)) < 4k when k is odd and (K^{2}(2k+1, k)) < 4k+2 when k is even. Also, we use intersecting families of sets to prove lower bounds on (K^{2}(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 K_{k,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.
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.
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.
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 K_{7} 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
d_{F} such that for G in F and d(P)
> d_{F}, 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 (G) < r and (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 S_{n}, 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 S_{n} 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] [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 (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 3^{k}-colored, provided (G) < n/3^{k+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 (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). |