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

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.

Series: Graph Theory Seminar

Richter and Salazar conjectured that graphs that are critical for a fixed crossing number k have bounded bandwidth. A weaker well-known conjecture of Richter is that their maximum degree is bounded in terms of k. We disprove these conjectures for every k >170, by providing examples of k-crossing-critical graphs with arbitrarily large maximum degree, and explore the structure of such graphs.

Series: Graph Theory Seminar

A well know theorem of Kuratowski states that a graph is planar graph iff it contains no TK_5 or TK_{3,3}. In 1970s Seymour conjectured that every 5-connected nonplanar graph contains a TK_5. In the talk we will discuss several special cases of the conjecture, for example the graphs containing K_4^- (K_4 withour an edge). A related independent paths theorem also will be covered.

Series: Graph Theory Seminar

I will discuss some new results, as well as new interpretations of some old results, concerning reduced divisors (a.k.a. G-parking functions) on graphs, metric graphs, and tropical curves.

Series: Graph Theory Seminar

Many results in asymptotic extremal combinatorics are obtained using just a handful of instruments, such as induction and Cauchy-Schwarz inequality. The ingenuity lies in combining these tools in just the right way. Recently,
Razborov developed a flag calculus which captures many of the available techniques in pure form, and allows one, in particular, to computerize the search for the right combination. In this talk we outline the general approach and describe its application to the conjecture that a digraph with minimum outdegree n/3 contains a directed triangle. This special case of the Caccetta-Haggkvist conjecture has been extensively investigated in the past. We show that a digraph with minimum outdegree a*n contains a directed triangle for a = 0.3465. The proof builds on arguments used to establish previously known bounds, due to Shen from 1998 (a = 0.3542) and Hamburger, Haxell and Kostochka from 2008 (a = 0.3531). It consists of a combination of ~80 computer generated inequalities. Based on joint work with Jan Hladky and Daniel Kral.

Series: Graph Theory Seminar

Tiling problems belong to the oldest problems in whole mathematics. They attracted attention of many famous mathematicians. Even one of the Hilbert problems is devoted to the topic. The interest in tilings by unit cubes originated with a conjecture raised by Minkowski in 1908. In this lecture we will discuss the conjecture, and other closely related problems.