WELCOME TO THIS BLOG!!. PLEASE ENJOY THE MENU HAS BEEN PROVIDED

Friday, July 18, 2014

A THEOREM OF TURAN

A THEOREM OF TURAN
Introduction
  • Extremal problem are problem that ask what is the largest or smallest graph with a speficied property.
  • “the largest” ® the graph with the most edges, given the number of vertices.
  • The number of vertices in G : Order of G
  • The number of edges in G : Size of G
  • Induced Subgraph of a graph G is a subgraph of G obtained by taking a subset W of the vertices of G together with every edge of G that has both endpoints in W.
Problem 1
Find a largest graph G with n vertices and chromatic number two
Solution :
  • Since G has chromatic number two, the vertices are colored by two colors, red and blue.
  • If there is a red vertex that is not adjacent to a blue vertex, we can add this edge and increase the number of edges .
  • So blue vertex is adjacent to every red vertex Þ complete bipartite graph.
Find a largest graph G with n vertices and chromatic number two
Solution :
  • Suppose there are  m1 blue and m2 red vertices, m1+m2 = n. [m1-m]2 ≤1
  • Suppose that m2 £ m1.
  • If m2 + 2 £ m1, then we choose another complete bipartite graph     with m2 + 1 red vertices and m1 - 1 blue vertices.
  • Then,
            G has m1m2 edges
             has (m1 - 1) (m2 + 1) edges
            (m1 - 1) (m2 + 1) - m1m2 = m1 - m2 - 1
  • Diasumsikan m2 £ m1 - 2 Þ m1 - m2 - 1 ³ 1
  •        has at least one more edge than G ® colorable 2 colors and has n vertices ® m1 and m2 differ by at most one.        
Find a largest graph G with n vertices and chromatic number two
Solution :
  • There is a way to write the result by using Gauss’ symbol for the greatest integer function.
                                    ëxû = the greatest integer £ x
            Using this notation, the graph G that is the solution to our problem is the graph           with



Find a largest graph G with n vertices and chromatic number k
  • Suppose that n is some positive integer and we wish to have n = n1 + n2 + . . . + nk , ni as close in value as possible.
  • n divisible by k ® n = k, n is not divisible by k, then any two of them will differ by no more than one.
  • ê ni + nj ú £ 1, for all i and j
For example :
            n =15, k = 4
            Solution
                        15 = 3 + 4 + 4 + 4



Problem 2
PROBLEM : Find the largest graph G with n vertices and chromatic number k
SOLUTION :
·         Since G is k-chromatic, the vertices of G can be colored with k colors.
·         mi be the number of vertices colored with color i = 1,2, . . . , k
                        Þ n = m1 + m2 + . . . + mk
                        Þ G complete k-partite graph Km1,m2,…,mk

·         Denote the number of edges k-partite graph Km1,m2,…,mk
                           by A (m1,m2,…mk) so
                        A (m1,m2,m3…mk) = m1m2+A(m1 + m2, m3, . . . ,mk)
