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₅ 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₆ by means of YDelta- and DeltaY-exchanges.

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₆-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. [19] G. Fan and C. Q. Zhang, Circuit decompositions of Eulerian graphs, 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.5n) 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₆-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