5
$\begingroup$

Given a simple graph $G$ [no loops or parallel edges] on six vertices, let $G^c$ denote its complement. It is known that either $G$ or $G^c$ must contain a triangle $T$ in it. [An example of a Ramsey number I think.]

My question came up when I tried to find such a graph on six vertices which had only one $T$ in it or its complement. I believe if I did things right there are none of these. This I tried to check by drawing a copy of each graph $G$ on six vertices which has a $T$ in it, and then looking at the complements to see if any had no $T$'s in them. I found none.

One way to pose my question for a general number $n$ of vertices is then as follows: Consider the set of all graphs $G$ on $n$ vertices, and for each one construct $G^c.$ Count the number of $T$ in $G$ and add that to the number of $T$ in $G^c.$ Finally find the minimal such sum for the given $n$ and call that say $M(n).$ So my above six vertex conjecture is that $M(6)=2.$

By considering a cycle graph on five vertices we find $M(5)=0.$

So going further one could ask if anything is known about this minimum function $M(n)$ for larger $n$ [such as bounds, etc.] And does it have a name?

I would also like to see a simpler way to handle the six vertex case, one not involving drawing all the graphs.

$\endgroup$
  • $\begingroup$ @Yikai Not quite.. looking for a single graph $G$ on six verties whose complement we call $G^c$ and wish to find one such that either $G$ has one triangle and $G^c$ has no triangles, or else the reverse -- $G^c$ has one triangle and $G$ has no triangles. [I believe there are no examples of this...] $\endgroup$ – coffeemath Apr 4 '17 at 2:04
6
+50
$\begingroup$

Suppose each edge of $K_n$ is colored red or blue. Let $r_i$ and $b_i$ denote the red degree and the blue degree of the vertex $v_i.$ Let $t$ denote the number of non-monochromatic triangles, i.e., triangles having at least one edge of each color. Let $a$ denote the number of $2$-colored angles, i.e., pairs $\{e,f\}$ where $e$ and $f$ are adjacent edges of different colors. Observe that $$2t=a=\sum_{i=1}^nr_ib_i.\tag1$$ Case I. $n$ is even, say $n=2k.$

Then the sum (1) is maximized when $\{r_i,b_i\}=\{k,k-1\}$ for each $i,$ and in that case $$t=\frac12\sum_{i=1}^{2k}k(k-1)=k^2(k-1),$$ and so the number of monochromatic triangles is $$M(2k)=\binom{2k}3-k^2(k-1)=\frac{k(k-1)(k-2)}3.$$ Example. For $n=6$ the minimum number of monochromatic triangles is $2.$

Case II. $n=4k+1.$

The sum (1) is maximized when $r_i=b_i=2k$ for each $i,$ and in that case $$t=\frac12\sum_{i=1}^{4k+1}(2k)^2=2k^2(4k+1),$$ and so the number of monochromatic triangles is $$M(4k+1)=\binom{4k+1}3-2k^2(4k+1)=\frac{2k(k-1)(4k+1)}3.$$ Case III. $n=4k+3.$

It's not possible to have $r_i=b_i=2k+1$ for all $i,$ since $2k+1$ and $n=4k+3$ are both odd. The sum (1) is maximized when $r_i$ and $b_i$ are as nearly equal as possible, e.g., when $\{r_1,b_1\}=\{2k,2k+2\}$ and $r_i=b_i=2k+1$ for all $i\ne1.$ In that case $$t=\frac12\left[(2k)(2k+2)+\sum_{k=2}^{4k+3}(2k+1)^2\right]=2k(k+1)+(2k+1)^3=8k^3+14k^2+8k+1,$$ and so the number of monochromatic triangles is $$M(4k+3)=\binom{4k+3}3-(8k^3+14k^2+8k+1)=\frac{8k^3+6k^2-2k}3.$$

Construction of extremal graphs. In cases I and II we can take $G=C_n^{\lfloor n/4\rfloor}$ for the red graph. In case III we start with $C_{4k+3}^k$ and (with vertices numbered cyclically) add the $2k+1$ edges $v_2v_{2k+3},\ v_3v_{2k+4},\dots,\ v_{2k+2}v_{4k+3}.$

References. The function $M(n)$ is OEIS sequence A014557; the general formula is $$M(n)=\binom n3-\left\lfloor\frac n2\left\lfloor\left(\frac{n-1}2\right)^2\right\rfloor\right\rfloor;$$ the original reference is:

A. W. Goodman, On sets of acquaintances and strangers at any party, Amer. Math. Monthly 66 (1959), 778–783.

$\endgroup$
  • $\begingroup$ For a graph $G$ with $n$ vertices,the Goodman article gives a sharp lower bound for $E+F,$ where $E$ is the number of triangles in $G$ and $F$ the number in $G^c.$ So this seems to answer my question for general $n.$ [+1 now, likely accept after I read the article more carefully] $\endgroup$ – coffeemath Apr 4 '17 at 11:53
  • $\begingroup$ How do you show that it is possible to have that kind of coloring?And why is it impossible to have $r_i=b_i=2k+1$ in the case $n=4k+3$? $\endgroup$ – Taha Akbari Apr 22 '17 at 15:40
  • $\begingroup$ @TahaAkbari I "show that it is possible to have that kind of coloring" in the paragraph "Construction of extremal graphs". The impossibility of a $(2k+1)$-regular graph on $4k+3$ vertices follows from the so-called handshaking lemma which says that the degree-sum of a graph is an even number, equal to twice the number of edges. $\endgroup$ – bof Apr 22 '17 at 21:23
  • $\begingroup$ @bof coulld you explain more the part "Construction of extremal graphs" because I am a begginer in graph. $\endgroup$ – Taha Akbari Apr 23 '17 at 11:29
  • $\begingroup$ @TahaAkbari You didn't tell me what part of the construction you don't understand. Perhaps the notation $C_n^k$ is unfamiliar to you? I'm using $C_n^k$ to denote the $k^{\text{th}}$ power of the cycle graph $C_n.$ $\endgroup$ – bof Apr 23 '17 at 11:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.