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

Haven Kerr 2022-09-15 Answered
An upper bound for a graph Ramsey number
I 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 ) q
Here 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.
You can still ask an expert for help

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (1)

Firetto8w
Answered 2022-09-16 Author has 8 answers
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 + 1
The 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.

We have step-by-step solutions for your answer!

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

asked 2022-06-07
Boxplots and bar graphs
I'm studying for the GRE and came across several questions that I was unable to answer in a practice booklet, even after looking at the answer and trying to work backwards, and searching google and other sites for helpful hints. I think I am missing a fundamental understanding or useful heuristic for solving many of these problems; any advice would be greatly appreciated as my exam is Monday (Aug 1st).
1. Eight hundred insects were weighed, and the resulting measurements, in milligrams, are summarized in the boxplot below.
If the 80th percentile of the measurements is 130 milligrams, about how many measurements are between 126 milligrams and 130 milligrams?
I calculated the range (41), the quartiles(Q1=114, Q2=118, Q3=126), and the IQR (12), but I'm confused about the question. If the 80th percentile (so 80% of the measurements?) is at 130, then 640 are within this percentile. I'm not sure if this is true and even if it is, where to go from here. Each quartile is 25% of the data, correct? So from 126 to 146 must contain 25%, or 200 measurements? (1-.8)(200) = 40, but conceptually I'm lacking what that means.
2.This question refers to the following graph:

(a) In 2003 the family used a total of 49 percent of its gross annual income for two of the categories listed. What was the total amount of the family’s income used for those same categories in 2004 ?
My confusion lies with the fact that I can't seem to find any combination of two categories that add up to 49%. Plus, it seems that the total % expenditure in each year is 101%. The chart is not 100% accurately drawn, but even being very liberal in measuring there seems to be a discrepancy.
asked 2022-08-21
Existence of solution for matrix equation ( I α A ) x ¯ = b ¯
This is my first question in here and I would be really thankful if someone could help me with understanding the matter.
I am solving a matrix equation ( I α A ) x ¯ = b ¯ for a positive vector x ¯ . I don't know anything about the signs of the scalar α and vector b ¯ (but I can always split the solution into several cases). Matrix A is a symmetric matrix with tr(A)=0 (basically it is an adjacent matrix of an undirected graph so it is built only of 0 and 1 with 0 on its diagonal).
My approach would be just to write it down as x ¯ = ( I α A ) 1 b ¯ whenever ( I α A ) is nonsingular (as far as I understand that happens for a finite number of α and thus Lebesgue measure of this set of "inappropriate" α is 0).
In most of the literature, however, it is required that 1 > α λ m a x ( A ) for the convergence of I + α A + α 2 A 2 + and for the solution x ¯ to exist (where λ m a x ( A ) is a maximum eigenvalue of A) . Moreover, then d e t ( I α A ) = 1 α d e t ( A ) = 1 α i λ i > 0 and hence it is also invertible.
So I have two questions here:
Q1: Why do I need convergence of I + α A + α 2 A 2 + in here? I understand that if it converges then k = 0 + α k A k = ( I α A ) 1 , but why do I need that for the existence of a solution x¯? For instance, if we take a simple example:
A = | 0 1 1 0 | α = 30
λ m a x ( A ) = 1 and hence, convergence condition is violated: 30>1. However, I can still calculate x ¯ . Inverse of ( I α A ) exists and is equal to 1 899 | 1 30 30 1 | . If, for instance, b ¯ was negative, then it would give me a positive x ¯ . Or is the condition 1 > α λ m a x ( A ) needed to guarantee that inverse will give a positive solution with both positive α and b ¯ ?
Q2: What will happen if α < 0 (and potentially b ¯ < 0)? What are the conditions for existence of solution x ¯ ? What are the conditions for it to be positive?
asked 2022-08-27
One graph a subgraph of another?
Consider a graph G on n vertices with minimum degree δ and with its largest independent set a > δ. Consider the graph K ¯ a K n a 1 (in other words, take a set of a points and add every edge relation between that set and K n a 1 . Intuitively, this graph is a K n 1 with a missing K a ).
How does one prove that that no matter how I take a vertex v and connect it to δ vertices in the K ¯ a , I will always get a copy of G.
I think this is trivially true for bipartite graphs, but I dont know how to prove it in general. Any help is nice!
asked 2022-07-19
complete k-partite graphs
I am trying to solve the following problem:
Let G be a nonempty graph with the property that whenever u v E ( G ) and v w E ( G ), then u w E ( G ). Prove that G has this property if and only if G is a complete k-partite graph for some k 2. (Consider G ¯ ).
The converse is straightforward and is given by the definition of the complete k-partite graphs, however, the direct way is not trivial and I could not get it.
asked 2022-07-16
Prove χ ( G ) χ ( G ¯ ) n for chromatic number of graph and its complement
Let us denote by χ(G) the chromatic number, which is the smallest number of colours needed to colour the graph G with n vertices. Let G ¯ be the complement of G. Show that
χ ( G ) + χ ( G ¯ ) n + 1
χ ( G ) χ ( G ¯ ) n
I was able to prove (a) using induction. Any hints on proving (b)?
asked 2022-07-09

Using a truth table, check the validity of the following argument: “If Jane won the competition, then either Mary came second or Silva came third. Silva didn’t come third. Thus, if Mary didn’t come second, then Jane didn’t win the competition.”

asked 2022-07-21
Prove that a self-complementary graph has radius 2 and diameter 2 or 3.
I think that is one of the well-known properties of self-complementary graphs, but I am having some troubles trying to prove it. The facts that, if G G ¯ , then both graphs G and G ¯ are connected, and that, for any graph, if r a d ( G ) 3 then r a d ( G ¯ ) 2, and that if d i a m ( G ) 3 then d i a m ( G ¯ ) 3, should make the proof quite easier, but I don't know how to develop it. Could you help me? Thanks in advance!

New questions