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

Series: Graph Theory Seminar

This is Lecture 2 of a series of 3 lectures by the speaker. See the abstract on Tuesday's ACO colloquium of this week. (Please note that this lecture will be 80 minutes' long.)

Series: Graph Theory Seminar

The celebrated Erdos-Hajnal conjecture states that for every graph H, there is a constant c > 0 such that every graph G that does not contain H as an induced subgraph has a clique or stable set of size at least n^c, where n = |V(G)|.

One approach for proving this conjecture is to prove that in every H-free graph G, there are two linear-size sets A and B such that either there are no edges between A and B, or every vertex in A is adjacent to every vertex in B. As is turns out, this is not true unless both H and its complement are trees. In the case when G contains neither H nor its complement as an induced subgraph, the conclusion above was conjectured to be true for all trees (Liebenau & Pilipczuk), and I will discuss a proof of this for a class of tree called "caterpillars".

I will also talk about results and open questions for some variants, including allowing one or both of A and B to have size n^c instead of linear size, and requiring the bipartite graph between A and B to have high or low density instead of being complete or empty. In particular, our results improve the bound on the size of the largest clique or stable that must be present in a graph with no induced five-cycle.

Joint work with Maria Chudnovsky, Jacob Fox, Anita Liebenau, Marcin Pilipczuk, Alex Scott, and Paul Seymour.

Series: Graph Theory Seminar

Let G be a graph containing 5 different vertices a0, a1, a2, b1 and b2.

We say that (G, a0, a1, a2, b1, b2) is feasible if G contains disjoint

connected subgraphs G1, G2, such that {a0, a1, a2}⊆V(G1) and {b1,

b2}⊆V(G2). In

this talk, we will complete a sketch of our arguments for characterizing when (G, a0, a1, a2, b1, b2) is feasible. Joint work with Changong Li, Robin Thomas, and Xingxing Yu.

Series: Graph Theory Seminar

Let G be a graph containing 5 different vertices a0, a1, a2, b1 and

b2. We say that (G, a0, a1, a2, b1, b2) is feasible if G contains

disjoint connected subgraphs G1, G2, such that {a0, a1, a2}⊆V(G1) and

{b1, b2}⊆V(G2). In this talk, we will prove the

existence of 5-edge configurations in (G, a0, a1, a2, b1, b2). Joint

work with Changong Li, Robin Thomas, and Xingxing Yu.

Series: Graph Theory Seminar

Let G be a graph containing 5 different vertices a0, a1, a2, b1 and

b2. We say that (G, a0, a1, a2, b1, b2) is feasible if G contains

disjoint connected subgraphs G1, G2, such that {a0, a1, a2}⊆V(G1) and

{b1, b2}⊆V(G2). In this talk, we will introduce

ideal frames, slim connectors and fat connectors. We will first deal

with the ideal frames without fat connectors, by studying 3-edge and

5-edge configurations. Joint work with Changong Li, Robin Thomas, and

Xingxing Yu.

Series: Graph Theory Seminar

Let G be a graph containing 5 different vertices a0, a1, a2, b1

and b2. We say that (G, a0, a1, a2, b1, b2) is feasible if G contains

disjoint connected subgraphs G1, G2, such that {a0, a1, a2}⊆V(G1) and

{b1, b2}⊆V(G2). In this talk, we will describe

the structure of G when (G, a0, a1, a2, b1, b2) is infeasible, using

frames and connectors. Joint work with Changong Li, Robin Thomas, and

Xingxing Yu.

Series: Graph Theory Seminar

In this talk we will discuss some Tur\'an-type results on graphs with a given circumference.

Let $W_{n,k,c}$ be the graph obtained from a clique $K_{c-k+1}$

by adding $n-(c-k+1)$ isolated vertices each joined to the same $k$ vertices of the clique,

and let $f(n,k,c)=e(W_{n,k,c})$.

