Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This time my question is related to Ramsey number   $R(4\ 4; 3) = 13$.

DEFINITIONS:   Functions   $c : \binom X3\rightarrow \{0\ 1\}$   are called 2-colorings of triangles in   $X$.   The $4$-element subsets   $A\subseteq X$   are called tetrahedra. Each 2-coloring   $c$   of triangles induces   $(\alpha\ \beta)$-coloring of each tetrahedron   $A$,   where $$\beta := \sum_{T\subseteq A,\ |T|=3}\ c(T)\quad\quad\quad \alpha := 4-\beta$$

A 2-coloring of triangles is called lively   $\Leftarrow:\Rightarrow$   there are no tetrahedra which have all four walls painted in the same color, i.e. when no tetrahedron has coloring of type   $(4\ 0)$ or $(0\ 4)$. Integer   $n\ge 5$   is called lively   $\Leftarrow:\Rightarrow$   an (hence any) $n$-element set admits a lively 2-coloring.

QUESTION:   Let   $n\ge 5$   be an arbitrary lively integer. What is the minimal number   $m:=m_{22}(n)$   for which there exists a 2-coloring of triangles in an $n$-element set such that no tetrahedron has all four walls of the same color, and there are exactly   $m$ tetrahedra with $(2\ 2)$-coloring.

MOTIVATION:   I want to estimate anew   $R(4\ 4; 3)$, from scratch, ignoring the fact that this Ramsey number is perfectly known--it was obtained after years of effort by some mathematicians and computer scientists assisted by computers. So far, my last partial result listed below helped me to obtain only   $R(4\ 4; 3) \le 17$.


  • $m_{22}(5) = 1$
  • $m_{22}(6) = 3$
  • $m_{22}(n) \ge \lceil\frac 15\cdot\binom n4\rceil$     for every lively   $n=5\ 6\ 7\ 8$
  • $m_{22}(n) \ge \lceil\frac {13}{63}\cdot\binom n4\rceil$     for every lively   $n=9\ 10\ 11\ \ldots$

REMARK   Lively integers are simply integers in the range $5\ldots R(4\ 4;3)$--but I pretend that I have no a priori information about this Ramsey number. I am computing it from scratch.

share|improve this question
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.