A (k,d)-coloring of a graph assigns congruence classes mod k to the vertices so that adjacent vertices are assigned classes that are at least d apart. The circular chromatic number of G is the minimum of k/d such that G has a (k,d)-coloring. The ordinary chromatic number always equals the ceiling of the circular chromatic number.

At this summer's workshop in Vancouver, Zhu showed that if D is an acyclic orientation of G such that a(C)/b(C) < k/d-1 for every cycle C of G whose length l satisfies (l-1)d = i mod k for i in {k-d+1,..., 0,..., d-1}, then the circular chromatic number of G is at most k/d. In this talk, we present the background and the proof of this theorem.

(Joint work with T. Bohman, A. Frieze, and M. Ruszinko.)

Let PRⁿ be a lattice point polytope, and let L(P) = P Zⁿ. We say that P has distinct pair-sums if v_i + v_j = v_k + v_l implies {i,j} = {k,l} for v_i, v_j, v_k, v_l L(P). An example is the triangle T with vertices (0,0), (2,1), (1,2); L(T) consists of the vertices plus the interior point (1,1), and it is easy to check that the sums of pairs of points in L(T) (as vectors) are distinct, or alternatively, that the averages of the pairs are distinct. In this joint work with M. D. Choi and T. Y. Lam, we show that

(1) If PRⁿ has distinct pair-sums, then |L(P)| < 2ⁿ (a quick Putnam-ish argument), and

(2) For every n, there is a distinct pair-sum polytope in Rⁿ with |L(P)| = 2ⁿ.

We also discuss the minimum "size" of such a maximal polytope. This definition is motivated by questions in the representations of polynomials as a sum of squares.

(This is joint work with Imre Leader, David Gunderson, and Hans Juergen Prömel.)

In our work with Y. Kohayakawa and V. Rödl, we introduce the concept of discrepancy for k-uniform hypergraphs with an arbitrary constant density d, and we prove that condition disc(H) = o(1) is equivalent with several other properties of H similar to the ones introduced by Chung and Graham.

This talk will present some history, results, outlines of proofs, and open questions.

We prove that given nonnegative integers a₂, a₃, ..., a_n with sum 2^n-1-1, K_2ⁿ has a decomposition into a₂ C_2²-factors, a₃ C_2³-factors, and so on up to a_n C_2ⁿ-factors.

This is joint work with Saad El-Zanati and Shailesh Tipnis.

For a connected simple graph G, let d(u,v) be the distance between vertices u and v. A constraints function is a nonincreasing nonnegative function f: N -> R. We say that a colouring c of G satisfies f (or is an f-colouring if |c(u)-c(v)| > f(d(u,v)) whenever u and v are distinct vertices. The span of a colouring is the difference between the supremum and the infimum of its values on vertices; this can be finite or infinite.

The problem of finding a colouring with minimum span under certain constraints is a model for the problem of optimally assigning frequencies to transmitters in a radiocommunication network. In that context, the constraints functions are integer-valued, with only finitely many nonzero values.

We consider the f-colouring problem with an arbitrary real-valued constraints function f. We study what the conditions are for existence of an f-colouring of G with a finite span. We give an exact criterion for existence of such colourings when G is the d-dimensional lattice graph Z^d in which distance is the sum of absolute differences in corresponding coordinates.

Theorem: For a constraints function f, the graph Z^d has an f-colouring with a finite span if and only if f is O(n^-d), that is, f(n)<C n^-d for some constant C and all n>0.

Two conditions are obviously necessary: 3 < m < n, and m must divide the number of edges in either K_n or K_n-I. Many articles and several surveys have discussed this question, but no complete solution has been given. In this talk, we show that the necessary conditions are sufficient when m and n have the same parity, thereby completing the solution in this case.

This result provides proofs and strengthenings of Sauer's Lemma and a new approach to the reverse Sauer Inequality of Bollobás and Radcliffe. Sauer's Lemma, proved by Sauer, by Perles and Shelah, and by Vapnik and Chervonenkis, states that if F shatters no set of size k, then |F| < {m\choose k-1}+{m\choose k-2}+ ... + {m\choose 0}, and this bound is sharp.

We characterize those sets which can be order-shattered by a uniform family and those sets which can be order-shattered by an antichain. We apply the concept to a conjecture of Frankl that if F is an antichain and shatters no k-set then |F|< {m\choose k-1}.

We also give an algebraic interpretation of order shattering using Gröbner bases. This results in sharpening of a theorem of Frankl and Pach. It also points out an interesting and promising connection between combinatorial and algebraic objects.

This is joint work with Vojtech Rödl and Andrzej Rucinski.

In the past couple of years more progress has been made on various major problems in the combinatorics of arrangements, and the purpose of this talk is to survey some of this progress. The main topics that I will survey are:

* The k-set problem: A lot of new results have been obtained, starting with Dey's improved bound for k-sets in the plane, and including an improved bound in 3 dimensions, an improved lower bound in the plane, connection between k-sets and deep results in the theory of polytopes, and improved bounds on levels in arrangements of curves.

* Incidences between points and curves: I will survey recent progress on this problem, including improved bounds for incidences between points and circles and several related problems. I will also mention new results concerning bounds on the number of k-simplices spanned by a point set in d dimensions that are congruent to a fixed simplex.

This notion was introduced by Adler and Leighton in a paper presenting a new compression technique for efficient multi-casting. In this talk, we present the main results of their paper on this variant of Ramsey theory: they proved that \Omega(p^3/5) < m(p) < O(p^5/6). If time permits, we will discuss the motivating application.