1991-1992

September 24, 1997

The committee contacted all participants in the 1991-1992 DIMACS Special Year on Graph Theory, and asked them to evaluate its impact, given the perspective of several years. The response was overwhelmingly positive. All respondents reported favorably on the impact the Special Year has had on their research and scientific and scholarly development. While some individuals refered to a stimulating atmosphere and valuable interactions they had during their visits, most of the responses were very specific, pointing to concrete results and journal articles that resulted from their DIMACS visits.

It would not be practical to describe all of these results in the report. Instead, we will mention only those that this committee felt were of special importance for the development of the field. The list of references, however, presents a complete list of articles supplied by the participants. Those works were either obtained during or inspired by the activities of the Special Year.

** 2. Workshops**

Four workshops were organized during the Special Year.

- Planar Graphs: Structures and Algorithms, organized by W. T. Trotter
- Graph Embedding and Parallel Architectures, organized by F. T. Leighton, B. Maggs and A. Rosenberg
- Random Graphs and Randomized Algorithms, organized by M. Mihail and J. Spencer
- Expander Graphs and their Applications, organized by P. Diaconis and J. Friedman

**3. Post-docs and visitors**

The post-docs at the special year were Sandy Irani, Laszlo Pyber, Gabor
Tardos, Prasad Tetali and Dirk Vertigan. Irani is an Assistant Professor
of Information and Computer Science
at the University of California, Irvine,
Pyber and Tardos hold research
positions at the Hungarian Academy of Sciences in Budapest, Tetali
is an Assistant Professor of Mathematics at the Georgia Institute
of Technology and Vertigan is an Assistant Professor of Mathematics at the
Louisiana State University. Tetali reports that the most valuable aspect
of the Special Year were the workshops; on the whole he is indebted to
DIMACS for facilitating his transition from graduate school to a tenure-track
appointment.

**4. New results **

As we already mentioned in the Introduction, many results were obtained
during or immediately following the Special Year. Here we mention a select
few.

** 4.1 Piercing convex sets**

Noga Alon and Daniel Kleitman completely solved a problem raised by
Hadwiger and Debrunner about fourty years ago. A family of sets in
** R**^{d} has the (*p, q*)-property if among any *p* members of the
family some *q* have a nonempty intersection. The Hadwiger and Debrunner's
problem was whether or not for every *p, q, d*
there exists an integer *c* such that every family of compact convex
subsets of **R**^{d} having the (*p, q*)-property can be split into
*c* or fewer families, each having nonempty intersection. Alon and
Kleitman answered the question in the affirmative by using a fractional
version of Helly's theorem, linear programming duality, and a result
on epsilon-nets of convex sets.

** 4.2 Arrangeability, Ramsey numbers and game chromatic number**

This section clearly demonstrates the benefits of a timely exchange of
scientific ideas. At the Special Year workshop on Planar Graphs,
G.~Chen presented his results obtained with R. Schelp on the linearity
of Ramsey numbers for planar graphs. They used a concept they called
``arrangeability" of a graph, breaking their proof into two steps.
First they showed that graphs of bounded arrangeability have linear
Ramsey numbers, and then they demonstrated that every planar graph
has arrangeability at most 761.
Tom Trotter and Hal Kierstead were in
the audience, and shortly thereafter realized that they can use
arrangeability for a problem they were interested in: bounding the
so-called game chromatic number of a graph. Indeed, they were able
to show that every graph of bounded arrangeability has bounded
game chromatic number, and hence, by the result of Chen and Schelp
it follows that planar graphs have bounded game chromatic number.
Furthermore, Kierstead and Trotter were able to improve upon the
original bound of Chen and Schelp. That raised the question which classes of
graphs have bounded arrangeability. Later, Rodl and Thomas proved that
graphs with no subdivision isomorphic to a fixed
graph do form such a class.

**4.3 Quadratic dynamical systems**

This is a new research direction initiated by Y. Rabinovich, A. Sinclair
and A. Widgerson during Sinclair's visit to DIMACS.
Quadratic dynamical systems
are a natural class of non-linear stochastic processes that
are used to model various phenomena in the natural sciences,
such as population genetics and the kinetic theory of ideal
gases. Less classically, they also provide an appropriate
framework for the study of genetic algorithms for combinatorial
optimization. In contrast to linear systems, which are well
understood, there is little general theory available for the
quantitative analysis of quadratic systems. Inspired by the
many computational applications of linear stochastic systems
in recent years, Rabinovich, Sinclair
and Widgerson set out to investigate the potential of
their quadratic counterparts.

