4
$\begingroup$

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$$

QUESTION:   Does every set   $X$   admit a 2-coloring   $c$   of its triangles such that the induced coloring of every tetrahedron is of the   $(2\ 2)$ type?   And if the answer is NOT, then what is the smallest cardinality   $|X|$   for which   $X$   does not admit such   $c$   (then such cardinality must be finite)?

A PARTIAL RESULT:   If   $|X| \le 6$   then there exists a 2-coloring of triangles such that all tetrahedra are colored   $(2\ 2)$.

(Of course, if such a coloring exists for a set $X$ then it exists--it induces--a similar coloring of triangles in every subset of $X$, hence together with any good cardinal number all smaller cardinal numbers are good too).

$\endgroup$

2 Answers 2

1
$\begingroup$

When $|X|=7$, no such coloring exists.

In this case there are 35 triangles and 35 tetrahedra. If $A$ is a tetrahedron, let $(\alpha_A,\beta_A)$ be its type. Each triangle in $X$ is a subset of exactly $4$ tetrahedra, so if $$\sum_{T\subseteq X, |T|=3}c(T)=n$$ then $$\sum_{A\subseteq X, |A|=4} \beta_A = 4n$$ If each $A$ were of type $(2,2)$, this would imply $4n=70$.

$\endgroup$
1
  • $\begingroup$ Thank you, @stepan, very nice! It was worthy of my frustration. I posted my question, so eager to post a good one, and went to sleep. When I woke up (at noon :-)) I got my answer, as posted below, while my Internet connection failed me (I am typing these words from a library). My solution is quite routine, and I was annoyed with myself for overlooking it earlier, for making what may be considered an unnecessary post. But your pretty solution justified my entry, I think. Thank you again. (BTW, I have my 6-point example already for a week or more but it took my post here to see the rest). $\endgroup$ Feb 16, 2013 at 20:50
0
$\begingroup$

@Stepanp21 has answered my question. Here is another solution:

Let   $|X|=7$.   Let   $c$   be a coloring of triangles, and let   $p\in X$.   Define the induced coloring   $b = b_{c\ p} : \binom Y2\rightarrow \{0\ 1\}$   of edges of   $Y := X\setminus \{p\}$   as follows: $$ \forall_{e\in\binom Y2}\quad b(e) := c(e\cup\{p\})$$

Since   $|Y|=6$   there is a uni-color (monochromatic) triangle   $A\subseteq Y$,   meaning that all of its three edges got the same color from edge coloring   $b$.   Then tetrahedron   $A\cup\{p\}\subseteq X$ has (at least) three triangular faces of the same color, as colored by   $c$.   END of PROOF

$\endgroup$
1
  • $\begingroup$ Actually, there are at least two different monochromatic triangles in $Y$ (see above)--it's the first and most classical elementary theorem of Ramsey Theory. Thus every point $x\in X$ is a vertex of at least two different tetrahedra which are not of the $(2\ 2)$ type. $\endgroup$ Feb 17, 2013 at 6:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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