6
$\begingroup$

Let $\kappa$ be an infinite cardinal. Consider the following example to $2^\kappa\nrightarrow (3)^2_\kappa$.

$V$ is a set of vertices, each of which is an element of $2^\kappa$. Color the edge between two vertices $f,g\in 2^\kappa$ by the least ordinal on which $f,g$ disagree. It follows that there is no homogeneous set of size $3$, i.e. there is no triangle with all three edges the same color.

More is true: There is no closed walk of length 3,5,7,... which is monochromatic, i.e. all edges are the same color.

Definition:A closed walk consists of a sequence of vertices starting and ending at the same vertex.

Question: Can you find an example to $2^\kappa\nrightarrow (3)^2_\kappa$, therefore no monochromatic triangles are allowed, but which has closed walks of length $n$, for any odd number $n>3$?

Improve this question
$\endgroup$
2
  • $\begingroup$ This example works even when $\kappa$ is finite. Maybe a good question could also be asked in the finite case, say replace the quantifier with "for any odd $n$, $3<n \leq \kappa$." $\endgroup$
    – Monroe Eskew
    Feb 9, 2016 at 19:40
  • $\begingroup$ @MonroeEskew My interest is in the infinite case, but now that you mentioned, the question can also be asked in the finite case too. I would like to see an example with $\kappa$ infinite. $\endgroup$
    – Ioannis Souldatos
    Feb 9, 2016 at 19:50

1 Answer 1

Reset to default
3
$\begingroup$

The answer is yes. In fact, we can get an example by slightly modifying your example.

Let $V = 2^\kappa \cup \{a,b,c,d,e\}$. Color the edges $ab$, $bc$, $cd$, $de$, and $ea$ with some ordinal $< \kappa$, say $0$. Color all other edges from $a$ with a different color, say $A$. Color all other edges from $b$ with a different color, say $B$. Similarly for $c$, $d$, and $e$. The remaining edges are all between elements of $2^\kappa$, and we color them just as you did in your example, with the least ordinal on which they disagree. This gives a coloring of $V$ with $\kappa$ colors, namely $\kappa \cup \{A,B,C,D,E\}$. We have a $5$-cycle in color $0$. We obviously have no triangles in colors $A,B,C,D,E$, and we have no triangles in our other colors $> 0$ because there are no triangles in your example. We have no triangles in color $0$ because in that color we only added a $5$-cycle that is not connected to anything else.

This shows that we can extend your example to one including a $5$-cycle in color $0$ by using five new colors and five new vertices. But we didn't use any specific properties of your example -- any example would have done just fine -- and the number $5$ wasn't special either. So after adding a $5$-cycle in color $0$, we can then add a $7$-cycle some other color, a $9$-cycle in some other color, etc. In fact, we can add monochromatic $n$-cycles for any set of odd $n$ we like, using any colors we like. You can even iterate the construction transfinitely ($\kappa$ steps) to get a graph of size $2^\kappa$ colored in $\kappa$ colors with no monochromatic triangles, but $\kappa$ $n$-cycles in every color for every odd $n > 3$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ The answer is basically the powerset example, plus a triangle-free graph of size $\kappa$ that contains $n$-cycles for every odd $n>3$. Although I did not write it in the question, I was thinking the resulting structure to be "generic" enough. For instance, to have $n$-cycles for each color. In your example we get $n$-cycles for only the new colors (A,B,C,D,E, etc.) $\endgroup$
    – Ioannis Souldatos
    Feb 10, 2016 at 19:31
  • $\begingroup$ Now the finite case becomes more interesting because you can't just add nodes to the powerset example. $\endgroup$
    – Monroe Eskew
    Feb 10, 2016 at 21:33
  • $\begingroup$ @MonroeEskew: The finite case can be solved by observing that in Ioannis's coloring of $2^n$, one color (namely $n-1$) is used very few times. In fact, the graph we get by looking at only $n-1$-colored edges is just a sum of $2^{n-1}$ copies of $K_2$. By adding in a few edges, one can keep this graph triangle-free while adding cycles of length $m$ for every $4 \leq m \leq 2^n-1$. In other words, you can start with Ioannis's coloring and then change some edge colors to $n-1$ to get an $n$-colored graph with no monochromatic triangles, but many monochromatic cycles (in one color). $\endgroup$
    – Will Brian
    Feb 11, 2016 at 15:48
  • $\begingroup$ @IoannisSouldatos: Yes, I agree that the construction is a bit ad hoc. However, do notice that, while we have introduced $5$ new colors, our cycle is in an old color. This is why a transfinite iteration allows you to get odd cycles in every color eventually. I agree, though, that a nice, symmetric example would be more satisfying. $\endgroup$
    – Will Brian
    Feb 11, 2016 at 15:52

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.