Forbidding Subgraphs 1

We will carry over some notation from Ramsey Theory article. We will show a slightly fresh perspective on the general Ramsey problem, and Indeed show that finding the Ramsey number is an extremal problem.

General Ramsey Problem:

Let $({\mathbb{G}}_i)1\le i\le n$ be a collection of graphs. $R({\mathbb{G}}_i)$ is the smallest number of vertices that a complete graph can have, such that if we partition the edges of this complete graph, into $n$ non empty (color) classes, the edge-induced subgraph of one of the classes, contains some ${\mathbb{G}}_i$.

We give an example of such a problem:

If the edges of a $t-$clique is colored with at most $t$/2 colors, then, it must a monochromatic connected graph on $t$ vertices.

proof: by the pigeon hole principle, there must be a color class with at least $t(t-1)/2|C|$ edges. Since we have at most $t/2$ colors, that color class must contain at least $t-1$ edges.

The language of average degree here, is useless. Instead, we ask the question, what is the largest number of edges a graph on $n$ vertices can have, such that it does not contain an $s+1$ clique?

This leads us an extremal problems, where we want, (for a fixed number of vertices), “lots” of edges, and also want to forbid some subgraph

Turan-Problems:

Define $T(n,\mathbb{H})$ to be the largest number of edges, that an $n$ vertex graph can have, while being $\mathbb{H}$-free. In particular, Turan showed us that a complete $s$-partite graph with nearly equal vertices in each partition $\lfloor n/s\rfloor ,\lceil n/s\rceil$ will give us a graph with maximum edges, and will be $\mathbb{K}[s+1]$ free.

We will denote Turan graphs by $\mathcal{K}(n,s)$, where the fancy letter K is used to denote the fact that not only is the graph complete and $s$-partite on $n$ vertices, but there are nearly equal vertices in each partition. Among all complete s-partite graphs, it’s intuitively clear that the one with most parts (hence nearly equal vertices), will have most edges. We will need the number of edges of $\mathcal{K}(n,s)$ quite often, so here goes: first, $n=as+b,0\le b<s$. Then upon doing some algebra, we have the following equation:

But more useful is workable upper and lower bounds, without the remainder $b$ chiming in.

In particular, whenever $n$ is a multiple of $s$,

Anti-Turan Problem:

define $\bar{T}(n,\mathbb{H})$ to be the smallest number of edges , that an $n$ vertex graph can have, so that no matter how we put these edges, we’re guaranteed to have $\mathbb{H}$ as a subgraph. This problem is intimately linked with the two color Ramsey number for $\mathbb{H}$. In particular, if $n\ge R(2,\mathbb{H})$, then for every edge configuration resulting in $\mathbb{G}[n],\overline{\mathbb{G}}[n]$, at least one of them must contain $\mathbb{H}$. In particular, we look at all the configurations where $\mathbb{G}$ and $\overline{\mathbb{G}}$ have nearly equal number edges, namely$\lfloor n(n-1)/4\rfloor ,\lceil n(n-1)/4\rceil$. Hence, it is clear that in any case, all configurations of at least $\lceil n(n-1)/4\rceil$ edges is sufficient. Using $R(2,\mathbb{K}[s])\le 4^s$, we have that for large enough $n$

Any graph on $n$ vertices and at least $\lceil n(n-1)/4\rceil$ edges, contains any subgraph of order close to $\log (n)/log(4).$

if $n<R(2,\mathbb{H})$, then there are some arrangements of edges of $\mathbb{G}[n]$ such that neither $\mathbb{G}$, nor its compliment contains $\mathbb{H}$ . (this follows from the fact that the graph induced by red edges is complementary to the one induced by blue edges).

Take any such arrangement, where neither $\mathbb{G}[n]$ nor $\overline{\mathbb{G}}[n]$ contains $\mathbb{H}$ as a subgraph. one of these graphs contains at least $\lceil n(n-1)/4\rceil$ edges. so even having more than half of all possible edges is not good enough. So in the cases that $n<R(2,\mathbb{H})$ what can we say about anti-Turan problems? at least when $\mathbb{H}$ is a clique?

The general link: Suppose we have a $\mathbb{G}[n]$, and $|E(\mathbb{G})|\ge T(n,\mathbb{H})+1$. Now suppose that $\mathbb{G}$ is $\mathbb{H}$-free. This would contradict the definition of $T(n,\mathbb{H})$. Hence, no graph whose edges are more than $T(n,\mathbb{H})$ is $\mathbb{H}$ free. So we have $\bar{T}(n,\mathbb{H})=T(n,\mathbb{H})+1$.

Mantel’s Theorem: (Special case of Turan’s Theorem)

The maximum number of edges that a triangle free graph on $n$ vertices can have is $\lfloor n^2/4\rfloor$, where equality occurs on the Turan graph of two parts, $\mathcal{K}(n,2)$.

for the following arguments, will consider an graph on $n$ vertices and $m$ edges, which is triangle free.

proof 1: if $xy$ is an edge, then they cannot have a common neighbor, hence, $d(x)+d(y)\le n$. Using a counting argument, it is not difficult to show that $\sum _{xy\in E}d(x)+d(y)=\sum _{v\in V}d(x{)}^2$.

Using QM-AM inequality, we have that $\sum _{v\in V}d(x{)}^2\ge {(\sum _{v\in V}d(x))}^2/n$. Thus, we have $nm\ge 4m^2/n$ or $m\le n^2/4$.

Noticing the sharp points of the inequalities, we can convince ourself that the extremal number of edges occurs in the Turan graph of two parts.

Proof 2: let $A$ be (an) independent set of maximum vertices. then, for any vertex $v$ the set of neighbors of $v$, $N(v)$ must be an independent set. hence $d(v)\le |A|$. Let $B=V-A$. in our original graph, since, $A$ is an independent set, all edges must have at least one endpoint in $B$. so adding up the degrees of all vertices in $B$ gives us an overcount of the number of edges. Hence, $E\le |A||B|$ (since any vertex $b\in B$ has $d(b)\le |A|$. using AM-GM, we have that $E\le {(|A|+|B|/2)}^2=n^2/4$.

It is even easier to deduce the nature of the extremal graph here, observing the sharp points of each inequality. In particular, placing the condition that all edges must have exactly one endpoint in $B$ already gives us Bi-parted-ness. setting $d(v)=|A|$ gives us completeness.