Timeline for Non-trivial parity maps in graphs
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 3, 2018 at 7:49 | comment | added | Dominic van der Zypen | Thanks @PeterHeinig, sorry for being a bit sloppy! I'll leave the statement as is, as it was my mistake, and if it deleted, the comments pointing to a deleted line of mine might confuse other readers. It was a good idea of yours just to strike the false statement but not delete it | |
| Mar 2, 2018 at 15:59 | history | edited | Peter Heinig | CC BY-SA 3.0 |
For completeness, and to prevent the (admittedly unlikely) eventuality that a future reader who needs exactly this concept and does not read till the comments is misled, I struck out a false statement, leaving it visible, so as to keep a comment meaningful.
|
| Mar 2, 2018 at 15:59 | comment | added | Peter Heinig | Dear @Dominic van der Zypen: for completeness, and to prevent the (admittedly unlikely) eventuality that a future reader who needs exactly this concept (and does not read up to the comments-section) is misled, I struck out a false statement, leaving it visible, so as to keep a comment meaningful. I hope you agree with this (if MO aspires to be some sort of living reference work, then even small errors should be corrected), but of course, needless to say, you can also delete the statement entirely if you prefer. | |
| Mar 2, 2018 at 15:44 | comment | added | Peter Heinig | For completeness, let me note that, curiously, $n=4$ is the only natural number such that the $n$-circuit $C_n$ does not admit a non-trivial parity map. One can even push this to $n\in\{0,1,2\}$ if one agrees that '$n$-circle'='$n$-vertex 2-regular connected multigraph', then this everything works. (For $n=1$, it's the loop.) The non-trivial parity maps in the cases $n\in\{3\}\cup\{k: k\geq 5\}$ are unique and easy to find. In a sense, you have discovered a characterization of the number $4$: a number $n$ is equal to $4$ iff the 'circle' on $n$ vertices admits a nontrivial parity map. | |
| Mar 2, 2018 at 11:18 | vote | accept | Dominic van der Zypen | ||
| Mar 2, 2018 at 10:45 | answer | added | Christopher Purcell | timeline score: 8 | |
| Mar 2, 2018 at 10:24 | comment | added | Philipp Lampe | If $n$ is even, then the complete bipartite graph $K_{n,n}$ has minimal degree $n$ and does not admit a non-trivial parity map. | |
| Mar 2, 2018 at 10:01 | comment | added | Peter Heinig | The statement "for $n\geq 4$ the circle $C_n$ does not have a non-trivial parity map" is false. E.g., for $n=6$, a non-trivial parity map does exist, e.g. (the matrix is meant to represent a circuit, e.g. by reading it clockwise): $\begin{matrix} 1 \quad- & 0\quad- & 1\quad \\ \hspace{-18pt}| & & \hspace{-10pt}|\\ 1\quad- & 0\quad - & 1\quad\end{matrix}$. | |
| Mar 2, 2018 at 8:12 | history | asked | Dominic van der Zypen | CC BY-SA 3.0 |