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

Series: Graph Theory Seminar

We study the uniqueness of optimal configurations in extremal
combinatorics. An empirical experience suggests that optimal solutions to
extremal graph theory problems can be made asymptotically unique by
introducing additional constraints. Lovasz conjectured that this phenomenon
is true in general: every finite feasible set of subgraph density
constraints can be extended further by a finite set of density constraints
such that the resulting set is satisfied by an asymptotically unique graph.
We will present a counterexample to this conjecture and discuss related
results.
The talk is based on joint work with Andrzej Grzesik and Laszlo Miklos
Lovasz.

Series: Graph Theory Seminar

For a graph G, the Colin de Verdière graph parameter mu(G) is the maximum
corank of any matrix in a certain family of generalized adjacency matrices
of G. Given a non-negative integer t, the family of graphs with mu(G) <= t
is minor-closed and therefore has some nice properties. For example, a
graph G is planar if and only if mu(G) <= 3. Colin de Verdière conjectured
that the chromatic number chi(G) of a graph satisfies chi(G) <= mu(G)+1.
For graphs with mu(G) <= 3 this is the Four Color Theorem. We conjecture
that if G has at least t vertices and mu(G) <= t, then |E(G)| <= t|V(G)| -
(t+1 choose 2). For planar graphs this says |E(G)| <= 3|V(G)|-6. If this
conjecture is true, then chi(G) <= 2mu(G). We prove the conjectured edge
upper bound for certain classes of graphs: graphs with mu(G) small, graphs
with mu(G) close to |V(G)|, chordal graphs, and the complements of chordal
graphs.

Series: Graph Theory Seminar

A spanning subgraph $F$ of a graph $G$ iscalled an even factor of $G$ if each vertex of $F$ has even degreeat least 2 in $F$. It was proved that if a graph $G$ has an evenfactor, then it has an even factor $F$ with $|E(F)|\geq {4\over7}(|E(G)| + 1)$, which is best possible. Recently, Cheng et al.extended the result by considering vertices of degree 2. They provedthat if a graph $G$ has an even factor, then it has an even factor$F$ with $|E(F)|\geq {4\over 7}(|E(G)| + 1)+{1\over 7}|V_2(G)|$,where $V_2(G)$ is the set of vertices of degree 2 in $G$. They alsogave examples showing that the second coefficient cannot be largerthan ${2\over 7}$ and conjectured that if a graph $G$ has an evenfactor, then it has an even factor $F$ with $|E(F)|\geq {4\over7}(|E(G)| + 1)+ {2\over 7}|V_2(G)|$. We note that the conjecture isfalse if $G$ is a triangle. We confirm the conjecture for all graphson at least 4 vertices. Moreover, if $|E(H)|\leq {4\over 7}(|E(G)| +1)+ {2\over 7}|V_2(G)|$ for every even factor $H$ of $G$, then everymaximum even factor of $G$ is a 2-factor in which each component isan even circuit.

Series: Graph Theory Seminar

Consider the following solitaire game on a graph. Given a chip configuration on the node set V, a move consists of taking a subset U of nodes and sending one chip from U to V\U along each edge of the cut determined by U. A starting configuration is winning if for every node there exists a sequence of moves that allows us to place at least one chip on that node. The (divisorial) gonality of a graph is defined as the minimum number of chips in a winning configuration. This notion belongs to the Baker-Norine divisor theory on graphs and can be seen as a combinatorial analog of gonality for algebraic curves. In this talk we will show that the gonality is lower bounded by the tree-width and, if time permits, that the parameter is NP-hard to compute. We will conclude with some open problems.

Series: Graph Theory Seminar

