Embedding edge-colored graphs in expanders with roll-back
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929685530673152 |
|---|---|
| author | Lund, Ben Xu, Chuandong |
| author_facet | Lund, Ben Xu, Chuandong |
| contents | We introduce a method to embed edge-colored graphs into families of expander graphs, which generalizes a framework developed by Draganić, Krivelevich, and Nenadov (2022). As an application, we show that each family of sufficiently pseudo-random graphs on $n$ vertices contains every edge-colored subdivision of $K_Δ$, provided that the distance between branch vertices in the subdivision is large enough, the average degree of each graph in the family is at least $(1+o(1))Δ$, and the number of vertices in the subdivision is at most $(1-o(1))n$.
This work is motivated in part by the problem of finding structures in distance graphs defined over finite vector spaces. For $d\ge 2$ and an odd prime power $q$, consider the vector space $\mathbb{F}_q^d$ over the finite field $\mathbb{F}_q$, where the distance between two points $(x_1,\ldots,x_d)$ and $(y_1,\ldots,y_d)$ is defined to be $\sum_{i=1}^d (x_i-y_i)^2$. A distance graph is a graph associated with a non-zero distance to each of its edges. We show that large subsets of vector spaces over finite fields contain every distance graph that is a nearly spanning subdivision of a complete graph, provided that the distance between branching vertices in the subdivision is large enough. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_14286 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Embedding edge-colored graphs in expanders with roll-back Lund, Ben Xu, Chuandong Combinatorics We introduce a method to embed edge-colored graphs into families of expander graphs, which generalizes a framework developed by Draganić, Krivelevich, and Nenadov (2022). As an application, we show that each family of sufficiently pseudo-random graphs on $n$ vertices contains every edge-colored subdivision of $K_Δ$, provided that the distance between branch vertices in the subdivision is large enough, the average degree of each graph in the family is at least $(1+o(1))Δ$, and the number of vertices in the subdivision is at most $(1-o(1))n$. This work is motivated in part by the problem of finding structures in distance graphs defined over finite vector spaces. For $d\ge 2$ and an odd prime power $q$, consider the vector space $\mathbb{F}_q^d$ over the finite field $\mathbb{F}_q$, where the distance between two points $(x_1,\ldots,x_d)$ and $(y_1,\ldots,y_d)$ is defined to be $\sum_{i=1}^d (x_i-y_i)^2$. A distance graph is a graph associated with a non-zero distance to each of its edges. We show that large subsets of vector spaces over finite fields contain every distance graph that is a nearly spanning subdivision of a complete graph, provided that the distance between branching vertices in the subdivision is large enough. |
| title | Embedding edge-colored graphs in expanders with roll-back |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2501.14286 |