Timeline for Graph $G$ such that removing an edge leaves $G$ "unchanged"
Current License: CC BY-SA 4.0
24 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 28, 2021 at 16:18 | comment | added | Sam Hopkins | This property (the one the OP is asking about) is already mentioned on the wiki page of the Rado graph, by the way: en.wikipedia.org/wiki/… | |
| Jul 28, 2021 at 5:44 | comment | added | Emil Jeřábek | The random graph property implies that for any such $A$ and $B$, there are infintely many vertices each of which is connected to all elements of $A$ and to no elements of $B$. Removing an edge can disturb at most one of them, hence infinitely many remain. | |
| Jul 28, 2021 at 4:34 | vote | accept | Dominic van der Zypen | ||
| Jul 28, 2021 at 1:52 | answer | added | Louis D | timeline score: 1 | |
| Jul 28, 2021 at 1:32 | comment | added | markvs | @AndreasBlass: I am not sure what and to whom you are trying to prove. I know that after removing an edge the graph remains random. | |
| Jul 28, 2021 at 1:27 | comment | added | Andreas Blass | To prove the property holds for $A$ and $B$ after the deletion, just apply the property to the original graph with slightly larger $A$ and $B$. | |
| Jul 28, 2021 at 1:25 | comment | added | markvs | @AndreasBlass: Exactly that property is not clear how to use. A vertex connected to all vertices of $A$ may not be connected to all vertices of $A$ if one of the edges is removed. The thing is that there are at least two such vertices. Also using the fact that the graph is random as mentioned above seems easier. | |
| Jul 28, 2021 at 1:20 | comment | added | Andreas Blass | @MarkSapir The random graph is characterized up to isomorphism, among countable simple graphs, by the property that, given any two disjoint, finite sets of vertices $A$ and $B$, there exists another vertex adjacent to all the members of $A$ and to none of the members of $B$. This property is easily seen to be preserved when an edge is removed. | |
| Jul 27, 2021 at 22:48 | answer | added | M. Winter | timeline score: 14 | |
| Jul 27, 2021 at 22:13 | comment | added | Anthony Quas | Surely the kind of answer the OP is really looking for is the Rado graph | |
| Jul 27, 2021 at 22:11 | answer | added | Mikael de la Salle | timeline score: 7 | |
| Jul 27, 2021 at 21:50 | comment | added | markvs | OK, it is nice. Perhaps, then, it is the answer the OP is looking for? | |
| Jul 27, 2021 at 21:48 | comment | added | Mikael de la Salle | @MarkSapir Yes, it is connected: better, any two points have a common neighbour. | |
| Jul 27, 2021 at 21:42 | comment | added | markvs | Is the random graph connected? I only remember its local properties. | |
| Jul 27, 2021 at 21:38 | comment | added | markvs | @MikaeldelaSalle: I believe you but I do not see why after removing an (any) edge you still get a random graph. | |
| Jul 27, 2021 at 21:35 | answer | added | Tri | timeline score: 2 | |
| Jul 27, 2021 at 21:31 | comment | added | Mikael de la Salle | @MarkSapir If you accept Theorem 1 in the previous reference, this is rather obvious: removing or adding a given edge in a random iid graph is still a random iid graph, and in particular almost surely both graphs are isomorphic to the random graph. (here by random iid graph I mean the graph obtained on a given countable infinite set by putting independantly at random an edge between any two pairs of vertices). | |
| Jul 27, 2021 at 21:21 | comment | added | user44191 | @MarkSapir The graph with no edges isn't such an example, because there is no edge to remove in the first place. | |
| Jul 27, 2021 at 21:21 | review | Close votes | |||
| Aug 3, 2021 at 9:05 | |||||
| Jul 27, 2021 at 21:10 | comment | added | markvs | @MikaeldelaSalle: Why is it so? | |
| Jul 27, 2021 at 21:08 | comment | added | Mikael de la Salle | An(other) example is the random graph arxiv.org/abs/1301.7544 | |
| Jul 27, 2021 at 21:06 | comment | added | markvs | The graph with no edges is an example. | |
| Jul 27, 2021 at 20:58 | answer | added | hbjj | timeline score: 5 | |
| Jul 27, 2021 at 20:45 | history | asked | Dominic van der Zypen | CC BY-SA 4.0 |