A tournament is a directed graph obtained by orienting each edge of a
complete graph. A set of vertices D is a dominating set in a tournament
if every vertex not in D is pointed by a vertex in D. A tournament H is a
rebel if there exists k such that every H-free tournament has a
dominating set of size at most k. Wu conjectured that every tournament
is a rebel. This conjecture, if true, implies several other conjectures
about tournaments. However, we will prove that Wu's conjecture is false
in general and prove a necessary condition for being rebels. In
addition, we will prove that every 2-colorable tournament and at least
one non-2-colorable tournament are rebels. The later implies an open
case of a conjecture of Berger, Choromanski, Chudnovsky, Fox, Loebl,
Scott, Seymour and Thomasse about coloring tournaments. This work is
joint with Maria Chudnovsky, Ringi Kim, Paul Seymour and Stephan
Thomasse.

Series: Graph Theory Seminar

Lately there was a growing interest in studying
self-similarity and fractal
properties of graphs, which is largely inspired by applications in
biology,
sociology and chemistry. Such studies often employ statistical physics
methods that borrow some ideas from graph theory and general topology, but
are not intended to approach the problems under consideration in a
rigorous
mathematical way. To the best of our knowledge, a rigorous combinatorial
theory that defines and studies graph-theoretical analogues of topological
fractals still has not been developed.
In this paper we introduce and study discrete analogues of Lebesgue and
Hausdorff dimensions for graphs. It turned out that they are
closely related to well-known graph characteristics such as rank dimension
and Prague (or Nesetril-Rodl) dimension. It allowed us to formally define
fractal graphs and establish fractality of some graph classes. We show,
how
Hausdorff dimension of graphs is related to their Kolmogorov complexity.
We
also demonstrate fruitfulness of this interdisciplinary approach by
discover a novel property of general compact metric spaces using ideas
from
hypergraphs theory and by proving an estimation for Prague dimension of
almost all graphs using methods from algorithmic information theory.

Series: Graph Theory Seminar

Stiebitz showed that a graph with minimum degree s+t+1 can be decomposed
into vertex disjoint subgraphs G_1 and G_2 such that G_1 has minimum degree
at least s and G_2 has minimum degree at least t. Motivated by this result,
Norin conjectured that a graph with average degree s+t+2 can be decomposed
into vertex disjoint subgraphs G_1 and G_2 such that G_1 has average degree
at least s and G_2 has average degree at least t. Recently, we prove
that a graph
with average degree s+t+2 contains vertex disjoint subgraphs G_1 and G_2
such that G_1 has average degree at least s and G_2 has average degree at
least t. In this talk, I will discuss the proof technique. This is joint
work with Hehui Wu.

Series: Graph Theory Seminar

A special feature possessed by the graphs of social networks
is triangle-dense. R. Gupta, T. Roughgarden and C. Seshadhri give a
polynomial time graph algorithm to decompose a triangle-dense graph into
some clusters preserving high edge density and high triangle density in
each cluster with respect to the original graph and each cluster has
radius 2. And high proportion of triangles of the original graph are
preserved in these clusters. Furthermore, if high proportion of edges in
the original graph is "locally triangle-dense", then additionally, high proportion of
edges of the original graph are preserved in these clusters.
In this talk, I will present most part of the paper "Decomposition of Triangle-dense Graphs"
in SIAM J. COMPUT. Vol. 45, No. 2, pp. 197–215, 2016, by R. Gupta, T. Roughgarden and C. Seshadhri.

Series: Graph Theory Seminar

Let G be a 5-connected nonplanar graph. To show the Kelmans-Seymour
conjecture, we keep contracting a connected subgraph on a special vertex z
until the following happens: H does not contain K_4^-, and for any subgraph
T of H such that z is a vertex in T and T is K_2 or K_3, H/T is not
5-connected. In this talk, we study the structure of these 5-separations
and 6-separations, and prove the Kelmans-Seymour conjecture.

Series: Graph Theory Seminar

Let G be a 5-connected nonplanar graph. To show the Kelmans-Seymour
conjecture, we keep contracting a connected subgraph on a special vertex z
until the following happens: H does not contain K_4^-, and for any subgraph
T of H such that z is a vertex in T and T is K_2 or K_3, H/T is not
5-connected. In this talk, we prove a lemma using the characterization of
three paths with designated ends, which will be used in the proof of the
Kelmans-Seymour conjecture.