They established the abstract combinatorial framework of QDSs, which is essential to understanding their computational potential, and derived many of their fundamental properties, such as convergence to a fixed point and the existence of linear invariants. They also posed several intriguing open questions. This work appeared at the IEEE FOCS in 1992 [57]. It has led to further work by several authors (see, e.g., [55, 12, 34]) and remains an active topic of research. One interesting more recent related development which they have been involved in is a quantitative analysis of crossover operators in population genetics [56].

** 4.4 Linkless embeddings of graphs in 3-space**

Robertson, Seymour and Thomas studied linkless embeddings of graphs
in 3-space. A piecewise-linear embedding of a graph
in 3-space is called
* flat* if every circuit of the graph bounds a disk disjoint from the rest
of the graph. They have shown that:

- An embedding is flat if and only if the fundamental group of the complement in 3-space of the embedding of every subgraph is free.
- If two flat embeddings of the same graph are not ambient isotopic,
then they differ on a
subdivision of
*K*_{5}or*K*_{3,3}. - Any flat embedding of a graph can be transformed to any other flat embedding of the same graph by ``3-switches," an analog of 2-switches from the theory of planar embeddings. In particular, any two flat embeddings of a 4-connected graph are either ambient isotopic, or one is ambient isotopic to a mirror image of the other.
- A graph has a flat embedding if and only if it has no minor isomorphic to one of
seven specified graphs. These are the graphs that can be obtained from
*K*_{6}by means of*Y*Delta- and Delta*Y*-exchanges.

