Timeline for Seymour's second neighborhood conjecture for infinite graphs
Current License: CC BY-SA 4.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 17, 2022 at 21:45 | history | edited | YCor | CC BY-SA 4.0 |
added assumption to avoid trivial counterexample
|
| Dec 17, 2022 at 0:03 | comment | added | bof | As for strongly connected, does there even exist a strongly connected, locally finite, infinite digraph $G$ with $|N^+(x)|\ge|N^{++}(x)|$ for all $x\in V(G)$? | |
| Dec 16, 2022 at 23:58 | comment | added | bof | @TonyHuynh Or just take an infinite sequence $G_1,G_2,G_3,\dots$ of copies of a finite counterexample $G$, and draw an arc from every vertex in $G_n$ to every vertex in $G_{n+1}$. | |
| Dec 16, 2022 at 22:10 | answer | added | bof | timeline score: 8 | |
| Dec 16, 2022 at 15:18 | comment | added | Timothy Chow | @ThomasBloom Ah...that makes sense! I'll leave my comment up in case someone else has the same confusion. | |
| Dec 16, 2022 at 15:05 | comment | added | Thomas Bloom | @TimothyChow Tony Huynh's construction is to show that the infinite, weakly connected, version implies the finite one - take a supposed counterexample $G$ to the finite conjecture and via Tony's construction one gets a weakly connected infinite counterexample. | |
| Dec 16, 2022 at 14:10 | comment | added | Timothy Chow | @TonyHuynh I don't understand what your weakly connected construction is intended to illustrate. Say $G$ has only a single vertex $v$. Then $|N^+(v)| = 0 \le 0 = |N^{++}(v)|$, right? | |
| Dec 16, 2022 at 2:57 | comment | added | Joel David Hamkins | Thomas, in the post you say that $N^{++}(x)$ consists of "everything reachable in exactly two steps," but your more formal definition following this would be better stated as "everything reachable in exactly two steps and not fewer." | |
| Dec 16, 2022 at 2:24 | comment | added | Joel David Hamkins | The infinite degree case is easy, as I explain in my answer, since one can just use the order relation on any endless linear order. @LouisD | |
| Dec 16, 2022 at 2:23 | answer | added | Joel David Hamkins | timeline score: 8 | |
| Dec 15, 2022 at 22:09 | comment | added | Thomas Bloom | No particular reason, just to keep things as close to the finite case as possible. Yes, that would be interesting (assuming you meant for every $x$). | |
| Dec 15, 2022 at 21:56 | comment | added | Louis D | Is there a particular reason you are only interested in the locally finite case? I'm not saying I could provide such an example, but would you be interested in an example where $|N^+(x)|$ is infinite, but $|N^{++}(x)|$ is finite, or say $|N^+(x)|$ is uncountable, but $|N^{++}(x)|$ is countable? | |
| Dec 15, 2022 at 21:01 | history | edited | Thomas Bloom | CC BY-SA 4.0 |
added 288 characters in body
|
| Dec 15, 2022 at 13:02 | comment | added | Tony Huynh | Here's a weakly connected construction. Take a finite $G$. Add $|V(G)|+1$ new vertices $X_1$ and add an arc from each vertex in $X_1$ to each vertex in $G$. Add $|V(G)|+2$ new vertices $X_2$ and add an arc from each vertex in $X_2$ to each vertex in $X_1$. Repeat. | |
| Dec 15, 2022 at 13:01 | comment | added | Thomas Bloom | I was thinking weakly connected, but I don't know anything in the strongly connected case either. | |
| Dec 15, 2022 at 12:51 | comment | added | Joel David Hamkins | By connected, for digraphs, do you mean strongly connected or weakly connected? That is, any two vertices admit a directed path, or is an undirected path sufficient? | |
| Dec 15, 2022 at 12:17 | history | edited | JoshuaZ | CC BY-SA 4.0 |
adding in connected to avoid triviality
|
| Dec 15, 2022 at 11:56 | comment | added | Thomas Bloom | True! I was imagining $G$ to be connected, so perhaps (2) is still possible for connected $G$. (But again maybe there's some way to embed the finite problem within an infinite connected graph.) | |
| Dec 15, 2022 at 11:51 | comment | added | Tony Huynh | The infinite version implies the finite version. Just take infinitely many disjoint copies of a finite $G$. So (2) is unlikely. | |
| Dec 15, 2022 at 11:18 | history | asked | Thomas Bloom | CC BY-SA 4.0 |