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