MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
3

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

flag

2 Answers

1

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

link|flag
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). – Wlodzimierz Holsztynski Feb 16 at 20:50
0

@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

link|flag
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. – Wlodzimierz Holsztynski Feb 17 at 6:20

Your Answer

Get an OpenID
or

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