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

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.

Series: Graph Theory Seminar

Each graph can be embedded in 3-space. The problem becomes more interesting if we put restrictions on the type of embedding. For example, a linkless embedding of a graph is one where each pair of vertex-disjoint circuits has linking number equal to zero. The class of all graphs that have a linkless embedding is closed under taking minors. Robertson, Seymour, and Thomas gave the forbidden minors for this class of graphs. Open remained how to find a linkless embedding in polynomial time. In the talk we start with discussing an algorithm to find a linkless embedding.Instead of embedding the graph in 3-space, we could also consider mapping properties of certain superstructures of the graph in 3-space, and, indeed, if this superstructure has not the right mapping properties in 3-space, see whether it has the right one in 4-space, etc. Recently, we introduced for a graph G a new graph parameter \sigma(G), which is defined as the smallest d such that superstructures of G have a zero intersection mapping in d-space. The nicest property of this graph parameter is its independence of the superstructure and thus depends on the graph only. For d=2 and d=3, \sigma(G) \leq d if and only if G is outerplanar and planar, respectively. The graphs G with \sigma(G)\leq 4 are exactly those that have a linkless embedding. In the second part of the talk we will discuss this new graph parameter. (This part is joint work with R. Pendavingh.)

Series: Graph Theory Seminar

Given a configuration of pebbles on the vertices of a connected graph G, a pebbling move is defined as the removal of two pebbles from some vertex, and the placement of one of these on an adjacent vertex. The pebbling number of a graph G is the smallest integer k such that given any configuration of k pebbles on G and any specified vertex v in V(G), there is a sequence of pebbling moves that sends a pebble to v. We will show that the pebbling number of a graph of diameter four on n vertices is at most 3n/2 + O(1), and this bound is best possible up to an additive constant. This proof, based on a discharging argument and a decomposition of the graph into ''irreducible branches'', generalizes work of Bukh on graphs of diameter three. Further, we prove that the pebbling number of a graph on n vertices with diameter d is at most (2^{d/2} - 1)n + O(1). This also improves a bound of Bukh.

Series: Graph Theory Seminar

PLEASE NOTE UNUSUAL TIME

We will consider the problem of counting the number T(n,g) of cubic graphs with n edges on a surface of of genus g, and review was is known in the combinatorial community in the past 30 years, what was conjectured in physics 20 years ago, and what was proven last month in joint work with Thang Le and Marcos Marino, using the Riemann-Hilbert analysis of the Painleve equation. No knowledge of physics or analysis is required.

Series: Graph Theory Seminar

In this lecture I will introduce the method and sketch some recent applications. The main idea is to exploit a natural connection between the evolution of discrete random processes and continuous functions on the real numbers. Roughly speaking, the method is as follows: Given a discrete random process, we calculate the expected change in the random variable (or variables) of interest in one step of the process, write a differential equation suggested by the expected change, and show that the evolution of the random variable over the course of the process is sharply concentrated around the trajectory given by the solution of the differential equation. This allows us to translate simple facts (often combinatorial in nature) about expected changes in one step of the process into strong statements about sharp concentration of the random variable over the entire course of the process.

Series: Graph Theory Seminar

The aim of this talk is to introduce techniques from knot theory into the study of graphs embedded in 3-space. The main characters are hyperbolic geometry and the Jones polynomial. Both have proven to be very successful in studying knots and conjecturally they are intimately related. We show how to extend these techniques to graphs and discuss possible applications. No prior knowledge of knot theory or geometry will be assumed.