| Title: | On the chromatic number of intersection graphs of convex sets in the plane |
| Speaker: | Seog-Jin Kim [www], [e-mail] |
| University of Illinois at Urbana-Champaign | |
| Date: | September 10, 2002 |
| Abstract: | Let G be the intersection graph of a finite family of convex sets obtained by translations of a fixed convex set in the plane. We show that the chromatic number of G is at most 3k-2, where k is the clique number of G. This is joint work with A.V. Kostochka and K. Nakprasit. |
| Title: | Cycles in graphs |
| Speaker: | Dr. Jacques Verstraete [www], [e-mail] |
| Microsoft Research | |
| Date: | September 17, 2002 |
| Abstract: | One of the fundamental open problems in combinatorics is the determination of the maximum number of edges in a graph on n vertices without a cycle of fixed even length. In general, the only information known is that this number is at most 8(k -1)n(1 + 1/k) and of order at least n(1 + 2/3k). In this talk, I will discuss such extremal problems for cycles and a few connections to questions in combinatorial number theory, geometry, and simple group theory. We will end with some open questions. |
| Title: | Proof of a Conjecture of Loebl for large graphs |
| Speaker: | Dr. Yi Zhao [e-mail] |
| University of Illinois at Chicago | |
| Date: | September 24, 2002 |
| Abstract: | M. Loebl conjectured that if in a graph G on n vertices at least half the vertices have degree at least n/2, then G contains, as subgraphs, all trees with at most n/2 edges. The truth of the conjecture will imply that the Ramsey number of trees on n vertices is at most 2n-2. Improving the approximate result of Ajtai, Komlós, and Szemerédi, we prove the conjecture for sufficiently large n. |
| Title: | Packing of jacks |
| Speaker: | Dr. Jozef Skokan [www], [e-mail] |
| University of Illinois at Urbana-Champaign | |
| Date: | October 1, 2002 |
| Abstract: |
For a point
c = (c1, c2, ..., ck)
in {1, 2, ..., n}k we define a jack
J(c)
with center c as the set of points that differ from
c in at most one coordinate.
For i, 1< i < k, and fixed
c1, c2, ..., ci-1, ci+1,
...,ck in {1, 2, ...,n},
we also define a line as a set of n points of the form
{(c1, c2, ..., ci-1, x,
ci+1, ...,ck) :
1< x < n}.
The following problem was formulated by Laszló Székely: Let LS(n, k) be the maximum cardinality of a system J of jacks for which
This is a joint work with Vojtech Rödl (Emory University). |
| Title: | Equitable choosability for graphs of bounded tree-width |
| Speaker: | Professor Michael Pelsmajer |
| Illinois Institute of Technology | |
| Date: | October 8, 2002 |
| Abstract: | A graph is equitably k-choosable if for every assignment of lists of size k to its vertices, there is a proper coloring chosen from the lists such that each color class has size at most the ceiling of n/k. This combines the notions of k-choosability and equitable k-colorability. It is conjectured that a graph with maximum degree \Delta is equitably k-choosable for all k > \Delta+1, and this has been proved for several classes of graphs. We show that for w = 2, 3, 4, 5, a graph with tree-width at most w is equitably k-choosable if k > \Delta+1 and k >: 3w-1. For w > 5, we show that a graph with tree-width at most w is equitably k-choosable if k > \Delta+w-4 and k > 3w-1. A corollary is that chordal graphs are equitably k-choosable for k > 3\Delta-1. |
| Title: | Uniformly distributed hypergraphs are uniformly distributed locally |
| Speaker: | Professor Dhruv Mubayi [e-mail] |
| University of Illinois at Chicago | |
| Date: | October 15, 2002 |
| Abstract: |
Ramsey-Turán problems are similar to Turán problems, except
that we require the underlying (hyper)graph to have small independence
number. I will describe several new results on Ramsey-Turán
problems for hypergraphs. One of them, informally stated in the title,
allows us to construct infinitely many l-graphs with
Ramsey-Turán density lower than the Turan density. (This is joint work with Vojtech Rödl.) |
| Title: | Distance graph on the integer grid with l1 norm |
| Speaker: | Jeong-Hyun Kang [e-mail] |
| University of Illinois at Urbana-Champaign | |
| Date: | October 22, 2002 |
| Abstract: |
A long-standing open problem in combinatorial geometry is the chromatic
number of the unit-distance graph in Rn; here
points are adjacent if their distance in the l2-norm is
1. For n=2, we know the answer is between 4 and 7. Little is known
about other dimensions. The subgraph induced by the rational points has
been studied with limited success in small dimensions.
We consider the analogous problem on the n-dimensional integer grid with fixed distance in the l1 norm. That is, we make two integer grid points adjacent if the sum of the absolute differences in their coordinate values is r. Let the chromatic number of this graph be c(n,r). Since the resulting graph is bipartite when r is odd, we focus on the case of even r. Here Broere [1994] proved that c(2,r)=4. We will prove that (i) c(n,2) = 2n for all n, and (ii) (1.1)n < c(n,r) < (6e)n for large n. This is joint work with Prof. Füredi. |
| Title: | On incomparable and uncomplemented families of sets |
| Speaker: | Professor Yuejian Peng [e-mail] |
| Indiana State University | |
| Date: | October 29, 2002 |
| Abstract: |
Let A1,...,Ak be families of distinct
subsets of [n]. These families are incomparable if no set
in one family is contained in a set in another family. A family of
subsets is uncomplemented if it contains no complementary pair of
sets. Hilton conjectured that for k families of distinct subsets
from [n] that are incomparable and uncomplemented, the sum of the
sizes of the families is at most 2k-1. We prove that
(4-81/2)2n-1 is an upper bound. We also
prove the conjectured bound for some cases.
(This is joint work with Cheng Zhao.) |
| Title: | Decompositions of Planar Graphs based on Schnyder labellings |
| Speaker: | Professor William T. Trotter |
| Georgia Institute of Technology | |
| Date: | November 5, 2002 |
| Abstract: | The concept of a Schnyder labelling of the angles of a planar triangulation plays a key role in his proof that a graph is planar if and only if its vertex-edge poset has dimension at most 3. In particular, the labelling induces a family of normal paths. Brightwell and Trotter generalized the path concept to arbitrary 3-connected planar graphs to show that the vertex-edge-face poset of a planar graph has dimension 4 and drop to 3 if any vertex or any face is removed. Here we discuss a decomposition of a planar triangulation based on the structure of the Schnyder labellings. These labellings form a distributive lattice, and the unique maximum element has a number of interesting properties. |
| Title: | Geometric Inclusion Orders: From planar graphs to Ramsey theory |
| Speaker: | Professor William T. Trotter |
| Georgia Institute of Technology | |
| Date: | November 7, 2002 |
| Abstract: |
Every partial order has a representation as a family of sets ordered by
inclusion. In recent years, attention has focused on inclusion
representations using familiar geometric objects such as rectangles,
squares, circles (disks), and their higher dimensional analogues. For
example, Schnyder's theorem asserts that a graph is planar if and only if
its vertex-edge poset has dimension at most 3; this is equivalent to
having an inclusion representation using equilateral triangles with a
common orientation.
Scheinerman showed that the vertex-edge poset of a graph has dimension at most 3 if and only if it has an inclusion representation using disks in the plane. While some posets of large dimension are such "circle orders", techniques from algebraic geometry show that almost all 4-dimensional posets are not circle orders. Felsner, Fishburn, and Trotter used Ramsey theoretic techniques to prove a much stronger result: There exists a finite 3-dimensional poset that is not a sphere order. That is, this finite poset does not have an inclusion representation using spheres in d-dimensional euclidean space for any d. |
| Title: | A graph with cover degeneracy less than chromatic number |
| Speaker: | Luigi Marini |
| University of Illinois at Urbana-Champaign | |
| Date: | November 12, 2002 |
| Abstract: | We present an example by A. Pyatkin of a 4-chromatic graph that admits a vertex partition into three parts such that the union of every two of them induces a forest. |
| Title: | A bijective count of the regions formed by chords joining n points on a circle |
| Speaker: | Kevins Milans |
| University of Illinois at Urbana-Champaign | |
| Date: | November 12, 2002 |
| Abstract: | When {n choose 2} chords are drawn joining n points on a circle, the number of bounded regions formed is 1 + {n choose 2} + {n choose 4}. We give a bijective proof. |
| Title: | On the number of edges in uniform hypergraphs with no even cycles |
| Speaker: | Professor Alexandr V. Kostochka [www], [e-mail] |
| University of Illinois at Urbana-Champaign | |
| Date: | November 19, 2002 |
| Abstract: |
The problem of finding the maximum number of edges in k-uniform
hypergraphs on n vertices with no odd cycles was solved by
Gyarfas, Jacobson, Kezdy, and Lehel. We find the analogous bound for
hypergraphs with no even cycles. The problem reduces to bounding the
number of edges in a bipartite graph with no cycles of length divisible
by four such that one partite set has size n and the degree of
every vertex in the other is k.
(This is joint work with Jacques Verstraete.) |
| Title: | Coloring d-degenerate graphs equitably |
| Speaker: | Kittikorn Nakprasit [e-mail] |
| University of Illinois at Urbana-Champaign | |
| Date: | December 3, 2002 |
| Abstract: |
An equitable coloring of a graph is a proper vertex coloring such that the
sizes of color classes differ by at most 1. A d-degenerate
graph is a graph whose subgraphs have minimum degree at most d. For
example, forests are 1-degenerate, outerplanar graphs are
2-degenerate, and planar graphs are 5-degenerate.
We show that if the maximum degree of a d-degenerate n-vertex graph is at most n/15, then G is equitably k-colorable for every k at least 16d. A corollary is that there exists a polynomial-time algorithm that, given a d-degenerate graph that is equitably s-colorable, can produce an equitable k-coloring whenever k > 31ds. |
| Title: | Graph homomorphism into an odd cycle |
| Speaker: | Gexin Yu [e-mail] |
| University of Illinois at Urbana-Champaign | |
| Date: | December 10, 2002 |
| Abstract: |
A homomorphism from a graph G to a graph H is an
adjacency-preserving map from V(G) to V(H). For example, a
proper k-coloring of G can be viewed as a homomorphism from
G to a k-clique. Let G be a simple n-vertex
graph, and suppose that n > k > 5. We prove
that if every odd cycle in G has length at least 2k+1 and
the minimum degree of G is at least 2n/(2k+3), then G
has a homomorphism into the cycle of length 2k+1. As a corollary,
we settle affirmatively the following open problem posed by Alberson, Chan
and Haas in 1993: If a graph G satisfies the conditions above, must
the ratio of the independence number of G to the number of vertices
of G be at least k/(2k+1)?
This is joint work with Prof. Hong-Jian Lai of West Virginia University. |