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.

z 1

V(G), |N[x] D|

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.)

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.

We prove that (K²(2k+1,k)) < 4k when k is odd and (K²(2k+1, k)) < 4k+2 when k is even. Also, we use intersecting families of sets to prove lower bounds on (K²(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.

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.

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.

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.

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.

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.

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.

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.

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.