Content deleted Content added
Hamsterrific (talk | contribs) m Changed "color the edges" link to a more precise wikipedia page |
Made the argument that both properties hold with prob. > 0 more clear. |
||
Line 59:
A 1959 paper of Erdős (see reference cited below) addressed the following problem in [[graph theory]]: given positive integers {{mvar|g}} and {{mvar|k}}, does there exist a graph {{mvar|G}} containing only [[cycle (graph theory)|cycles]] of length at least {{mvar|g}}, such that the [[chromatic number]] of {{mvar|G}} is at least {{mvar|k}}?
It can be shown that such a graph exists for any {{mvar|g}} and {{mvar|k}}, and the proof is reasonably simple. Let {{mvar|n}} be very large and consider a random graph {{mvar|G}} on {{mvar|n}} vertices, where every edge in {{mvar|G}} exists with probability {{math|''p'' {{=}} ''n''<sup>1/''g''−1</sup>}}.
:'''Property 1.''' {{mvar|G}} contains at most {{math|''n''/2}} cycles of length less than {{mvar|g}}.
Line 70:
:<math>\Pr \left (X> \tfrac{n}{2} \right )\le \frac{2}{n} E[X] \le \frac{1}{n} \sum_{i=3}^{g-1} p^i n^i = \frac{1}{n} \sum_{i=3}^{g-1} n^{\frac{i}{g}} \le \frac{g}{n} n^{\frac{g-1}{g}} = gn^{-\frac{1}{g}} = o(1).</math>
: Thus for sufficiently large {{mvar|n}}, property 1 holds with a probability of more than {{math|1/2}}.
:'''Property 2.''' {{mvar|G}} contains no [[Independent set (graph theory)|independent set]] of size <math>\lceil \tfrac{n}{2k} \rceil</math>.
Line 78 ⟶ 79:
when
:<math>y = \left \lceil \frac{n}{2k} \right \rceil.</math> Thus, for sufficiently large {{mvar|n}}, property 2 holds with a probability of more than {{math|1/2}}.
For sufficiently large {{mvar|n}}, the probability that a graph from the distribution has both properties is positive, as the events for these properties cannot be disjoint (if they were, their probabilities would sum up to more than 1).
Here comes the trick: since {{mvar|G}} has these two properties, we can remove at most {{math|''n''/2}} vertices from {{mvar|G}} to obtain a new graph {{math|''G′''}} on <math>n'\geq n/2</math> vertices that contains only cycles of length at least {{mvar|g}}. We can see that this new graph has no independent set of size <math>\lceil \frac{n'}{k} \rceil</math>. {{math|''G′''}} can only be partitioned into at least {{mvar|k}} independent sets, and, hence, has chromatic number at least {{mvar|k}}.
| |||