What can be said about the rate of growth of f(n), defined by f(n)=min/(|V(G)|=n) [χ(G)+χ(bar G)], where the minimum is taken over all graphs G on n vertices.

wstecznyg5 2022-07-21 Answered
chromatic number of a graph versus its complement
What can be said about the rate of growth of f(n), defined by
f ( n ) = min | V ( G ) | = n [ χ ( G ) + χ ( G ¯ ) ] ,
where the minimum is taken over all graphs G on n vertices.
Two observations.
(1) Either G or G ¯ contains a clique on roughly logn vertices by Ramsey theory, so f ( n ) c 1 log n for some constant c 1 > 0.
(2) If G=G(n,1/2) is a random graph, then χ ( G ) χ ( G ¯ ) n / log n n/ log n almost surely, so we also have f ( n ) c 2 n / log n n/log n for some constant c 2 > 0.
These bounds seem hopelessly far apart.
Can we improve on the bounds
c 1 log n f ( n ) c 2 n / log n
for all sufficiently large n?
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 (2)

frisiao
Answered 2022-07-22 Author has 13 answers
(Answering for posterity, don't select this as best.)
First, extend @ccc's proof to show that if p q n then f ( n ) p + q. You do this first by taking a graph on n nodes consisting of (at most) p cliques of at most q nodes each, and noting that χ ( G ) p and χ ( G ¯ ) q
Now, as shown by ccc in coments above,
2 n f ( n ) 2 n
This reduces to at most two values.
In general, if 2 x < 2 x , then the fractional part of x is in ( 0 , 1 2 ). So we only need to consider the cases where the fractional part of n is in this range, that is, n = p + δwhere p is an integer and 0 < δ < 1 2 .
Claim: p ( p + 1 ) n.
We know that p ( p + 1 ) n. Since n and p(p+1) are integers, this means p ( p + 1 ) n
Therefore, f ( n ) 2 p + 1 = 2 n
So we know that f ( n ) is always 2 n
Not exactly what you’re looking for?
Ask My Question
Marisol Rivers
Answered 2022-07-23 Author has 4 answers
Although there is already an accepted answer, I answer to give a bit more information, for what I have to say would not fit in a comment.
This is the Nordhaus-Gaddum Theorem:
If G is a graph of order n, then
2 n χ ( G ) + χ ( G ¯ ) n + 1
n χ ( G ) χ ( G ¯ ) ( n + 1 2 ) 2
And, there is no possible improvement of any of these bounds. In fact, much more can be said:
Let n be a positive integer. For every two positive integers a and b such that
2 n a + b n + 1
n a b ( n + 1 2 ) 2
there is a graph G of order n such that χ(G)=a and p q n.
Source: Graphs & Digraphs (Fifth edition) by Chartrand, Lesniak, and Zhang
Not exactly what you’re looking for?
Ask My Question

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-07-09
Is age a discrete or continuous variable? Why?
asked 2022-07-16
What is the z-score of sample X, if n = 196 ,   μ = 55 ,   St.Dev = 42 ,   μ X = 58?
asked 2022-07-19
Underline the correct word (in the parenthesis) to complete the sentence.
4) When normal scores are transformed into z-scores, the resulting z-scores will have a mean of (0, 1 ).
5) For a normal random variable, the probability of observing a value less than or equal to its mean is (0,0.5, 1).
asked 2022-07-09
If we have N sets, { A 1 , , A N }, and we form a set S by taking the sum of each element in the set with each element in the other sets, what can we say about the mode of S?
Intuitively, I would like to think that we can simply take the sum of the modes, i.e:
Mode ( S ) = n = 1 N Mode ( A n )
However, this seems unlikely, especially as we would expect that Mode ( A n ) could potentially be a set of values, rather than a single value.
So I was wondering if we'd be able to relax this condition to state that Mode ( S ) n = 1 N Mode ( A n ), where we define Mode ( A ) + Mode ( B ) as the set formed by taking the sum of each element in Mode ( A ) with each element in Mode ( B ), formally:
Mode ( S ) n = 1 N Mode ( A n ) = { n = 1 N x n : x i A i }
This seems to be true, but I was wondering if we could say anything stronger?
asked 2022-05-08
How can I calculate the mode in a grouped frequency distribution when the largest frequency occurs in two or more classes?
asked 2022-05-28
Given a sample (the scope is 72 elements) with mode=54 mean=55,7 median=54,5. The 73th value of the extended sample is 56. What can I say about the mode, median and mean of the extended sample?
asked 2022-07-18
The measure of effect size used with the X 2 test of independence is
a.That there is a small effect size
b. That there is a medium effect size
c. That there is a large effect size
d. That there is no effect size at all

New questions

The Porsche Club of America sponsors driver education events that provide high-performance driving instruction on actual racetracks. Because safety is a primary consideration at such events, many owners elect to install roll bars in their cars. Deegan Industries manufactures two types of roll bars for Porsches. Model DRB is bolted to the car using existing holes in the car's frame. Model DRW is a heavier roll bar that must be welded to the car's frame. Model DRB requires 20 pounds of a special high alloy steel, 40 minutes of manufacturing time, and 60 minutes of assembly time. Model DRW requires 25 pounds of the special high alloy steel, 100 minutes of manufacturing time, and 40 minutes of assembly time. Deegan's steel supplier indicated that at most 40,000 pounds of the high-alloy steel will be available next quarter. In addition, Deegan estimates that 2000 hours of manufacturing time and 1600 hours of assembly time will be available next quarter. The pro?t contributions are $200 per unit for model DRB and $280 per unit for model DRW. The linear programming model for this problem is as follows:
Max 200DRB + 280DRW
s.t.
20DRB + 25DRW 40,000 Steel Available
40DRB + 100DRW ? 120,000 Manufacturing minutes
60DRB + 40DRW ? 96,000 Assembly minutes
DRB, DRW ? 0
Optimal Objective Value = 424000.00000
Variable Value blackuced Cost
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
DRB 1000.00000 0.00000
DRW 800.00000 0.00000
Constraint Slack/ Surplus Dual Value
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
1 0.00000 8.80000
2 0.00000 0.60000
3 4000.00000 0.00000
Objective Allowable Allowable
Variable Coef?cient Increase Decrease
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
DRB 200.00000 24.00000 88.00000
DRW 280.00000 220.00000 30.00000
RHS Allowable Allowable
Constraint Value Increase Decrease
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
1 40000.00000 909.09091 10000.00000
2 120000.00000 40000.00000 5714.28571
3 96000.00000 Infnite 4000.00000
a. What are the optimal solution and the total profit contribution?
b. Another supplier offeblack to provide Deegan Industries with an additional 500 pounds of the steel alloy at $2 per pound. Should Deegan purchase the additional pounds of the steel alloy? Explain.
c. Deegan is considering using overtime to increase the available assembly time. What would you advise Deegan to do regarding this option? Explain.
d. Because of increased competition, Deegan is considering blackucing the price of model DRB such that the new contribution to profit is $175 per unit. How would this change in price affect the optimal solution? Explain.
e. If the available manufacturing time is increased by 500 hours, will the dual value for the manufacturing time constraint change? Explain.