Bound the number of red edges in a red-blue coloring of $K_{n}$ such that no two red triangles share an edge

Question

Denote by $K_n$ the complete graph with $n$ vertices. Let $RE(n)$ be maximum number of red edges in a red-blue coloring of $K_{n}$ such that no two red triangles share an edge. I want to show that $RE(n)=o(n^2)$, or preferably the stronger result that I suspect: $RE(n)\leq O(n^{3/2})$.

The original problem: Show that in any red-blue coloring of $K_n$ such that no two red triangles share an edge, there exists a $K_{\lfloor\sqrt{2n}\rfloor}$ containing no red-triangles. I reduced this problem to the problem above.

Answer 1

It's an interesting task. Here we formulate a monochromatic version of this problem equivalent to the color one.

Theorem. If $G$ is a graph of order $n$ in which each edge enters at most one triangle, then $G$ contains an induced triangle-free subgraph of order at least $\sqrt{2n}$.

Here is a brief proof of this theorem.

Denote $q=[\sqrt{2n}]$ and assume that $n\geq3$. We will say that a subset of vertices $S\subset V(G)$ has no triangles if $G[S]$ is an induced triangle-free subgraph. We must find a subset without triangles containing $\geq q$ vertices.

1. Let the graph $G$ have a vertex $v$ such that $\deg(v)=q-1$.

Let $N_G(v)$ be all neighbors of $v$ and $u\notin N_G(v)\cup\{v\}$ (at $n\geq3$ we have $q<n$). The subset $N_G(v)\cup\{u\}$ has no triangles and $|N_G(v)\cup\{u\}|=q$.

2. Let $\deg(v)\leq q-2$ for each vertex $v\in V(G)$.

Now let $S\subset V(G)$ be a maximal subset without triangles and $|S|=s$.

Since $\deg(x)\leq q-2$ for each vertex $x\in S$, the number of edges of the graph $H=G[S]$ is at most $s(q-2)/2$. Because each edge enters at most one triangle we have $$ |T|\leq|E(H)|\leq s(q-2)/2. $$ If $|S|+|T|<n$, then there exists a vertex $v\in V(G)$ and $v\notin S\cup T$ and the set $S\cup\{v\}$ has no triangles. This contradicts the maximality of $S$.

Thus $|S|+|T|\geq n$. So $$ n\leq|S|+|T|\leq s+s(q-2)/2=sq/2\ \Rightarrow\ s\geq2n/q\geq\sqrt{2n}. $$

This is what we needed to prove.

Answer 2

This problem can be solved by result of this problem. If you let {$A_i$} be the family of triangle vertex sets of $G$, you'll find this two problems are same.

https://artofproblemsolving.com/community/c6h48298p305430

It was problem from Romanian IMO team selection test, 1999.

Answer 3

The answer to the title question is that $\operatorname{RE}(3)=3$ and $\operatorname{RE}(n)=\lfloor n^2/4\rfloor$ for $n\ne3$.

To save typing let $f(n)=\operatorname{RE}(n)$. It is easy to verify that $f(3)=3$ and $f(n)=\lfloor n^2/4\rfloor$ for $n=1,2,4$. Moreover, it's easy to see that $f(n)\ge\lfloor n^2/4\rfloor$ for all $n$; just color the edges of $K_n$ so that the spanning subgraph formed by the red edges is a complete bipartite graph $K_{\lceil n/2\rceil,\lfloor n/2\rfloor}$. We will prove by induction that $f(n)\le\lfloor n^2/4\rfloor$ for $n\gt4$.

First, by counting in two ways the pairs $(e,v)$ consisting of a red edge $e$ and a vertex $v$ not incident with $e$, we see that $f(n)\cdot(n-2)\le nf(n-1)$, i.e., $$f(n)\le\left\lfloor\frac n{n-2}f(n-1)\right\rfloor$$ for $n\gt2$.

For the inductive step, let $n\gt4$ and assume that $f(n-1)\le\lfloor(n-1)^2/4\rfloor$; we have to show that $f(n)\le\lfloor n^2/4\rfloor$. We consider two cases depending on the parity of $n$.

Case 1. $n=2k$ and $f(n-1)=f(2k-1)\le\lfloor(2k-1)^2/4\rfloor=k(k-1)$. Then $$f(n)=f(2k)\le\frac{2k}{2k-2}k(k-1)=k^2=\left\lfloor\frac{n^2}4\right\rfloor.$$ Case 2. $n=2k+1$ and $f(n-1)=f(2k)\le\lfloor(2k)^2/4\rfloor=k^2$. Then $$f(n)=f(2k+1)\le\left\lfloor\frac{2k+1}{2k-1}k^2\right\rfloor\le k^2+k=\left\lfloor\frac{n^2}4\right\rfloor$$ since $$\frac{2k+1}{2k-1}k^2\lt k^2+k+1.$$