- You are here:
- GT Home
- Home
- News & Events

Series: Graph Theory Seminar

A map is a connected graph G embedded in a surface S (a closed 2-manifold) such that all components of S -- G are simply connected regions. A map is rooted if an edge is distinguished together with a direction on the edge and a side of the edge. Maps have been enumerated by both mathematicians and physicists as they appear naturallyin the study of representation theory, algebraic geometry, and quantum gravity.In 1986 Bender and Canfield showed that the number of n-edgerooted maps on an orientable surface of genus g is asymptotic tot_g n^{5(g-1)/2}12n^n, (n approachces infinity),where t_g is a positive constant depending only on g. Later it wasshown that many families of maps satisfy similar asymptotic formulasin which tg appear as \universal constants".In 1993 Bender et al. derived an asymptotic formula for the num-ber of rooted maps on an orientable surface of genus g with i facesand j vertices. The formula involves a constant tg(r) (which plays thesame role as tg), where r is determined by j=i.In this talk, we will review how these asymptotic formulas are obtained using Tutte's recursive approach. Connections with random trees, representation theory, integrable systems, Painleve I, and matrix integrals will also be mentioned. In particular, we will talk aboutour recent results about a simple relation between tg(r) and tg, and asymptotic formulas for the numbers of labeled graphs (of various connectivity)of a given genus. Similar results for non-orientable surfaces will also be discussed.

Series: Graph Theory Seminar

A graph G contains a graph H as a minor if a graph isomorphic to H can be obtained from a subgraph of G bycontracting edges. One of the central results of the rich theory of graph minors developed by Robertson and Seymour is an approximate description of graphs that do not contain a fixed graph as a minor. An exact description is only known in a few cases when the excluded minor is quite small.In recent joint work with Robin Thomas we have proved a conjecture of his, giving an exact characterization of all large, t-connected graphs G that do not contain K_t, the complete graph on t vertices, as a minor. Namely, we have shown that for every integer t there exists an integer N=N(t) such that a t-connected graph G on at least N vertices has no K_t minor if and only if G contains a set of at most t- 5 vertices whose deletion makes G planar. In this talk I will describe the motivation behind this result, outline its proof and mention potential applications of our methods to other problems.

Series: Graph Theory Seminar

A fundamental question in topological graph theory is as follows: Given a surface S and an integer t > 0, which graphs drawn in S are t-colorable? We say that a graph is (t+1)-critical if it is not t-colorable, but every proper subgraph is. In 1993, Carsten Thomassen showed that there are only finitely many six-critical graphs on a fixed surface with Euler genus g. In this talk, I will describe a new short proof of this fact. In addition, I will describe some structural lemmas that were useful to the proof and describe a list-coloring extension that is helpful to ongoing work that there are finitely many six-list-critical graphs on a fixed surface. This is a joint project with Ken-ichi Kawarabayashi of the National Institute of Informatics, Tokyo.

Series: Graph Theory Seminar

Several interesting models of random partial orders can be described via a
process that builds the partial order one step at a time, at each point
adding a new maximal element. This process therefore generates a linear
extension of the partial order in tandem with the partial order itself. A
natural condition to demand of such processes is that, if we condition on
the occurrence of some finite partial order after a given number of steps,
then each linear extension of that partial order is equally likely. This
condition is called "order-invariance".
The class of order-invariant processes includes processes generating a
random infinite partial order, as well as those that amount to taking a
random linear extension of a fixed infinite poset.
Our goal is to study order-invariant processes in general. In this talk, I
shall focus on some of the combinatorial problems that arise.
(joint work with Malwina Luczak)

Series: Graph Theory Seminar

A graph G is k-critical if every proper subgraph of G is (k-1)-colorable, but the graph G itself is not. We prove that every k-critical graph on n vertices has a cycle of length at least logn/100logk, improving a bound of Alon, Krivelevich and Seymour from 2000. Examples of Gallai from 1963 show that this bound is tight (up to a constant depending on k). We thus settle the problem of bounding the minimal circumference of k-critical graphs, raised by Dirac in 1952 and Kelly and Kelly in 1954. This is joint work with Robin Thomas.

Series: Graph Theory Seminar

