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.

$\endgroup$
4
  • $\begingroup$ Did you mean $k=\lfloor\sqrt{2n}\rfloor$? $\endgroup$
    – Thomas Andrews
    Commented Oct 3, 2012 at 20:18
  • $\begingroup$ Yes, I did - sorry about that. $\endgroup$
    – Quantumpencil
    Commented Oct 3, 2012 at 20:21
  • $\begingroup$ The $[ \cdots]$s are redundant with the $\lfloor\cdots\rfloor$ unless I am misunderstanding what you mean by $\lfloor[\sqrt{2n}]\rfloor$ $\endgroup$
    – Thomas Andrews
    Commented Oct 3, 2012 at 20:25
  • $\begingroup$ Aye, a result of mixing up sqrt{} and sqrt[]. too much Mathematica. Fixed now $\endgroup$
    – Quantumpencil
    Commented Oct 3, 2012 at 20:29

2 Answers 2

Reset to default
1
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Thanks for the hint; I am returning to ask what is meant by $o(n^2)$? We've not yet encountered this function in my course, or if we have we're calling it something else. I also have a few further questions about the problem(Sorry for the break, was finishing another problem set) If I'm understanding your hint correctly from going and reading about greedy algorithms on wikipedia, I want to choose at say the $nth$ step, the vertex which has the largest red neighborhood that intersects with the most red neighborhoods of the vertices in $K_k$ without forming a triangle, is the choice we want.*con $\endgroup$
    – Quantumpencil
    Commented Oct 5, 2012 at 15:41
  • $\begingroup$ If we look at the graph at the jth step, after adding such a vertex, I'm still how to bound number of vertices that are in the graph $K_k$, or more alarmingly, the number of edges (from which I could calculate or at least bound $j$ using $j(j-1)=\vert E(G)\vert$. Am I approaching the algorithm wrong? Are the inequalities part of the algorithm? (That the cost of every other edge adjacent to $K_k$ in $K_n$ must be less than the cost of the one I added), or does it come from a clever observation about the constraint on $K_n$, and the max size of the red neighborhood of a given vertex? $\endgroup$
    – Quantumpencil
    Commented Oct 5, 2012 at 15:58
  • $\begingroup$ Greedy algorithm is actually not the best choice of words here; my argument is more like "choose a set of vertices with no red triangles so that no matter what vertex you add to that set, you will get a red triangle." (Basically taking a maximal set satisfying the conditions.) Then, think about the red triangles you will get; what will it mean that they have no edges in common? $\endgroup$
    – only
    Commented Oct 5, 2012 at 17:17
  • $\begingroup$ The maximal number of vertices shared by any two triangles is one. Furthermore, since no two triangles red-share more than one vertex, we can do something like: Add a vertex $v_1$, giving us k+1 and n-k-1 vertices in G and the complement, and creating a red triangle. Add another vertex $v_2$, which must also create a triangle in $K_k\cup v_2$. If we the set of vertices ${v_i}$ not in $K_k$ create exactly one triangle that shares exactly 1 vertex with the triangles created by $i\neq i'$, that should give us the maximal number of vertices in the complement of a maximal $K_k$. On the right track? $\endgroup$
    – Quantumpencil
    Commented Oct 6, 2012 at 20:48
  • $\begingroup$ also, if not, I think I'd like the "answer" now - not the rigor, but the method - largely because I think I've spent way more than a reasonable amount of time on this problem, which doesn't seem like it should be this hard, and problem sets for next week are already up -_- $\endgroup$
    – Quantumpencil
    Commented Oct 6, 2012 at 20:54
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This is interesting - I will try to follow through on this soon. $\endgroup$
    – Quantumpencil
    Commented Oct 5, 2012 at 16:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .