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

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).

share|improve this question

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer
    
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). –  Włodzimierz Holsztyński Feb 16 '13 at 20:50

@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

share|improve this answer
    
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. –  Włodzimierz Holsztyński Feb 17 '13 at 6:20

Your Answer

 
discard

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

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