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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented Feb 11, 2016 at 15:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .