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

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.

Series: Graph Theory Seminar

Slightly modifying a quote of
Paul Erdos: The problem for graphs we
solve this week. The corresponding problem
for posets will take longer.
As one example, testing a graph to determine
if it is planar is linear in the number of
edges. Testing an order (Hasse) diagram to
determine if it is planar is NP-complete.
As a second example, it is NP-complete
to determine whether a graph is a cover
graph.
With these remarks in mind, we present
some results, mostly new but some classic,
regarding posets with planar cover graphs
and planar diagrams. The most recent
result is that for every h, there is 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.

Series: Graph Theory Seminar

We study several parameters of cubic graphs with large girth. In particular, we prove that every n-vertex cubic graph with sufficiently large girth satisfies the following:

- has a dominating set of size at most 0.29987n (which improves the previous bound of 0.32122n of Rautenbach and Reed)
- has fractional chromatic number at most 2.37547 (which improves the previous bound of 2.66881 of Hatami and Zhu)
- has independent set of size at least 0.42097n (which improves the previous bound of 0.41391n of Shearer), and
- has fractional total chromatic number arbitrarily close to 4 (which answers in the affirmative a conjecture of Reed). More strongly, there exists g such that the fractional total chromatic number of every bridgeless graph with girth at least g is equal to 4.

The presentation is based on results obtained jointly with Tomas Kaiser, Andrew King, Petr Skoda and Jan Volec.