Combinatorics Seminar

Graduate Center,
CUNY

The combinatorics seminar covers a wide range of topics in combinatorics and graph theory with particular emphasis on algorithms and areas related to computer science. Many of the speakers are CUNY and NYU visitors, postdocs, and graduate students. A seminar talk may cover original research or report on an interesting paper. The seminar is run by Janos Pach

The seminar meets on Wednesdays at 6:30 p.m. in room 6417 of the new building of the Graduate Center, 365 Fifth Avenue (at the corner of 34th Street), New York. it can be easily approached by subway, using the B,D,F,N,Q,R, or 6 trains.

Upcoming events

February 6, 2008, Florian Lengyel, CUNY Graduate Center
Probabilistic and enumerative combinatorics of almost injective functions and random matchings in hypergraphs
February 13, 2008, Dan Cranston, DIMACS and Bell Labs
Antimagic labelings of regular bipartite graphs: An application of the Marriage Theorem
February 27, 2008, Esther Ezra, Duke University
On the union of cylinders
March 12, 2008, Geza Toth, Renyi Institute
The Erdos-Szekeres theorem with forbidden order types
March 19, 2008, Gabor Kun, Simon Fraser University, Burnaby
Cops and robbers in random graphs
April 2, 2008, Micha Sharir, Tel Aviv University and NYU
Weak epsilon nets, Davenport-Schinzel sequences, and other recent surprizes
April 9, 2008, Wal Wallis, Southern Illinois University, Carnondale
Properly separated permutations
April 30, 2008, Visualization Day at City College, CUNY
140th St. at Convent Av., 10 a.m. Details
May 14, 2008, Alexey Glazyrin, University of Texas, Brownsville
Anti-Durer conjecture for nonconvex polytopes

Past attractions

FALL 2007

September 5, 2007, Boris Aronov, Polytechnic University, Brooklyn
A generali zation of magic squares with applications to digital halftoning
September 19, 2007 Boris Bukh, Princeton University
Non-trivial solutions to a symmetric linear equation in integers
October 3, 2007 Peter Brass, City College, CUNY
Searching a target in a grid graph
October 10, 2007, Maria Chudnovsky, Columbia University
Even pairs in Berge graphs
October 17, 2007, Alfred Inselberg, Tel Aviv University
Multidimensional visualization and its applications
October 24, 2007, Dan Ismailescu, Hofstra University
Circumscribed polygons of small area
October 31, 2007, Po-Shen Loh, Princeton University
Avoiding small subgraphs in Achlioptas processes
November 7, 2007, Joel Spencer, Courant Institute, NYU
The Erdos-Renyi phase transition
December 12, 2007, Student Presentations
Ben Baumer, Pete Terlecky
December 19, 2007, Adrian Dumitrescu, University of Wisconsin, Milwaukee
On distinct distances among points

SPRING 2007

February 14, 2007, Jon Lenchner, IBM T.J. Watson Research Center, Yorktown Heights
New proof of a theorem of Csima and Sawyer concerning ordinary points in line arrangements
March 7, 2007, Daniel Stefankovic, University of Rochester
Adaptive annealing: A near-optimal connection between sampling and counting
March 28, 2007, Jan Vondrak, Princeton University
Embedding trees in pseudorandom graphs
April 11, 2007, Imre Barany, Renyi Institute, Budapest and University College London
Paths with no small angle
April 12, 2007, Thursday 4:15pm, Assaf Naor, Courant Institute, NYU
The story of the Sparsest Cut Problem (in rm. 9204!)
April 25, 2007, Panagiotis Cheilaris, CUNY Graduate Center
Conflict-free coloring for geometric hypergraph
May 2, 2007, Jacob Fox, Princeton University
Induced Ramsey-type theorems
May 9, 2007, Ferran Hurtado, Univ. Politecnica de Catalunya,
Squares!

FALL 2006

