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

Series: Graph Theory Working Seminar

Erdős and Nešetřil conjectured in 1985 that every graph with maximum degree Δ can be strong edge colored using at most (5/4)Δ^2 colors. In this talk we discuss recent progress made in the case of Δ=4, and go through the method used to improve the upper bound to 21 colors, one away from the conjectured 20.

Series: Graph Theory Working Seminar

A classical result of Edwards says that every m-edge graph has a 2-cut of size m/2+Ω(√m), and this is best possible. We will continue our discussion about recent results on analogues of Edwards’ result and related problems in hypergraphs.

Series: Graph Theory Working Seminar

An $r$-cut of a $k$-uniform hypergraph $H$ is a partition of the vertex set of $H$ into $r$ parts and the size of the cut is the number of edges which have a vertex in each part. A classical result of Edwards says that every $m$-edge graph has a 2-cut of size $m/2+\Omega(\sqrt{m})$, and this is best possible. In this talk we will discuss recent results on analogues of Edwards’ result and related problems in hypergraphs.

Series: Graph Theory Working Seminar

Gallai
conjectured in 1968 that the edges of a connected graph on n vertices
can be decomposed into at most (n+1)/2 edge-disjoint paths. This
conjecture
is still open, even for planar graphs. In this talk we will discuss some
related results and special cases where it is known to hold.

Series: Graph Theory Working Seminar

We will go through
the proof of the hypergraph container result of Balogh, Morris, and
Samotij. We will also discuss some applications of this container
result.

Series: Graph Theory Working Seminar

Many combinatorial questions can be formulated as problems about independent sets in uniform hypegraphs, including questions about number of sets with no $k$-term arithmetic progression and questions about typical structure of $H$-free graphs. Balogh, Morris, and Samotij and, independently, Saxton and Thomason gave an approximate structural characterization of all independent sets in uniform hypergraphs with natural contitions on edge distributions, using something called "containers". We will go through the proof of the hypergraph container result of Balogh, Morris, and Samotij. We will also discuss some applications of this container result.