·         Suppose that in G any two of these numbers differ by more than 1, m2 + 2 £ m1
·         We consider a new graph  Km1-1,m2+1,…,mk
·         The number of edges in
A (m1-1, m2+1, m3, …, mk   = (m1-1)(m2+1)+A(m1+m2,m3,…mk)
Size in      - size G is  (m1-1)(m2+1)-m1m2 = m1-m2-1
·         Since   m2 + 2 £ m1
·                                             Þ m1 - m2 - 1 ³ 1
·          has at least one more edge than G hence G couldn’t have the max number of edges.
·         Assumption m2 + 2 £ m1 leads to contradiction ® any two of the numbers mi and mj differ  by at most one. Proved !
THEOREM 4.1.1
“The largest graph with n vertices and chromatic number k is a complete k-partite graph
with n = n1 + n2 + . . . + nk  and ê ni - nj ú £ 1 ”
Find the largest graph G with n vertices and chromatic number k
THEOREM 4.1.2 (TURAN) : The largest graph with n vertices that contains no subgraph isomorphic to Kk+1 is a complete k-partite graph   Km1,m2,…,mk   with n = n1 + n2 + . . . + nk  and ê ni - nj ú £ 1
Proof :
  • The conclusion of Theorem 4.1.2 = Theorem 4.1.1
  • The assumption of Theorem 4.1.1 implies the assumption in Theorem 4.1.2, but not conversely.
  • Certainly no graph with chromatic number k contains a subgraph isomorphic to Kk+1.
Theorem 4.1.2* : The largest graph with n vertices that contains no triangle is a complete bipartite graph Kn1,n2  with n = n1 + n2 and ê n1 - n2 ú £ 1
Proof  :
  • Let be a graph with n vertices that doesn’t contain triangle.
  • Let V be the vertex set of G.
  • Choose a vertex x of G so degG(x) is maximal.
  • Consider the set W of vertices of G that adjacent to x.
  • G would contain a triangle.
  • Define a new graph H with the same set of vertices V as G.
  • Let W be the same subset of V as above
  • Every vertex in V-W is adjacent to every vertex in W in H.
  • H is complete bipartite graph.
  • If z  is a vertex in V-W, then degH(z) = degH(x) = degG(x) ³ degG(z)
  • x to be a vertex of maximal degree in G.
  • Suppose that the number of vertices in W is w.
  • Then if z is a vertex in W, degH(z) = n - w ³ degG(z),  So G would contain a triangle.
  • Thus we have found a new graph H such that degG(z) £ degH(z).
  • The total number of edges in H must be at least the number of edges in G.
  • H is a complete bipartite graph.
  • Based on theorem 4.1.1, the largest complete bipartite graph with n vertices is  Kn1,n2            with n = n1 + n2 and ê n1 - n2 ú £ 1.
LEMMA 4.1.3 : If G is a graph on n vertices that contains no Kk+1 then there is a k-partite graph H with the same vertex set as G such that degG(z) £ degH(z) for every vertex of G.
PROOF :
  • Suppose that the lemma is true for all values less than k
            Suppose that G is a graph with n vertices not containing Kk+1.
  • Let V be the vertex set of G
            Let x be a vertex of G with degG(x) maximal.
            Let W be the set of vertices adjacent to x in G.
            Let G0 be the subgraph induced by the set
  • G0 can’t contain a subgraph isomorphic to Kk
  • Otherwise G would contain a subgraph isomorphic to Kk+1 since x is adjacent to all the vertices of W.
  • Thus the lemma holds for G0 and there exist a (k - 1)-partite graph H0 such that degGo(z) £ degHo(z) for every vertex z in W.
  • Take the vertices in V - W and connect each of them to every vertex H0 to form a new graph H
PROOF LEMMA 4.1.3 :
For every vertex z in V - W we have
                  degG (z) £ degG (x),
                  degG (x) = degH (x) = degH (z),           . . . degG (x) maximal
Thus for every vertex z in V - W
                  degG (z) £ degH (z).
Let z be a vertex in W and w be the number of vertices in W. So
                  degG (z) £ degG (z) + n - w,
since z can be adjacent to at most n - w of the vertices in V - W in G. Also,
                   degG (z) + n - w £ degG (z) + n - w
by the induction hypothesis. Finally
                  degHo (z) + n - w = degH (z)
                  degG (z) £ degH (z)
Since the above inequality holds for all z in V, the lemma is proved.
For every vertex z in V - W we have
                  degG (z) £ degG (x),
                  degG (x) = degH (x) = degH (z),           . . . degG (x) maximal
Thus for every vertex z in V - W
                  degG (z) £ degH (z).
Let z be a vertex in W and w be the number of vertices in W. So
                  degG (z) £ degG (z) + n - w,
since z can be adjacent to at most n - w of the vertices in V - W in G. Also,
                   degG (z) + n - w £ degG (z) + n - w
by the induction hypothesis. Finally
                  degHo (z) + n - w = degH (z)
                  degG (z) £ degH (z)
Since the above inequality holds for all z in V, the lemma is proved.
NOTES :
Lemma 4.1.3 shows that if G is a graph with n vertices that doesn’t contain a subgraph isomorphic to Kk+1, then G can be replaced by a k-partite graph without decreasing the number of edges. The largest k-partite graph with n vertices is the complete k-partite graph.
Turan Graph
·         If n and k given, tis graph is called the Turan graph Tn,k
The Turan Graph T15,4
·         The octahedron graph is so also the graph T6,3  the largest graph on six vertices that contains no K4




.