September 13, 2006 Raghavan Dhandapani, Courant Institute, NYU
Greedy embeddings of planar triangulations
September 20, 2006 Geza Toth, Renyi Institute, Hungarian Academy
Drawing graphs with few slopes
September 21, Thursday, 4:15pm!!! Benny Sudakov, Princeton University and IAS
Additive approximation for edge-deletion problems, at the CUNY Graduate Center, 365 Fifth Ave., rm 9204/9205!!!
September 27, 2006 Boris Bukh, Princeton University
Induced subgraphs of Ramsey graphs with many distinct degrees
October 11, 2006 Rados Radoicic, Baruch College, CUNY
The discharging method and its applications for graph drawing
October 12, Thursday, 4:15pm!!!Maria Chudnovsky, Columbia University and Clay Math. Institute
Testing for a theta
October 18, 2006 John Iacono, Polytechnic University, Brooklyn
Necklaces, convolutions, and X+Y
November 1, 2006 Amitai Perlstein, Technion, Haifa
Sylvester-Gallai type theorems for pseudoparabolas
November 8, 2006 Olivier Bernardi, Centre de Recerca Matematica, Barcelona
Bijective decomposition of tree-rooted maps
November 29, 2006 Amit Agarwal, Princeton University
Undecidable statements and the zero-one law in random geometric graphs

SPRING 2006

February 8, 2006 Po-Shen Loh, Princeton University
Independent transversals in locally sparse graphs
February 15, 2006 Nir Y Ailon, Princeton University
Ranking and clustering: aggregating inconsistent information
February 22, 2006, at 3 p.m. in room 1314 Courant Institute!!! Shakhar Smorodinsky, Courant Institute, NYU
The k-set problem
February 22, 2006 Tudor Zamfirescu, Universitat Dortmund
Pushing bodies through holes
March 1, 2006 Geza Toth, Renyi Institute, Budapest
Degenerate crossing numbers of graphs
March 15, 2006 Jonathan Lenchner, IBM T.J. Watson Research Center, Yorktown Heights
Ordinary points in the Euclidean and projective planes
March 22, 2006 Rados Radoicic, Rutgers University, New Brunswick
Old and new directions in Ramsey theory on integers
April 26, 2006 Pankaj K. Agarwal, Duke University, Durham
Robust shape fitting via peeling and grating coresets
May 3, 2006 Peter Brass, City College, CUNY
Problems and results on data structures

FALL 2005

September 14, 2005 Jacob Fox, MIT, Cambridge
A bipartite analogue of Dilworth's theorem
September 21, 2005 Andres Varon, CUNY Graduate Center
On the empty hexagon theorem
September 28, 2005 Raghavan Dhandapani, Courant Institute, NYU
The halving line problem
October 5, 2005 Joel Ratsaby, Ben Gurion University of the Negev
On the combinatorial complexity of constrained Vapnik-Chervonenkis classes
October 19, 2005 Arman Artuc, CUNY Graduate Center
Simultaneous embeddings of planar graphs
October 26, 2005 Edgar Troudt, CUNY Graduate Center
Geometric graphs have arbitrarily large geometric thickness
November 2, 2005 Panos Hilaris, CUNY Graduate Center
Some remarks on online conflict-free coloring for intervals
November 16, 2005 Amitava Bhattacharya, University of Illinois at Chicago
The alternating cone of a 2-colored graph
November 30, 2005 Jan Vondrak, Microsoft, Redmond
Ramsey-type results for the hypercube
December 7, 2005 Marisa Debowsky, Courant Institute, NYU
A characterization of projective-planar signed graphs

SPRING 2005

March 2, 2005 Jacob Fox, M.I.T., Cambridge
Independence in Euclidean Ramsey Theory
March 9, 2005 David Galvin, Institute for Advanced Study, Princeton
Entropy and graph homomorphisms
March 16, 2005 Tibor Szabo, ETH Zurich
Random walk on oriented hypercubes
March 23, 2005 Adrian Dumitrescu, University of Wisconsin, Milwaukee
Sliding disks in the plane
May 4, 2005 Jan Vondrak, M.I.T., Cambridge
Boosted sampling and minimum spanning trees
May 11, 2005 Gabor Tardos, Renyi Institute, Budapest
T.B.A.

FALL 2004

