NSF/CBMS Regional Research Conference
in Mathematical Sciences on
Geometric Graph Theory

Home

General Announcement

Program

Principal Lecturer
János Pach

Subject
Geometric Graph Theory

Lectures

Other Invited Speakers

Invited Talks

Participants

Local Arrangements

Computing Facilities

Application Forms

Contacts

May 28 - June 1, 2002
Gateway Center

University of North Texas, Denton

Invited Talks

Title:Euclidean Ramsey Theory
Speaker:Ron Graham
Abstract:

The guiding principle of Ramsey theory can be expressed by the following statement: "Complete disorder is impossible". In this talk, we show how this principle can be applied in a geometrical setting. ------------------------------------------------------------------------------

Title:Geometry of configurations of points and lines in the plane
Speaker:Branko Grunbaum
Abstract:

In simplest terms, a geometric configuration (n_k) is a collections of n points and n (straight) lines in the plane, such that every point is incident with k of the lines, and every line is incident with k of the points. The study of configurations took off about 120 years ago, when it was realized that the theorems of Pappus and Desargues, basic for projective geometry, can be interpreted as dealing with particular configurations (9_3) and (10_3). After some initial successes at enumeration of configurations (n_3) for small n, and a few general results, the investigations ground to a halt. In particular, no nontrivial results on configurations (n_k) with k > 3 were established. This changed quite drastically about fifteen years ago. New kinds of questions were asked, and partially answered by Sturmfels, White, Pisanski, Berman, and others. Among other results, today there is a lot of information available on (n_4) configurations. These results, and as well as a variety of still unsolved problems, will be presented in the talk. -------------------------------------------------------------------------------

Title:TBA
Speaker:Daniel J. Kleitman
Abstract:

TBA ------------------------------------------------------------------------------

Speaker:Takao Nishizeki
Title:Total Colorings of Degenerate Graphs and Topological Graphs
Abstract:

A total coloring of a graph G is a coloring of all elements of G, i.e. vertices and edges, in such a way that no two adjacent or incident elements receive the same color. A graph G is s-degenerate for a positive integer s if G can be reduced to a trivial graph by successive removal of vertices with degree at most s. We prove that an s-degenerate graph G has a total coloring with D+1 colors if the maximum degree D of G is sufficiently large, say D is at least 4s+3. Our proof yields an efficient algorithm to find such a total coloring. We also obtain some implications of the result on "topological graphs," that is, graphs having bounded genus, thickness or arboricity. This is a joint work with Shuji Isobe and Xiao Zhou. ------------------------------------------------------------------------------

Speaker:Miklos Simonovits
Title:Extremal Graph Theory
Abstract:

Extremal Graph Theory is one of the most developed branches of graph theory. It has many applications in Geometry, Finite Geometries, Theory of Random Graphs. Number Theory and many other fields. The lecture will give an introduction into the exact and asymptotic extremal graph theory, into its applications and its interplay with other fields of Combinatorics and Graph Theory.

We will also list a few of the many unsolved problems in the field. ------------------------------------------------------------------------------

Speaker:Endre Szemeredi
Title:On a Ramsey type problem in combinatorial number theory
Abstract:

We describe the proof of the conjecture of K. F. Roth, P. Erd\H{o}s, A. S\'ark\"ozy and V. T. S\'os.

The conjecture states that if you color the positive integers with $k$ colors then one color-class must contain two elements, $i$ and $j$, such that $i+j=\ell^2$, for some integer $\ell$. We present a method which can be used to attack some other problems as well.

This is a joint work with Ayman Khal Falach. ------------------------------------------------------------------------------

Speaker:Roberto Tamassia
Title:Bounds on Geometric Properties of Drawings of Graphs
Abstract:

We overview upper and lower bounds on geometric properties of drawings of graphs, including area, angular resolution, edge length and number of bends. We consider various drawing standards (e.g., straight-line, orthogonal, polyline) and classes of graphs (e.g., trees and planar graphs). We also discuss computational complexity issues for graph drawing algorithms. ------------------------------------------------------------------------------

Speaker:Robin Thomas
Title:Linkless embeddings of graphs in 3-space
Abstract:

An embedding of a graph in 3-space is linkless if every circuit bounds a disc disjoint from the graph. We develop a theory of linkless embeddings which is analogous to (and generalizes) the theory of planar embeddings. We prove that
(i) Any two linkless embeddings of the same graph differ (up to isotopy) by "3-switches" (an analog of Whitney's 2-switches for planar graphs),
(ii) if two linkless embeddings of the same graph are not ambient isotopic, then they differ on a K5 or a K3,3 minor,
(iii) an embedding is linkless if and only if the fundamental group of the complement is free,
(iv) a graph is linklessly embeddable if and only if it cannot be reduced to K6 by taking minors and by doing triangle-star exchanges. This is joint work with Neil Robertson and P.D.Seymour. ------------------------------------------------------------------------------

Speaker:Tom Trotter
Title:Geometric Inclusion Orders and Ramsey Theory
Abstract:

Almost 20 years ago, Fishburn and Trotter asked whether every finite 3-dimensional partial order has an inclusion representation using circles (disks) in the plane. The answer is YES for 2-dimensional orders, and using the Alon/Scheinerman degrees of freedom argument, NO for almost all 4-dimensional orders.

Scheinerman and Weirman showed that the finiteness requirement is essential by showing that the countably infinite 3-dimensional poset Z x Z x Z does not have an inclusion representation using circles. This was subsequently extended by inclusion representation using spheres in any finite dimensional euclidean space.

The original question was settled by Felsner, Fishburn and Trotter who showed that there is a finite 3-dimensional poset which does not have an inclusion representation using spheres. In this talk, we focus on the ramsey theoretic aspect of the proof, an application which leads to a new perspective on inequalities and approximations.