Timeline for existence of a certain subset of vertices in a graph
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 27, 2018 at 6:57 | comment | added | bof | The unit distance graph on $\mathbb R^n$ is easy. The cases $n=0$ (finite graph) and $n=1$ (locally finite) are trivial. For $n\ge2$ an easy transfinite construction (with the axiom of choice of course) gets us a set $A\subset\mathbb R^n$ such that $|N(x)\cap A|=0$ for $x\in A$ while $|N(x)\cap A|=|\mathbb R|$ for $x\in\mathbb R^n\setminus A$. | |
| Nov 25, 2018 at 3:07 | vote | accept | hookah | ||
| Nov 24, 2018 at 12:46 | comment | added | bof | At least it's true for locally finite graphs, by compactness. Right? | |
| Nov 23, 2018 at 22:19 | comment | added | fedja | @bof Hard to tell... Of course, when we have some sort of compactness principle, we can reduce the question to the finite case, but what would you do in the case of the unit distance graph for the points in $\mathbb R^n$, for instance? | |
| Nov 23, 2018 at 5:49 | comment | added | bof | And of course the same argument shows that, for any nonnegative integer $d$ and any finite graph $G=(V,E)$, there is a set $M\subseteq V$ such that $M=\{x\in V:|N(x)\cap M|\le d\}$. Is this also true for infinite graphs? | |
| Nov 23, 2018 at 3:31 | history | answered | fedja | CC BY-SA 4.0 |