September 22, 2004 Joshua Cooper, Courant Institute, NYU
Generalized de Bruijn Cycles
September 29 - October 2, 2004 Graph Drawing 04, Steinman Hall, City College, CUNY
12th International Symposium on Graph Drawing
October 20, 2004 Raghavan Dhandapani, Courant Institute, NYU
On Edge Guarding a Planar Graph
October 27, 2004 John Iacono, Polytechnic University, Brooklyn
O(loglogn)-competitive Binary Search Trees
November 3, 2004 Rados Radoicic, Rutgers University, New Brunswick
Iterative Processes in the Plane
November 17, 2004 Shakhar Smorodinsky, ETH Zurich and New York University
On-Line Conflict-Free Coloring

SPRING 2003

February 5, 2003 Amit Chakrabarti, Institute for Advanced Study, Princeton
Informational complexity and lower bounds in communication complexity
February 19, 2003 Peter Brass, City College, CUNY
On testing congruence of higher-dimensional point sets
March 5, 2003 James Abello, DIMACS, Rutgers University
Massive graph mining
March 19, 2003 Geza Toth, Renyi Institute, Budapest
Conflict-free coloring
March 26, 2003 Amotz Bar-Noy, Brooklyn College and Graduate Center
The windows scheduling problem
April 2, 2003 Laura Heinrich-Litan, Technische Universitat Braunschweig
Nearest neighbor search in high dimensions
April 9, 2003 Rom Pinchasi , M.I.T. Cambridge, MA
The number of directions determined by n points in space
April 15, 2003 ON TUESDAY!!! Bilal Khan, CUNY Graduate Center
Whitehead's graph: automorphic conjugacy in the free group of rank 2
May 7, 2003 Adrian Dumitrescu, University of Wisconsin
Monotone paths in line arrangements with a small number of directions

FALL 2002

September 18, 2002 Peter Brass, City College, CUNY
Geometry with coins
September 25, 2002 Micha Sharir, Tel Aviv University
Incidences and related problems
October 9, 2002 Geza Toth, Renyi Institute, Budapest
An Erdos-Szekeres type problem in the plane
October 23, 2002 Stefan Burr, City College, CUNY
Equal sums of cubes
October 30, 2002 Rados Radoicic, MIT, Cambridge
Graphs drawn with at most 3 crossings per edge
November 13, 2002 Joseph Malkevitch, York College, CUNY
Robot arms, polygons, and rigidity
November 20, 2002 Sergio Cabello, Universiteit Utrecht
Testing homotopy for paths in the plane
December 4, 2002 Anupam Gupta, Bell Laboratories
Algorithmic applications of metric embeddings

SPRING 2002

February 6, 2002 Jozsef Balogh AT&T
Monoton graph properties
February 13, 2002 Sanjoy Dasgupta AT&T
An algorithm for clustering high-dimensional data
February 28, 2002, 4p.m. in room 9204 (special date and place!) Noga Alon Tel Aviv University and I.A.S., Princeton
Testing graph properties
March 6, 2002 Ayman Khalfalah Rutgers University
Ramsey-type problems in combinatorial number theory
March 13, 2002 Zoltan Furedi University of Illinois and Hungarian Academy of Sciences
Identifying codes
March 20, 2002 Martin Anthony London School of Economics
Combinatorial measures of expressive power in computational learning theory
April 3, 2002 Peter Brass Freie Universitat Berlin
On finding symmetries and related algorithmic problems
April 10, 2002 Yi Zhao Rutgers University
Proof of a tiling conjecture of Komlos
April 17, 2002 Amit Chakrabarti Princeton University
Minor-closed graph properties are evasive

FALL 2001

October 10, 2001 Micha Sharir Tel Aviv University
Union of geometric objects
October 24, 2001 Rados Radoicic M.I.T., Cambridge, MA
The chromatic number of 3-space
November 7, 2001 Herve Bronnimann Polytechnic University, Brooklyn
Enumerating pseudo-triangulations
November 21, 2001, 5:30pm (!) Nick Wormald Melbourne University, Australia
Models of random regular graphs
November 28, 2001 Mario Szegedy Rutgers University, New Brunswick
Quantum lower bounds by dualization
December 12, 2001, 5:30pm (!) Roy Meshulam Institute for Advanced Study, Princeton
Group algebras, expanders and codes

SPRING 2001