Another significant result that was the outcome of the special year is [13], which since then led to very important results in random graphs and random structures in general. In the symmetric, special case of Bernoulli measure on the product space (which was an earlier result of Kahn-Kalai-Linial, FOCS '88), this result states that for every monotone Boolean function on {0, 1}

The work in [13] was fundamental in the work of Friedgut-Kalai [20] which, resolving a conjecture of Nati Linial, established results of the type - every monotone graph property has a sharp threshold. The result in [13] also had applications in learning theory and complexity theory (see e.g. [14]. More recently, Bourgain further generalized such results to monotone Boolean functions (on product spaces) which are not necessarily graph properties.

** 4.6 Hadwiger's conjecture for K_{6}-free graphs**

Robertson, Seymour and Thomas managed to settle the next open case of Hadwiger's conjecture. They have shown that every loopless graph which cannot be contracted onto the complete graph on six vertices is five-colorable. (They were awarded the D. Ray Fulkerson prize for this work).

**5 Criticisms and suggestions for future improvements**

Unlike the previous special year, which was
the first of many special years at DIMACS and
suffered the birth pains of any new enterprise, the 1991/92 Special Year
went rather smoothly. Participants found DIMACS staff courteous
and helpful, and facilities, including computer equipment, more than
adequate. The only criticism the committee has heard was that the
mathematics faculty at Rutgers were too busy to interact with on a regular
basis.

** References**

[1] P. K. Agarwal, N. Alon, B. Aronov and S. Suri, Can visibility graphs be
represented compactly?, Proc. 9^{th} ACM Symp. on Computational
Geometry, ACM Press (1993) 338-347. Also: * Discrete and Computational
Geometry* **12** (1994) 347-365.

[2]
N. Alon, F. R. K. Chung and R. L. Graham, Routing permutations on
graphs via matchings, Proc. 25^{th} ACM Symp. on the Theory of
Computing (STOC), San Diego, CA (1993) 583-591. Also: * SIAM J. Discrete
Math.* ** 7** (1994) 513-530.

[3]
N. Alon, U. Feige, A. Wigderson, D. Zuckerman, Derandomized
graph products, * Computational Complexity* (1995) pp. 60-75.

[4]
N. Alon and D. J. Kleitman,
Piercing convex sets and the Hadwiger Debrunner (*p, q*)-problem,
* Advances in Mathematics* ** 96** (1992) 103-112.

[5]
N. Alon and D. J. Kleitman,
Piercing convex sets (research announcement),
* Bulletin of the AMS* ** 27** (1992) 252-256.

[6]
N. Alon, S. Rajagopalan and S. Suri, Long non-crossing configurations
in the plane, Proc. 9^{th} ACM Symp. on Computational Geometry, ACM
Press (1993), 257-263. Also: * Fundamenta Informaticae* ** 22** (1995)
385-394.

[7]
N. Alon, J. Spencer, and P. Tetali, Covering with Latin
transversals, DIMACS Technical Report ** 91-71**, October 1991,
also * Discrete Applied Math.* ** 57** (1995) 1-10.

[8]
D. Archdeacon, C. P. Bonnington and C.H.C. Little,
An algebraic characterization of planar graphs,
* J. Graph Th.* ** 19-2** (1995) 237-250.

[9]
D. Archdeacon, N. Hartsfield, and C.H.C. Little,
Nonhamiltonian triangulations of large connectivity and
representativity,
* JCTB* ** 68** (1996) 45-55.

[10]
D. Archdeacon, N. Hartsfield, C.H.C. Little, and B. Mohar,
Obstruction sets for outer-projective-planar graphs,
* Ars Combinatoria* (to appear).

[11]
D. Archdeacon, P. Bonnington, N. Dean, and N. Hartsfield,
Obstruction sets for outer-cylindrical graphs, manuscript.

[12]
S. Arora, Y. Rabani and U. Vazirani,
Simulating quadratic dynamical systems is PSpace-complete,
* Proceedings of the 26th Annual ACM Symposium on Theory of Computing*
(1994) pp. 459-467.

[13]
J. Bourgain, J. Kahn, G. Kalai, Y. Katznelson and N. Linial,
The influence of variables in product spaces,
* Israel Jour. Math.* ** 77** (1992) 55-64.

[14]
N.H. Bshouty and C. Tamon, On the Fourier spectrum of monotone functions,
* Jour. of ACM,* ** 43**, (1996), 747-770.

[15]
G. Chen and R. H. Schelp, Graphs with linearly bounded Ramsey numbers,
* J. Combin. Theory Ser. B* ** 57** (1993) 138-149.

[16]
G. Chen and R. H. Schelp, A new game chromatic number,
* Europ. J. Combinatorics* ** 18** (1997) 1-9.

[17]
M. E. Dyer, A. M. Frieze, R. Kannan, A. Kapoor, L. Perkovic and U. Vazirani,
A mildly exponential algorithm for estimating the number of knapsack
solutions.
*Combinatorics, Probability and Computing* ** 2** (1993) 271-284.

[18]
P. Erdos, M. Nathanson, and P. Tetali, Independence of solution
sets and minimal asymptotic bases, * Acta Arithmetica*, ** LXIX.3**
(1995) 243-258.
* JCTB* (submitted).

[20]
E. Friedgut, G. Kalai, Every monotone graph property has a
sharp threshold, Proc. Amer. Math. Soc. 124 (1996), pp. 2993-3002.

[21]
A. M. Frieze, R. M. Karp and B. Reed,
When is the assignment bound asymptotically tight for the asymmetric
traveling-salesman problem?
* SIAM Journal on Computing* ** 24** (1995) 484-493.

[22]
Z. Furedi, F. Lazebnik, A. Seress, V.A. Ustimenko and A.J. Woldar,
Graphs of prescribed girth and bi-degree,
* Journal of Combinatorial Theory*, Ser. ** B**, Vol. 64, No. 2 (1995)
228-239.

[23]
P. Gemmel, R. Lipton, R. Rubinfeld, M. Sudan and A. Wigderson,
Self testing/correcting for polynomials and for approximate functions,
Proc. of the 23rd STOC (May 1991) pp. 32-42.

[24]
J. L. Goldwasser and C. Q. Zhang,
On minimal counterexamples to a conjecture about unique edge-3-coloring,
ConNum (Festscgrift for C. St. J. A. Nash-Williams) 113, (1996) 143-152.

[25]
C. Gotsman and N. Linial, Spectral properties of threshold functions,
* Combinatorica* ** 14** (1994) 35-50.

[26]
J. R. Griggs and Y.-C. Lin,
The maximum sum of degrees above a threshold in planar graphs,
* Discrete Mathematics* in press.

[27]
J. R. Griggs and Y.-C. Lin,
Planar graphs with few
vertices of small degree, * Discrete Mathematics* ** 143**
(1995) 47-70.

[28]
Lenwood S. Heath,
Recognizing undirected and directed leveled-planar graphs,
903rd Meeting of the American Mathematical Society,
Boston, Massachusetts, October 7, 1995.

[29]
Lenwood S. Heath and Sriram V. Pemmaraju,
Recognizing leveled-planar dags in linear time,
{Proceedings of Graph Drawing '95,}
* Lecture Notes in Computer Science *** 1027** (1996) pp. 300-311.

[30]
Lenwood S. Heath and Sriram V. Pemmaraju,
Stack and queue layouts of directed acyclic graphs: Part II,
accepted for publication in * SIAM Journal on Computing*
(1997).

[31]
Lenwood S. Heath, Sriram V. Pemmaraju, and Ann Trenk,
Stack and queue layouts of directed acyclic graphs,
an extended abstract in * Planar Graphs*,
William T. Trotter, editor, American Mathematical Society,
Providence, Rhode Island (1993) pp. 5-11.

[32]
Lenwood S. Heath, Sriram V. Pemmaraju, and Ann Trenk,
Stack and queue layouts of directed acyclic graphs: Part I,
accepted for publication in * SIAM Journal on Computing*
(1997).

[33]
T.-s. Hsu, V. Ramachandran, N. Dean, Implementation of
parallel graph algorithms on the MasPar, Volume 15, DIMACS
Series, pp. 165-198.

[34]
A. Juels,
* Topics in black-box combinatorial optimization*,
PhD Thesis, Computer Science Division, UC Berkeley, 1996.

[35]
M. Karchmer, I. Newman, M. Saks, A. Wigderson, Non-deterministic
communication complexity with few witnesses, 7th Structures in Complexity
Theory Conference (1992) pp. 275-281.

[36]
M. Karchmer, I. Newman, M. Saks, A. Wigderson, Non-deterministic
communication complexity with few witnesses,
* JCSS*, Vol 49, No. 2 (1994).

[37]
M. Karchmer, A. Wigderson, On Span Programs, Proc. of the 8th
Structures in Complexity conference (1993) pp. 102-111.

[38]
M. Karchmer, A. Wigderson, On characterizing
nondeterministic circuit size, Proc. of the 25th STOC (1993) pp. 532-545.

[39]
H.A. Kierstead and W.T. Trotter, Planar graph coloring with uncooperative
partner, * J. of Graph Theory* ** 18** (1994) 569-584.

[40]
F. Lazebnik, V.A. Ustimenko and A.J. Woldar,
New constructions of bipartite graphs on * m, n* vertices, with
many edges, and without small cycles, * Journal of Combinatorial Theory*,
Series ** B**, vol. 61, No. 1 (1994) pp. 111-117.

[41]
F. Lazebnik, V.A. Ustimenko and A.J. Woldar,
Properties of certain families of *2k*-cycle free graphs,
* Journal of Combinatorial Theory*,
Series ** (B)**, ** 60**, No. 2 (1994)
pp. 293-298.

[42]
F. Lazebnik, V.A. Ustimenko and A.J. Woldar,
A new series of dense graphs of high girth,
* Bulletin of the AMS*, Volume 32, Number 1 (1995) 73-79.

[43]
F. Lazebnik, V.A. Ustimenko and A.J. Woldar, A characterization of
the components of the graphs *D(k, q)*,
* Discrete Mathematics* ** 157** (1996) 271-283.

[44]
F. Lazebnik, V.A. Ustimenko and A.J. Woldar,
New upper bounds on the order of cages, * Electronic Journal of
Combinatorics*, v. 14, R13 (1997) 1-11.

[45]
F. Lazebnik, V.A. Ustimenko and A.J. Woldar,
Polarities and *2k*-cycle-free graphs, submitted.

[46]
F. Lazebnik, P. Wang, On the structure of extremal graphs of high
girth,
to appear in the * Journal of Graph Theory*.

[47]
Y.-C. Lin, Planar graphs with few vertices of small degree
Ph.D. Dissertation (1993) University of South Carolina, Columbia, SC.

[48]
N. Linial, E. London and Y. Rabinovich,
The geometry of graphs and some of its algorithmic applications,
* Combinatorica* ** 15** (1995) 215-245.

[49]
N. Linial and M. Saks, Low diameter graph decompositions,
* Combinatorica* ** 13** (1993) 441-454.

[50]
L. Lovasz, I. Newman, M. Naor, A. Wigderson, * Search Problems in
the Decision Tree Model*, Proc of the 32nd FOCS conference,
(1991) pp. 576-585.

[51]
M. Luby, B. Velickovic and A. Wigderson, Deterministic approximate
counting of depth-2 circuits, Proc. of the 2nd ISTCS (Israeli
Symposium on Theoretical Computer Science) (1993) pp. 18-24.

[52]
N. Nisan, E. Szemeredi, A. Wigderson, Undirected connectivity
in *O*(log^{1.5}*n*) space, Proc. of the 33rd FOCS conference (1992).

[53]
R. Ostrovski and A. Wigderson, Nontrivial zero-knowledge implies
one-way functions, Proc. of the 2nd ISTCS (1993) pp. 3-17.

[54]
A. Policriti and P. Tetali, On The satisfiability problem for the
ground case of first order theories, DIMACS Technical Report ** 92-38**,
August 1992.

[55]
P. Pudlak,
Complexity theory and genetics,
* Proceedings of the 9th Annual IEEE Symposium on Structure in
Complexity Theory* (1994) pp. 383-395.

[56]
Y. Rabani, Y. Rabinovich and A.J. Sinclair,
A computational view of population genetics,
* Proceedings of the 27th ACM Symposium on Theory of Computing*,
May 1995, pp. 83-92. Accepted for publication in
* Random Structures and Algorithms*.

[57]
Y. Rabinovich, A.J. Sinclair and A. Wigderson,
Quadratic dynamical systems,
* Proceedings of the 33rd IEEE Symposium on Foundations of
Computer Science* (1992) pp. 304-313.
(Extended version in preparation.)

[58]
V. Ramachandran and J. Reif, Planarity testing in parallel,
* J. Comput. System Sci.* ** 49** (1994) 517-561.

[59]
A. Razborov, E. Szemeredi, A. Wigderson, Constructing small
sets that are uniform in arithmetic progressions, * Probability,
Combinatorics and Complexity*, Vol. 2 (1993) pp. 513-518.

[60]
A. Razborov and A. Wigderson, *n*^{Omega(log n)} lower
bounds on the size of depth 3 threshold circuits with AND gates at the
bottom, IPL, Vol. 45 (1993) pp. 303-307.

[61]
N. Robertson, P. D. Seymour and R. Thomas,
Hadwiger's conjecture for *K*_{6}-free graphs,
* Combinatorica* **13** (1993) 279-361.

[62]
N. Robertson, P. D. Seymour and R. Thomas,
Kuratowski chains,
* J. Combin.\ Theory Ser.\ B* ** 64** (1995) 127-154.

[63]
N. Robertson, P. D. Seymour and R. Thomas,
Petersen family minors,
* J. Combin.\ Theory Ser.\ B* **64** (1995) 155-184.

[64]
N. Robertson, P. D. Seymour and R. Thomas,
Sach's linkless embedding conjecture,
* J. Combin.\ Theory Ser.\ B* **64** (1995) 185-227.

[65]
V. Rodl and R. Thomas,
Arrangeability and clique subdivisions,
In: * The Mathematics of Paul Erdos*,
R. L. Graham and J. Nesetril eds., Springer-Verlag, New York 1997.

[66]
A.J. Sinclair,
Improved bounds for mixing rates of Markov chains and multicommodity flow,
* Combinatorics, Probability and Computing* **1** (1992) pp. 351-370.

[67]
A.J. Sinclair,
Randomised algorithms,
for counting and generating combinatorial structures,
* Advances in Theoretical Computer Science*,
Birkhauser, Boston, 1993.

[68]
P. Tetali and P. Winkler, Simultaneous reversible Markov chains,
* Combinatorics, Paul Erdos is Eighty *, ** Vol. 1**,
Keszthely, Hungary (1993) 433-451.

[69]
D.B. West and T.G. Will,
Vertex degrees in planar graphs,
* DIMACS Series in Discrete Mathematics and Theoretical Computer
Science* ** 9** (1993) 139-149.

[70]
A. Wigderson, D. Zuckerman, Expanders that beat the
eigenvalue bound, explicit construction and applications, Proc. of
the 25th STOC (1993) pp. 245-251.

DIMACS home page

Contacting the Center

Document last modified on May 6, 1998.