Kopylov proved in 1977 that for $c<n$, any 2-connected graph $G$ on $n$ vertices with circumference $c$ has at most

$\max\{f(n,2,c),f(n,\lfloor\frac{c}{2}\rfloor,c)\}$ edges,

with equality if and only if $G$ equals $W_{n,2,c}$ or $W_{n,\lfloor\frac{c}{2}\rfloor,c}$.

Recently, F\"{u}redi et al. obtained a stability version of Kopylov's theorem.

They proved that if $G$ is a 2-connected graph on $n$ vertices with circumference $c$

such that $10\leq c<n$ and $e(G)>\max\{f(n,3,c),f(n,\lfloor\frac{c}{2}\rfloor-1,c)\}$,

then either $G$ is a subgraph of $W_{n,2,c}$ or $W_{n,\lfloor\frac{c}{2}\rfloor,c}$,

or $c$ is odd and $G$ is a subgraph of a member of two well-characterized families

which we define as $\mathcal{X}_{n,c}$ and $\mathcal{Y}_{n,c}$.

We extend and refine their result by showing that if $G$ is a 2-connected graph on $n$

vertices with minimum degree at least $k$ and circumference $c$

such that $10\leq c<n$ and $e(G)>\max\{f(n,k+1,c),f(n,\lfloor\frac{c}{2}\rfloor-1,c)\}$,

then one of the following holds:\\

(i) $G$ is a subgraph of $W_{n,k,c}$ or $W_{n,\lfloor\frac{c}{2}\rfloor,c}$, \\

(ii) $k=2$, $c$ is odd, and $G$ is a subgraph of a member of $\mathcal{X}_{n,c}\cup \mathcal{Y}_{n,c}$, or \\

(iii) $k\geq 3$ and $G$ is a subgraph of the union of a clique $K_{c-k+1}$ and some cliques $K_{k+1}$'s,

where any two cliques share the same two vertices.

This provides a unified generalization of the above result of F\"{u}redi et al. as well as

a recent result of Li et al. and independently, of F\"{u}redi et al. on non-Hamiltonian graphs.

Moreover, we prove a stability result on a classical theorem of Bondy on the circumference.

We use a novel approach, which combines several proof ideas including a closure operation and an edge-switching technique.

Series: Graph Theory Seminar

Let G be a graph containing 5 different vertices a0, a1, a2, b1 and b2.

We say that (G, a0, a1, a2, b1, b2) is feasible if G contains disjoint

connected subgraphs G1, G2, such that {a0, a1, a2}⊆V(G1)

and {b1, b2}⊆V(G2).

In this talk, we will continue our discussion on

the operations we use for characterizing feasible (G, a0, a1, a2, b1,

b2). If time permits, we will also discuss useful structures for

obtaining that characterization, such as frame, ideal frame, and

framework. Joint work with Changong Li, Robin Thomas, and

Xingxing Yu.

Series: Graph Theory Seminar

Let $G$ be a graph containing 5 different vertices $a_0, a_1, a_2, b_1$ and $b_2$. We say that $(G,a_0,a_1,a_2,b_1,b_2)$ is feasible if $G$ contains disjoint connected subgraphs $G_1, G_2$, such that $\{a_0, a_1, a_2\}\subseteq V(G_1)$ and $\{b_1, b_2\}\subseteq V(G_2)$. We give a characterization for $(G,a_0,a_1,a_2,b_1,b_2)$ to be feasible, answering a question of Robertson and Seymour. This is joint work with Changong Li, Robin Thomas, and Xingxing Yu.In this talk, we will discuss the operations we will use to reduce $(G,a_0,a_1,a_2,b_1,b_2)$ to $(G',a_0',a_1',a_2',b_1',b_2')$ with $|V(G)|+|E(G)|>|V(G')|+E(G')$, such that $(G,a_0,a_1,a_2,b_1,b_2)$ is feasible iff $(G',a_0',a_1',a_2'b_1',b_2')$ is feasible.

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.