The Jacobian of a graph, also known as the Picard Group, Sandpile Group, or Critical Group, is a discrete analogue of the Jacobian of an algebraic curve. It is known that the order of the Jacobian of a graph is equal to its number of spanning trees, but the exact structure is known for only a few classes of graphs. In this talk I will present a combinatorial method of approaching the Jacobian of graphs by way of a chip-firing game played on its vertices. We then apply this chip-firing game to explicitly characterize the Jacobian of nearly complete graphs, those obtained from the complete graph by deleting either a cycle or two vertex-disjoint paths incident with all but one vertex. This is joint work with Sergey Norin.

Series: Graph Theory Seminar

In 1865, Sylvester posed the following problem: For a region R in the plane,let q(R) denote the probability that four points chosen at random from Rform a convex quadrilateral. What is the infimum q* of q(R) taken over allregions R? The number q* is known as Sylvester's Four Point Problem Constant(Sylvester's Constant for short). At first sight, it is hard to imagine howto find reasonable estimates for q*. Fortunately, Scheinerman and Wilf foundthat Sylvester's Constant is intimately related to another fundamentalconstant in discrete geometry. The rectilinear crossing number of rcr(K_n)the complete graph K_n is the minimum number of crossings of edges in adrawing of K_n in the plane in which every edge is a straight segment. Itis not difficult to show that the limit as n goes to infinity ofrcr(K_n)/{n\choose 4} exists; this is the rectilinear crossing numberconstant RCR. Scheinerman and Wilf proved a surprising connection betweenthese constants: q* = RCR. Finding estimates of rcr(K_n) seems like a moreapproachable task. A major breakthrough was achieved in 2003 by Lovasz,Vesztergombi, Wagner, and Welzl, and simultaneously by Abrego andFernandez-Merchant, who unveiled an intimate connection of rcr(K_n) withanother classical problem of discrete geometry, namely the number of

Series: Graph Theory Seminar

A metric graph is a geometric realization of a finite graph by identifying each edge with a real interval. A divisor on a metric graph Gamma is an element of the free abelian group on Gamma. The rank of a divisor on a metric graph is a concept appearing in the Riemann-Roch theorem for metric graphs (or tropical curves) due to Gathmann and Kerber, and Mikhalkin and Zharkov. A rank-determining set of a metric graph Gamma is defined to be a subset A of Gamma such that the rank of a divisor D on Gamma is always equal to the rank of D restricted on A. I will present an algorithm to derive the reduced divisor from any effective divisor in the same linear system, and show constructively that there exist finite rank-determining sets. Based on this discovery, we can compute the rank of an arbitrary divisor on any metric graph. In addition, I will discuss the properties of rank-determining sets in general and formulate a criterion for rank-determining sets.

Series: Graph Theory Seminar

This is the third session in this series and a special effort will be made to make it self contained ... to the fullest extent possible.With Felsner and Li, we proved that the dimension of the adjacency poset of a graph is bounded as a function of the genus. For planar graphs, we have an upper bound of 8 and for outerplanar graphs, an upper bound of 5. For lower bounds, we have respectively 5 and 4. However, for bipartite planar graphs, we have an upper bound of 4, which is best possible. The proof of this last result uses the Brightwell/Trotter work on the dimension of thevertex/edge/face poset of a planar graph, and led to the following conjecture:For each h, there exists a constant c_h so that if P is a poset of height h and the cover graph of P is planar, then the dimension of P is at most c_h.With Stefan Felsner, we have recently resolved this conjecture in the affirmative. From below, we know from a construction of Kelly that c_h must grow linearly with h.

Series: Graph Theory Seminar

We will discuss the classic theorem of Walter Schnyder: a graph G is planar if and only if the dimension of its incidence poset is at most 3. This result has been extended by Brightwell and Trotter to show that the dimension of the vertex-edge-face poset of a planar 3-connected graph is 4 and the removal of any vertex (or by duality, any face) reduces the dimension to 3. Recently, this result and its extension to planar multigraphs was key to resolving the question of the dimension of the adjacency poset of a planar bipartite graph. It also serves to motivate questions about the dimension of posets with planar cover graphs.