Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2507.14473 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913949654450176 |
|---|---|
| author | Sheffield, Nathan S. Xi, Zoe |
| author_facet | Sheffield, Nathan S. Xi, Zoe |
| contents | In a recent paper, Caro, Lauri, Mifsud, Yuster, and Zarb ask which parameters $r$ and $c$ admit the existence of an $r$-regular graph such that the neighborhood of each vertex induces exactly $c$ edges. They show that every $r$ with $c$ satisfying $0\leq c\leq {r\choose 2}-5r^{3/2}$ is achievable, but no $r$ with $c$ satisfying ${r\choose 2}-\lfloor\frac{r}{3}\rfloor\leq c\leq {r\choose 2}-1$ is. We strengthen the bound in their nonexistence result from ${r\choose 2}-\lfloor\frac{r}{3}\rfloor$ to ${r\choose 2}-\lfloor\frac{r-2}{2}\rfloor$. Additionally, when the graph is the Cayley graph of an abelian group, we obtain a much more fine-grained characterization of the achievable values of $c$ between $\binom{r}{2} - 5r^{3/2}$ and $\binom{r}{2} - \lfloor\frac{r-2}{2}\rfloor$, which we conjecture to be the correct answer for general graphs as well. That result relies on a lemma about approximate subgroups in the "99% regime," quantifying the extent to which nearly-additively-closed subsets of an abelian group must be close to actual subgroups. Finally, we consider a generalization to graphs with multiple types of edges and partially resolve several open questions of Caro et al. about $\textit{flip}$ colorings of graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_14473 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Graphs With the Same Edge Count in Each Neighborhood Sheffield, Nathan S. Xi, Zoe Combinatorics Discrete Mathematics In a recent paper, Caro, Lauri, Mifsud, Yuster, and Zarb ask which parameters $r$ and $c$ admit the existence of an $r$-regular graph such that the neighborhood of each vertex induces exactly $c$ edges. They show that every $r$ with $c$ satisfying $0\leq c\leq {r\choose 2}-5r^{3/2}$ is achievable, but no $r$ with $c$ satisfying ${r\choose 2}-\lfloor\frac{r}{3}\rfloor\leq c\leq {r\choose 2}-1$ is. We strengthen the bound in their nonexistence result from ${r\choose 2}-\lfloor\frac{r}{3}\rfloor$ to ${r\choose 2}-\lfloor\frac{r-2}{2}\rfloor$. Additionally, when the graph is the Cayley graph of an abelian group, we obtain a much more fine-grained characterization of the achievable values of $c$ between $\binom{r}{2} - 5r^{3/2}$ and $\binom{r}{2} - \lfloor\frac{r-2}{2}\rfloor$, which we conjecture to be the correct answer for general graphs as well. That result relies on a lemma about approximate subgroups in the "99% regime," quantifying the extent to which nearly-additively-closed subsets of an abelian group must be close to actual subgroups. Finally, we consider a generalization to graphs with multiple types of edges and partially resolve several open questions of Caro et al. about $\textit{flip}$ colorings of graphs. |
| title | Graphs With the Same Edge Count in Each Neighborhood |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2507.14473 |