6
$\begingroup$

We have a graph $G$. The vertices of $G$ are a measurable subset of $\mathbb{R}^n$ for some $n$. The degree of each vertex is bounded by some absolute finite constant $K$.

Q1. Does $G$ have a maximal independent set? (This is a set of mutually non-adjacent vertices such that each vertex not in the set is adjacent to at least one vertex in the set.)

Q2. If the answer to Q1 is "yes", can we find a maximal independent set which is measurable?

As you can probably tell, my set theory is weak.

$\endgroup$
5
  • $\begingroup$ The first question is a standard application of Axiom of Choice (more precisely, Zorn's lemma) if you are happy with using that. $\endgroup$
    – Algernon
    Feb 19, 2018 at 3:23
  • $\begingroup$ @Algernon : I was hoping that the bounded degree allowed AC to be avoided. $\endgroup$ Feb 19, 2018 at 5:17
  • $\begingroup$ @BrendanMcKay: perhaps restricting to mere Borel sets (instead of arbitrary measurable sets) could lead you to results not using AC. I am not sure about that, though. In descriptive graph combinatorics, Borel sets tend to be studied more than arbitrary measurable sets, because the emphasis in descriptive graph combinatorics is set-theoretic definability. $\endgroup$ Feb 19, 2018 at 8:38
  • $\begingroup$ While Algermon has somewhat hinted at it already, it has not been spelled out explicitly in this thread yet that, assuming ZFC, for any specified finite set $\mathcal{S}$ of finite graphs, absolutely every graph (no measurability required) contains a subset which is inclusion-maximal w.r.t. the property of not containing any of the members of $\mathcal{S}$ as a subgraph. The OP's question Q1 is the special instance $\mathcal{S}=\{K^2\}$. A proof via the obvious application of Zorn's lemma ($\leftrightarrow$ AC) works because the union of a chain is again $\mathcal{S}$-free, because of [..] $\endgroup$ Feb 19, 2018 at 16:12
  • $\begingroup$ [...] the two finiteness-conditions. (This argument does not work if at least one of (0) number of forbidden subgraphs in $\mathcal{S}$, (1) number of vertices in the forbidden graphs in $\mathcal{S}$ is permitted to be infinite.) It is of course a fascinating problem to find out under what additional conditions AC can be (partly) avoided. $\endgroup$ Feb 19, 2018 at 16:13

2 Answers 2

6
$\begingroup$

A relevant statement is Proposition 4.2. in

[KST1999] A. S. Kechris, S. Solecki, S. Todorcevic, Borel Chromatic Numbers. Advances in Mathematics 141, 1-44 (1999)

In short, the proposition shows that if you settle for Borel sets instead of arbitrary measurable sets, then Q1 and even Q2 seem(problem) to admit of an affirmative answer, and then even in greater generality (only local countability, not boundedness, of the vertex degrees required).(caution)

In detail,

Proposition 4.2 ([KST1999, p. 12]) If $X$ is a standard Borel space, and if $R\subset X\times X$ is a symmetric irreflexive relation, and if

(range) for each Borel set $Y\subseteq X$ the set$\quad$ $R(Y) := \{x\in X\colon\ \exists y\qquad y\in Y\quad\wedge\quad (y,x)\in R\}$ is a Borel set, too, and

(chrom) if the Borel chromatic number of $(X,R)$ is countable,

then $X$ contains a maximal $R$-independent set, which moreover is Borel (and hence measurable).

To prepare for a conditional answer to your question, one also should quote (many thanks to Francis Adams for pointing this out):

Proposition 4.5 ([KST1999, p. 13]) If $X$ is a standard Borel space, and if $R\subset X\times X$ is an irreflexive relation (not necessarily symmetric), and if

(preimage) for each Borel set $Y\subseteq X$, the set $R^{-1}(Y):=\{x\in X\colon\ \exists y\qquad y\in Y\quad\wedge\quad (x,y)\in R\}$ is a Borel set, too, an

(degree) (*) each $x\in X$ has finite degree in the undirected graph obtained from $R$ by symmetrizing the relation,

then the Borel chromatic number of $(X,R)$ is countable.

Now to your question proper. Suppose $R$ is any irreflexive symmetric relation on, not only a measurable, but a Borel vertex-set. (This assumption is why this answer is only a conditional answer to your question; arbitrary measurable sets are not covered, and would not allow to conclude that the maximal independent set is measurable, as exemplified by Han's example at 2018-02-19 03:22:58Z). Suppose that as in the OP, $R$ has bounded vertex-degree; then (degree) in Proposition 4.5 holds.

Since $R$ is symmetric, for any $Y\subseteq X$ we have $R(Y)=R^{-1}(Y)$.

Now we can conclude the following:

if we could(problem) show that under the hypotheses in the OP it follows that (range)(* *) is true, then first Proposition 4.5 would imply that (chrom) is true, whereupon Proposition 4.2 then would imply that $X$ contains a maximal $R$-independent set, which moreover is Borel (and hence measurable), answering the OP's question affirmatively.

${}$_________________________

(*) In stating the following condition, op. cit. strangely first passes to the undirected graph underlying $R$, but then goes on to speak of an "outdegree" (cf. op. cit. Proposition 4.5); I find this confusing and can't explain this. I take the "out-degree" to simply mean "degree", since after all one is speaking of an undirected graph here.

(* *) Because of $R(Y)=R^{-1}(Y)$, we have (range) $\leftrightarrow$ (premimage).

(caution) An earlier version of this answer erroneously stated that one may then also conclude that the maximal independent set was (topologically-) discrete; this particular additional statement was false. (And quite nonsensical, since in Proposition 4.2 no topology is specified.) I was misled by the unusual usage of 'discrete' in op. cit. (and by my predjudices: I was thinking of the Lebesgue $\sigma$-algebra on $\mathbb{R}^d$, which makes one think of topology), but Propostion 4.2 in op. cit. is more general and does not use 'discrete' in the topological sense: unusually, 'discrete' in op. cit. is nothing but a synonym for what in graph-theory is called 'independent' (i.e., set no two members of which are connected by an edge). My error is understandable: in the setting of Borel-spaces, taking 'discrete' to have its usual topological meaning is quite reasonable, so why would one rummage through the article to find the definition of 'discrete'?

However, my statement that the maximal independent set could in addition be assumed to be discrete was not only not the intended one, but it is also materially false: a counterexample is the graph with vertex-set equal to the unit-circle, and two points adjacent if and only if one can be carried to the other by rotating the circle by a rational angle. (This is precisely the complement of the graph defined by Han at 2018-02-19 03:22:58Z.)

In this graph, the set $\{ (\cos(\varphi),\sin(\varphi))\colon\quad \varphi\in\mathbb{Q}\cap[0,2\pi)\}$ is a maximal independent set. Of course---being countable---it is Borel (as it must by Proposition 4.2.) but, needless to say, it is not (topologially-)discrete.

(problem) The problem is that, some helpful comments notwithstanding, I still don't see whether the following is true

(problem) For any standard Borel space $X$, any Borel set $Y\subseteq X$, and any irreflexive symmetric relation $R\subset X\times X$ with finite degree at each point, does it follow that he set $R(Y) = \{x\in X\colon\ \exists y\qquad y\in Y\quad\wedge\quad (y,x)\in R\}$ is a Borel set, too?

I did not look long into this matter, but in view of some similar results depending on the topology, I would rather suspect that (problem) has negative answer. Some results I looked at involve images of Borel sets under finite-to-one functions, which seems somewhat related, but $R$ need not be a function, and moreover some of the relevant results make conditions on topologies, which one does not have available here at all.

$\endgroup$
4
  • 1
    $\begingroup$ In the KST paper you mention, proposition 4.5 states that every locally finite Borel graph has countable Borel chromatic number. And proposition 4.6 improves this result for bounded degree graphs. $\endgroup$ Feb 19, 2018 at 16:05
  • $\begingroup$ @FrancisAdams: reading closely, it now seems to me that it is still open whether (hypotheses of OP)$\rightarrow$(condition 2. in Proposition 4.2). The reason is that in both Proposition 4.4 and 4.5 it is assumed that all neighbourhoods of arbitrary vertex subsets be Borel sets (cf. the notation $P^{-1}(Y)$ in op. cit.); this is not assumed by the OP, and is not guaranteed even if the vertex set $X$ is assumed to be a standard Borel space. Currently it seems I cannot improve the post. $\endgroup$ Feb 19, 2018 at 16:37
  • $\begingroup$ The way it looks is that the 'in particular' in 4.5 says the extra assumption is satisfied for locally finite graphs and graphs generated by functions. You can also handle the locally finite case by looking at proposition 4.3. There it says a graph (with R(Y) Borel when Y is Borel) has countable Borel chromatic number iff you can find a finer Polish topology where no point is in the closure of its set of graph neighbors. If each vertex only has finitely many points, this is clearly the case. $\endgroup$ Feb 19, 2018 at 19:12
  • $\begingroup$ This is very interesting and enlightening. Please come back here with more information if you come across any. $\endgroup$ Feb 21, 2018 at 7:54
8
$\begingroup$

The answer to Q1 is yes by Zorn's lemma. The answer to Q2 is no: Consider the 2-regular graph G whose vertex set is a circle whose two vertices are connected iff one is mapped to the other through rotation by a fixed irrational angle t. For non trivial results along these directions search for the literature on descriptive graph combinatorics.

$\endgroup$
1
  • $\begingroup$ While the following will be known to most readers, for completeness one should add that the example given to answer Q2 negatively is essentially Giuseppe Vitali's construction of a non-measurable set; this is presented in various ways, but a presentation perfectly apposite to Han's example is in Exercise 10.1 on page 137 of [Jech: Set Theory, Third Edition. Springer 2002]. (Technically, one has to show that continuous map $[0,1]\to S^1$, $x\mapsto (\cos 2\pi x, \sin 2\pi x)$ preserves non-measurability. Alternatively, define graph to have vertex-set $[0,1]$ right-away; circle is irrelevant). $\endgroup$ Feb 19, 2018 at 17:11

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.