An upper bound for a graph Ramsey numberI am trying to prove the following result, given as an exercise in my book: r ( K m + K n ¯ , K p + K q ¯ ) ≤ ( m + p − 1 m ) n + ( m + p − 1 p ) qHere r(G,H) denotes the Ramsey number for the graphs G and H, i.e. the smallest positive integer t, such that any graph F of order t either contains G or F ¯ (the complement of F) contains H. The join of graphs G+H is defined as the graph obtained by first drawing G ∪ H and then filling out all possible edges between the vertices of G and H.

Question

An upper bound for a graph Ramsey numberI am trying to prove the following result, given as an exercise in my book:  r  (      K    m    +                    K        n            ¯        ,      K    p    +                    K        q            ¯        )  ≤                    (                            m        +        p        −        1            m                      )              n  +                    (                            m        +        p        −        1            p                      )              qHere r(G,H) denotes the Ramsey number for the graphs G and H, i.e. the smallest positive integer t, such that any graph F of order t either contains G or             F      ¯       (the complement of F) contains H. The join of graphs G+H is defined as the graph obtained by first drawing   G  ∪  H and then filling out all possible edges between the vertices of G and H.

Firetto8w · Accepted Answer

We want to show that                    (1)                    r        (                  K          m                +                                            K              n                        ¯                          ,                  K          p                +                                            K              q                        ¯                          )        ≤                                                            (                                                                    m                +                p                −                1                            m                                                      )                                                    n        +                                                            (                                                                    m                +                p                −                1                            p                                                      )                                                    q        .            When n=q=1, (1) becomes                    (2)                    r        (                  K                      m            +            1                          ,                  K                      p            +            1                          )        ≤                                                            (                                                                    m                +                p                −                1                            m                                                      )                                                    +                                                            (                                                                    m                +                p                −                1                            p                                                      )                                                    =                                                            (                                                                    m                +                p                            m                                                      )                                                    .            This classical bound follows from the well-known inequality                    (3)                    r        (                  K                      m            +            1                          ,                  K                      p            +            1                          )        ≤        r        (                  K                      m                          ,                  K                      p            +            1                          )        +        r        (                  K                      m            +            1                          ,                  K                      p                          )        .            (The inequality (2) follows from (3) by induction on m+p. For the base cases, observe that, e.g.,   r  (      K          2        ,      K          p      +      1        )  =  p  +  1The fact that the desired inequality is an easy generalization of a classical result gives a strong hint as to the best way to approach the proof. Happily, (1) does indeed follow along the same lines as the standard proof of (2).Claim: If m,   p  ≥  2 and n,   q  ≥  0, then  r  (      K    m    +                    K        n            ¯        ,      K    p    +                    K        q            ¯        )  ≤  r  (      K          m      −      1        +                    K        n            ¯        ,      K    p    +                    K        q            ¯        )  +  r  (      K    m    +                    K        n            ¯        ,      K          p      −      1        +                    K        q            ¯        )  ..Proof: Set   N  =  r  (      K          m      −      1        +                    K        n            ¯        ,      K    p    +                    K        q            ¯        )  +  r  (      K    m    +                    K        n            ¯        ,      K          p      −      1        +                    K        q            ¯        ) and two-color   E  (      K    N    ) arbitrarily with the colors red and blue. Choose   x  ∈  V  (      K    N    ). By choice of N, it is easy to see that there must be either   r  (      K          m      −      1        +                    K        n            ¯        ,      K    p    +                    K        q            ¯        ) red edges incident to x or   r  (      K    m    +                    K        n            ¯        ,      K          p      −      1        +                    K        q            ¯        ) blue edges incident to x. Without loss of generality, suppose that the latter holds. Let U denote the set of vertices u such that ux is blue. Now consider the edges among the vertices of U. If these contain a red copy of       K    m    +                    K        n            ¯      , then we are done. If not, then by hypothesis they must contain a blue copy of       K          p      −      1        +                    K        q            ¯      . However, all of the edges from x to U are blue, so x and the copy of       K          p      −      1        +                    K        q            ¯       form a blue copy of       K          p        +                    K        q            ¯      We are nearly done. By induction on m+p, we have  r  (      K    m    +                    K        n            ¯        ,      K    p    +                    K        q            ¯        )  ≤                              (                                      m          +          p          −          2                          m          −          1                                      )                      n  +                              (                                      m          +          p          −          2                p                              )                      q    +                              (                                      m          +          p          −          2                m                              )                      n  +                              (                                      m          +          p          −          2                          p          −          1                                      )                      q  ,and                              (                                      m          +          p          −          2                          m          −          1                                      )                      n  +                              (                                      m          +          p          −          2                p                              )                      q  +                              (                                      m          +          p          −          2                m                              )                      n  +                              (                                      m          +          p          −          2                          p          −          1                                      )                      q  =                              (                                      m          +          p          −          1                m                              )                      n  +                              (                                      m          +          p          −          1                p                              )                      q  .Finally, for the base case, one can show by the same method as above that   r  (      K    1    +                    K        n            ¯        ,      K    1    +                    K        q            ¯        )  ≤  n  +  q. This completes the proof.

An upper bound for a graph Ramsey number r(Km+bar Kn,Kp+bar Kq)<=((m+p−1)/m)n+((9m+p−1)/p)q

Answered question

Answer & Explanation

New Questions in Descriptive Statistics