Timeline for Do balls in expander graphs have small expansion?
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 11, 2023 at 17:04 | comment | added | Louis Esperet | See this paper combinatorics.org/ojs/index.php/eljc/article/view/v29i2p23/pdf for a similar (open) question on sequences of finite graphs rather than infinite graphs (though infinite graphs are briefly mentioned in Section 3). | |
| Dec 3, 2023 at 21:43 | comment | added | Mikael de la Salle | You did not define what you mean by "expansion of a région S". Moishe Kohan interpreted it as the Cheeger constant of the induced subgraph, whereas you apparently had something else in mind. | |
| Dec 3, 2023 at 20:10 | comment | added | user3521569 | @SamNead thanks for acting as an intermediary -- can you however help me understand what was wrong with my definition? I believe I just copied it from the provided link. I am also confused since the aforementioned $H_n$s seem to have nonzero expansion (since they have legs sticking "off" of them and into the remainder of $G$) | |
| Dec 3, 2023 at 10:45 | comment | added | Sam Nead | @MoisheKohan - I believe that you and user3521569 are talking past each other. This is not helped by the fact that user3521569 gave the wrong definition for the expansion of an infinite graph. The correct definition is (I believe) given at the link user3521569 provided. | |
| Dec 3, 2023 at 10:44 | answer | added | Sam Nead | timeline score: 1 | |
| Dec 3, 2023 at 0:38 | comment | added | Moishe Kohan | Each connected graph $G$ of infinite diameter contains a subgraph which is a ray $H$, i.e. is isomorphic to $[0,\infty)$ with nonnegative integers playing role of vertices. Now, take a sequence of subgraphs $H_n$ in $H$ of the form $[0, n]$, $n\in {\mathbb N}$. Cheeger constants of the subgraphs $H_n$ converge to zero. Hence, with your definition, the "expansion constant" of $G$ is zero. It is possible that your expansion constant of a finite graph is not the same as the Cheeger constant. In any case, it is your responsibility to edit your question to clarify your definitions. | |
| Dec 3, 2023 at 0:18 | review | Close votes | |||
| Dec 10, 2023 at 3:05 | |||||
| Dec 2, 2023 at 21:39 | comment | added | user3521569 | why? for an infinite tree you get something nonzero (of course S must be nonempty in the above definition). you can see e.g. here for a readable introduction. | |
| Dec 2, 2023 at 20:54 | comment | added | Moishe Kohan | This definition will give you zero for all connected graphs of bounded valence (assuming that a "region" is a connected subgraph). Where did you see this as the definition? | |
| Dec 2, 2023 at 20:48 | comment | added | user3521569 | that is the actual definition, $\Phi = {\rm inf}_{S \, \mathrm{finite}} \Phi(S)$, where $\Phi(S)$ is the expansion of the region $S$. | |
| Dec 2, 2023 at 20:30 | comment | added | Moishe Kohan | Could you give an actual definition? I know how to define an expansion constant (the Cheeger constant) for a finite graph but then what? | |
| Dec 2, 2023 at 20:25 | comment | added | user3521569 | one normally just defines the expansion as the minimum expansion of any finite region. from this definition one sees that infinite trees are excellent expanders, while finite ones are very poor expanders (hence the intuition above) | |
| Dec 2, 2023 at 20:10 | comment | added | Moishe Kohan | How does one define the notion of expander for a single infinite graph? The definition I know is for a sequence of finite graphs. | |
| Dec 2, 2023 at 18:13 | history | edited | YCor |
edited tags
|
|
| S Dec 2, 2023 at 17:35 | review | First questions | |||
| Dec 2, 2023 at 18:08 | |||||
| S Dec 2, 2023 at 17:35 | history | asked | user3521569 | CC BY-SA 4.0 |