Timeline for Representing graphs by sets of small symmetric difference
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 9, 2021 at 12:03 | comment | added | Farmer S | For infinite graphs, the statement is equivalent to transitivity. (If $G$ is infinite and transitive, and $x\in V$, let $C_x$ be the transitively connected component $\{y\in V\bigm|xEy\}$, and for such a component $C$, let $A_C$ be a subset of $V$ of size $\mathrm{card}(V)$, with the $A_C$'s pairwise disjoint. Then define $\psi(x)=A_{C_x}\backslash\{x\}$, and note this works, using $\kappa=\mathrm{card}(V)$, or using $\kappa=3$, since for $x\neq y$, we have $xEy$ iff $C_x=C_y$ iff $A_{C_x}=A_{C_y}$ iff $\psi(x)\Delta\psi(y)=\{x,y\}$ iff $\psi(x)\Delta\psi(y)$ has card $<\kappa$.) | |
| Aug 9, 2021 at 9:11 | vote | accept | Dominic van der Zypen | ||
| Aug 9, 2021 at 0:08 | answer | added | Mikhail Tikhomirov | timeline score: 2 | |
| Aug 8, 2021 at 14:17 | comment | added | Dominic van der Zypen | Good point @FarmerS - thanks for noticing! - I would be delighted in a counterexample for any graph where no $\kappa$, finite or infinite, with the property stated in the question exists | |
| Aug 7, 2021 at 20:29 | comment | added | Farmer S | Sorry, if $\kappa$ is infinite, that is. | |
| Aug 7, 2021 at 20:21 | comment | added | Farmer S | Doesn‘t the condition imply the graph is transitive? | |
| Aug 7, 2021 at 20:07 | history | asked | Dominic van der Zypen | CC BY-SA 4.0 |