Facebook Page
Twitter
RSS
Thanks Thanks:  0
+ Reply to Thread
Results 1 to 2 of 2
  1. MHB Craftsman

    Status
    Offline
    Join Date
    Mar 2017
    Posts
    151
    Thanks
    42 times
    Thanked
    77 times
    #1
    I have already proved that for a graph $G$ with $n$ vertices and $|E(T'(n,q))|$ edges, $\alpha (G) \geq q$. Additionally, if $\alpha (G) = q$ then it must be that $G \cong T'(n,q)$.

    Apparently this is the "dual version" of Turan's Theorem. How does this theorem imply Turan's?

    That $ex(n, K_{p+1}) = |E(T(n,p))|$

    Where:

    - $T'(n,q)$ : $q$ disjoint cliques with size as equal as possible
    - $\alpha (G)$ : independence number of $G$
    - $ex(n, K_{p+1})$ : max number of edges in an n-vertex graph with no $K_{p+1}$ subgraph

  2. # ADS
    Circuit advertisement
    Join Date
    Always
    Posts
    Many
     

  3. MHB Craftsman

    Status
    Offline
    Join Date
    Mar 2017
    Posts
    151
    Thanks
    42 times
    Thanked
    77 times
    #2 Thread Author
    For completeness, here is the proof I wrote.
    I'm not sure it is correct! May be some mistakes in the details.

    Known Theorem:
    Define $T'(n,q)$ to be q disjoint cliques with sizes of vertex sets as equal as possible. Let G be a graph with n vertices and $|E(T'(n,q))|$ edges. Then,
    $$\alpha (G) \geq q$$
    and if $\alpha (G) = q$ then $G \cong T'(n,q)$.


    To prove Turan's theorem, it suffices to show that if $|E(G)|>|E(T(n,p))|$ then $\omega (G) \geq p+1$, (where $\omega (G)$ is the size of the largest clique in G).\\
    Assume $|E(G)|>|E(T(n,p))|$ then $|E(\overline{G})| \leq |E(T'(n,p))|$. By the in class proof, $\alpha (\overline{G}) \geq p+1$.
    Notice that $\omega(G) = \alpha(\overline{G})$. Then we have, $\omega(G) = \alpha(\overline{G}) \geq p+1$, completing the proof.

Similar Threads

  1. Replies: 2
    Last Post: February 15th, 2019, 04:56
  2. Replies: 2
    Last Post: February 10th, 2019, 01:22
  3. Dual Spaces ... Friedberg et al, Example 4, Section 2.6
    By Peter in forum Linear and Abstract Algebra
    Replies: 2
    Last Post: January 8th, 2019, 07:58
  4. Replies: 2
    Last Post: March 6th, 2016, 22:15
  5. Primal Dual Problems
    By OhMyMarkov in forum Advanced Applied Mathematics
    Replies: 0
    Last Post: April 30th, 2012, 09:03

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Math Help Boards