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

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.

Series: Graph Theory Seminar

For an undirected graph G=(V,E) with V={1,...,n} let S(G) be the set of all symmetric n x n matrices A=[a_i,j] with a_i,j non-zero for distinct i,j if and only if ij is an edge. The inertia of a symmetric matrix is the triple (p_+,p_-,p_0), where p_+, p_-,p_0 are the number of positive, negative, and null eigenvalues respectively. The inverse inertia problem asks which inertias can be obtained by matrices in S(G). This problem has been studied intensively by Barrett, Hall, and Loewy. In this talk I will present new results on the inverse inertia problem, among them a Colin de Verdiere type invariant for the inertia set (this is the set of all possible inertias) of a graph, a formula for the inertia set of graphs with a 2-separation, and a formula for the inertia set of the join of a collection of graphs.
The Colin de Verdiere type invariant for the inertia set is joint work with F. Barioli, S.M. Fallat, H.T. Hall, D. Hershkowitz, L. Hogben, and B. Shader, and the formula for the inertia set of the join of a collection of graphs is joint work with W. Barrett and H.T. Hall.

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. A graph is called pebbleable if for each vertex v there is a sequence of pebbling moves so that at least one pebble can be placed on vertex v. The pebbling number of a graph G is the smallest integer k such that G is pebbleable given any configuration of k pebbles on G. We improve on the bound of Bukh by showing that the pebbling number of a graph of diameter 3 on n vertices is at most the floor of 3n/2 + 2, and this bound is best possible. We give an alternative proof that the pebbling number of a graph of diameter 2 on n vertices is at most n + 1. This is joint work with Noah Streib and Carl Yerger.

Series: Graph Theory Seminar

The problem of generating random integral tables from the set of all nonnegative integral tables with fixed marginals is of importance in statistics. The Diaconis-Sturmfels algorithm for this problem performs a random walk on the set of such tables. The moves in the walk are referred to as Markov bases and correspond to generators of a certain toric ideal. When only one and two-way marginals are considered, one can naturally associate a graph to the model. In this talk, I will present a characterization of all graphs for which the corresponding toric ideal can be generated in degree four, answering a question of Develin and Sullivant. I will also discuss some related open questions and demonstrate applications of the Four Color theorem and results on clean triangulations of surfaces, providing partial answers to these questions. Based on joint work with Daniel Kral and Ondrej Pangrac.