Graphs and Geometry is a workshop intended for researchers working in all aspects of graph theory related to geometrical issues and in discrete geometry. The scope of the workshop includes but is not limited to planarity issues, embeddings on surfaces of higher genus, intersection and visibility representations of graphs, geometric graphs, and higher- dimensional analogues of planarity.
The workshop takes place at DIMATIA Center and the Department of Applied Mathematics of Charles University which is located in a historic buildingc in the center of Old Prague.
Let us note that our workshop is not intended to be a competition to Graph Drawing '97; in fact, we expect many participants will continue to Roma on Wednesday September 17, 1997.
We plan mainly long invited lectures followed by informal discussions. The speakers that tentatively agreed to deliver invited lectures are Victor Klee (Seattle), Robin Thomas (Atlanta), Janos Pach (New York) and Hubert de Fraysseix (Paris). Participants should not feel obliged to deliver contributing talks; however, there certainly will be time for some in case of interest.
The participants will be accommodated in student dorms serving as summer hotels during the summer break. This is a cheap but modest lodging (cca $10 per night).
A conference fee of $30 will be charged as a contribution towards the organizational costs and refreshments.
The conference is partly supported by Czech-US Science and Technology Research grant No 94051.
10:00-11:00 Victor Klee (Seattle): The Hirsch conjecture after forty years I
11:30-12:30 Robin Thomas (Atlanta): Permanents, Pfaffian orientations, and even directed circuits I
Monday Sept. 15
10:00-11:00 Janos Pach (New York): On the intersection structure of systems of segments I
11:30-12:30 Victor Klee II
14:00-16:00 Hubert de Fraysseix (Paris): Representations of planar graphs
Tuesday Sept. 16
10:00-11:00 Janos Pach II
11:30-12:30 Robin Thomas II
With D(d,n) denoting the maximum edge-diameter of (convex) d-polytopes with n facets, the Hirsch conjecture asserts that always D(d,n) <= n-d. Its special case, the d-step conjecture, asserts that always D(d,2d) = d. For various special classes of polytopes that arise in combinatorial optimization, these conjectures have been proved for all d and n. However, in the general case, the Hirsch conjecture is known only for d <= 3 and the d-step conjecture only for d <= 5, and that has been the situation for the past 30 years. By now, there are several bets concerning the ultimate fate of the conjectures, and they stand as the most important unsolved problems concerning the combinatorial structure of convex polytopes. Though the conjectures are still unsettled, there has been some recent progress on the behavior of the function D(.,.) and some related functions. This lecture will provide a survey of both older and more recent developments.
Robin Thomas (Atlanta): Permanents, Pfaffian orientations, and even directed circuits
Given an n by n 0-1 matrix A, when can some of the 1's be changed to -1's in such a way that the permament of A equals the determinant of the modified matrix? When does a real n by n matrix A have the property that every real matrix B with the same sign pattern (that is, the corresponding entries either have the same sign, or are both zero) is non-singular? When is a hypergraph with n vertices and n hyperedges minimally non-bipartite? When does a bipartite graph have a "Pfaffian orientation"? Given a digraph, does it have a directed circuit of even length? Given a digraph, does it have a subdivision with no even directed circuit? It is known that all the above problems are equivalent. We prove a structural characterization of the feasible instances, which implies a polynomial-time algorithm to solve all of the above problems. The structural characterization says, roughly speaking, that a bipartite graph has a Pfaffian orientation if and only if it can be obtained by piecing together (in a specified way) planar bipartite graphs and one sporadic non-planar bipartite graph. This is joint work with Neil Robertson and P.D. Seymour. The structural characterization was independently obtained by W. McCuaig.