0
$\begingroup$

Given a 2-coloring of $\ E(K_n)$ such that a red edge belongs to no more than one unique Red triangle, show that $\exists \ K_k \subset K_n$ which contains no Red triangle, with $\ k>\lfloor\sqrt{2n}\rfloor$.

Working through the first few example complete graphs, I've not been able to figure out where this bound comes from. If possible, I'd prefer not to be provided with the proof outright, but rather to be informed relevant results or what might give me some intuition concerning the origin of the bound (What exactly equals the square of double the number of vertices in a complete graph with edge disjoint monochromatic triangles? As far as I can tell, not the number of monochromatic triangles (that depends on the coloring), though that's my first intuition (There are at most $n-\lfloor\sqrt{2n}\rfloor$ edge-disjoint monochromatic triangles for any coloring of the edges, and therefore we can remove one vertex from each triangle, the result will follow.)

Thanks for any hints, I will accept.

  • 0
    Aye, a result of mixing up sqrt{} and sqrt[]. too much Mathematica. Fixed now2012-10-03

2 Answers 2

1

In this case, this seems to be a bound that just arises when one does the algebra, instead of something having a specific meaning.

Here's a hint: Try a greedy algorithm; add elements to the complete subgraph until you can't add anymore, and then bound the number of elements in the complete subgraph. When you solve the inequalities that arise, you should get the desired bound.

In general, for greedy/probabilistic arguments, the end bound won't mean something; it'll just be something you get from the algebra.

Since you seem interested in related results, I'll mention that it is possible to prove that you will have $o(n^2)$ red triangles in such a graph, but, if I recall correctly, you can get $n^{2-\epsilon}$ for all $\epsilon.$ My first statement follows from the Triangle Removal Lemma; I do not remember the proof of the second.

  • 0
    Ah, ok, I get it. So then there are at most $\frac{k^2}{4}$ red edges in $K_k$, since the red edges form a triangle free graph. Then the number of vertices not in $K_k$ is strictly less than $\frac{k^2}{4}$. Equivalently, the number of vertices in $K_k$ is greater than or equal to $\frac{k^2}{4}$. The bound follows by combining the inequality n>k>\frac{k^2}{4}. Thanks2012-10-07
0

I didn't play it through, but maybe treating this as an eigenvector problem can help: We may recolour any red edge blue that is not part of any red triangle. Then the matrix $A$ with $a_{i,j}=1$ iff there is a red edge from $i$ to $j$ has the folowing properties:

  • $A$ is symmetric hence admits an orthogonal basis of eigenvectors with real eigenvalues $\lambda_i$.
  • The sum of all eigenvalues is $\sum \lambda_i=\operatorname{tr} A=0$.
  • The diagonal entires of $A^2$ are the number of length-2 paths of a point to itself, that is the (red) degree of that vertex.
  • The diagonal entires of $A^3$ are the number of length-3 paths of a point to itself, that is again the (red) degree of that vertex (one path for each triangle in two different directions).
  • From the last two remarks, $\sum\lambda_i^2 = \sum\lambda_i^3$
  • Everey isolated red triangle gives rise to two eigenvalues $-1$ and one eigenvalue $+2$.

But I admit, I don't know yet how to make use of this exactly to find "nice" vertices to remove, so maybe this should rather have been a lengthy comment than an answer.

  • 0
    This is interesting - I will try to follow through on this soon.2012-10-05