January 31, 2001 Igor Shparlinski Macquarie University, Sydney
Set proportionality testing
February 7, 2001 Igor Pak M.I.T., Cambridge, MA
Invariants of ribbon tiles
February 14, 2001 Jim Cox and Dan Karron Brooklyn College, CUNY and Computer Aided Surgery, Inc.
Topological zone organization of scalar volume data
February 21, 2001 Gary Gordon Lafayette College and DIMACS
The beta invariant and antimatroids
March 7, 2001 Clifford Smyth Rutgers University, New Brunswick
Equilateral sets
March 21, 2001 Jozsef Solymosi ETH Zurich
Square triples in dense grids
March 28, 2001 Jesus De Loera UC Davis, CA
Counting network flows
May 2, 2001 Ariel Halpert CUNY Graduate Center
Sums over k-term compositions
May 4 (Friday) 2001 The Goodman-Pollack Two-thirds-of-a-century Fest at Courant Institute, 251 Mercer Street, Rm. 109
Featuring G. Kalai (Jerusalem), R. Wenger (Columbus), L. Lovasz (Microsoft), P. Agarwal (Duke)

FALL 2000

September 13, 2000 Dan Ismailescu Courant Institute, NYU,
Minimizer graphs for a class of extremal problems
September 20, 2000 Florian Lengyel CUNY Graduate Center,
New proof of a theorem on recurrence relations
September 27, 2000 Michael Krivelevich Tel Aviv University,
Graph coloring in expected polynomial time
October 11, 2000 Bill Steiger Rutgers University,
Depth
October 18, 2000 Joe Malkevitch CUNY York College,
Pancakes, parallel computation, and genome rearrangement
October 25, 2000 Rom Pinchasi Hebrew University, Jerusalem,
New results about circles in the plane
November 1, 2000 Bernardo Abrego and Silvia Fernandez Merchant Rutgers University, New Brunswick,
Unit distances among vertices of a convex polygon
November 8, 2000 Gabor Tardos Renyi Institute, Budapest,
k-sets in 2 and 3 dimensions
December 6, 2000 Bruce Reed CNRS, Paris,
Graph colouring via the probabilistic method

SPRING 2000

May 10, 2000 Peter Brass Freie Universitat, Berlin,
Matching point patterns
May 3, 2000 Katherine St. John, Lehman College, CUNY,
Games on random structures
April 12, 2000 Geza Toth, M. I. T.,
New bounds on crossing numbers
April 5, 2000 Bernardo Abrego and Silvia Fernandez Merchant, Rutgers University, New Brunswick
On the structure of point sets containing many similar copies of a given pattern
March 29, 2000 Alex Samorodnitsky, Institute for Advanced Study, Princeton,
On the optimum of Delsarte's linear program
March 8, 2000 Benny Sudakov, Princeton University,
Acyclic edge colorings of graphs
March 1, 2000 Eldar Fischer, NEC Research Institute, Princeton,
Graph embedding problems -- Methods and applications
February 23, 2000 Joel Spencer, Courant Institute, New York University,
Random processes
February 16, 2000 Alexander K. Kelmans, DIMACS, Rutgers University, NJ
Optimal packing of induced stars in a graph
February 9, 2000 Rom Pinchasi, Hebrew University, Jerusalem
Application of allowable sequences to plane geometry

FALL 1999

December 8, 1999 Ron Holzman, M.I.T. and Technion (Haifa)
The majority action on infinite graphs: strings and puppets
November 17, 1999 Stefan Burr, City College, CUNY
The Ramsey arrow and the polynomial hierarchy
November 10, 1999 Gabor Tardos, DIMACS and Hungarian Academy of Science
Linear hash functions
November 3, 1999 Bilal Khan, CUNY Graduate Center
Graphs, free groups, and the Hanna Neumann Conjecture
October 27, 1999 Gary Bloom, City College, CUNY
Some encouraging new negative results on graceful graphs
October 20, 1999 Richard Pollack, Courant Institute, NYU
ETR and some elementary geometric problems
October 6, 1999 Michael Anshel, City College, CUNY
Constructing public key cryptosystems via combinatorial group theory
September 29, 1999 Mario Szegedy, Institute for Advanced Study, Princeton
Testing first order graph properties
September 22, 1999 Dan Ismailescu, Courant Institute, NYU
Illuminating a convex polygon by floodlights
September 15, 1999 Ariel Halpert, CUNY Graduate Center
Cellular telephone networks and random maps in hypergraphs