3
$\begingroup$

Let $X$ be an infinite set and consider the undirected clique graph $Q(X)$. That is, $Q(X)$ has an edge between $x$ and $x'$ in $X$ for every distinct $x$ and $x'$.

My question is this:

In what circumstances can we orient the edges in $Q(X)$, such that each $x$ has only finitely many outgoing edges (and thus necessarily infinitely many incoming edges).

We can rephrase the question as a graph colouring question. Consider a set of colours $C$, having the same cardinality as $X$, and choose a fixed but arbitrary isomorphism $c: X\cong C$.
In what circumstances can we $C$-colour the edges in $Q(X)$ such that

  • For each $c$, only finitely many edges have colour $c$.
  • If an edge between $x$ and $x'$ has colour $c$ then $c=c(x)$ or $c=c(x')$.

Advice is welcome. Thank you.

$\endgroup$
3
  • $\begingroup$ so, the way you've phrased the first formulation, you are simply asking for a $C$-coloring of $Q(X)$ such that every color appears only finitely many times? this can always be done. let $<$ be an arbitrary linear ordering on $X$, and let $f:X\times X\to C$ be any bijection. then color the edge $\{x,x'\}$, where $x<x'$, as $f(x,x')$. in this coloring each color appears at most once $\endgroup$ Jun 2, 2022 at 16:39
  • $\begingroup$ but this is really just the fact that the number of edges in $Q(X)$ has the same cardinality as $X$ and hence the same cardinality as $C$. are you sure it's what you meant to ask? it's not at all clear to me that your second formulation is equivalent $\endgroup$ Jun 2, 2022 at 16:46
  • 1
    $\begingroup$ Many thanks @AtticusStonestrom. You're right that my "colourings" version of the question was incorrect. This should now be fixed: if you see any other errors please do not hesitate to let me know. Thanks again. $\endgroup$
    – Jim
    Jun 2, 2022 at 19:37

1 Answer 1

3
$\begingroup$

You are asking, when does the complete graph on an infinite set $X$ admit an orientation in which every vertex has finite outdegree? The answer is that such an orientation exists if and only if $X$ is countable.

Suppose $X$ is countable. Without loss of generality, assume $X=\mathbb N$. Let the edge between vertices $x$ and $y$ be directed from $x$ to $y$ if and only if $x\gt y$. Plainly each vertex has finite outdegree.

Suppose $X$ is uncountable. Assume for a contradiction that the complete graph on $X$ is oriented so that each vertex has finite outdegree. Choose a countably infinite subset $S$ of $X$. Then the set $N^+[S]$ consisting of the vertices in $S$ and their outneighbors is also countable. Since $X$ is uncountable we can choose a vertex $x\in X\setminus N^+[S]$. Then every vertex is $S$ is an outneighbor of $x$, so $x$ has infinite outdegree, contradicting our assumption.

The latter argument assumes the axiom of choice. Without the axiom of choice, there can be an uncountable tournament (oriented complete graph) in which each vertex has finite outdegree. For instance, such a tournament exists if the axiom of choice for countably many $3$-element sets is false, while the axiom of choice for countably many $2$-element sets is true.

$\endgroup$
1
  • $\begingroup$ Nice. Many thanks. $\endgroup$
    – Jim
    Jun 3, 2022 at 8:16

You must log in to answer this question.

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