Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2401.07223 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913247497551872 |
|---|---|
| author | Korsky, Samuel Saffat, Tahsin Aiylam, Dhroova |
| author_facet | Korsky, Samuel Saffat, Tahsin Aiylam, Dhroova |
| contents | In this work we attempt to count the number of integer-valued $h$-Lipschitz functions (functions that change by at most $h$ along edges) on two classes of sparse graphs; grid graphs $L_{m,n}$, and sparse random graphs $G(n,d/n)$. We find that for all $n$-vertex graphs $G$ with $k$ connected components, the number of such functions grows as $(ch)^{n - k}$ for some $1 \le c \le 2$. In particular, letting $α\approx 1.16234$ be the largest solution to $\tan{(1/x)} = x$, we prove that as $n \to \infty$ $$ c = α\sqrt{2} \approx 1.6438\ \ \text{when}\ \ G = L_{2,n} $$ and $$ 1.351 \approx α^2 \le c \le \arctan{(3/4)}^{-1} \approx 1.554\ \ \text{when}\ \ G = L_{n,n} $$ and $$ 1 + \frac{1}{2d} + O\left(\frac{1}{d^2}\right) \le c \le 1 + \frac{4\ln^2{d}}{d} + O\left(\frac{1}{d}\right)\ \ \text{(w.h.p.) when}\ \ G = G(n, d/n) $$ |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_07223 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Lipschitz Functions on Sparse Graphs Korsky, Samuel Saffat, Tahsin Aiylam, Dhroova Combinatorics In this work we attempt to count the number of integer-valued $h$-Lipschitz functions (functions that change by at most $h$ along edges) on two classes of sparse graphs; grid graphs $L_{m,n}$, and sparse random graphs $G(n,d/n)$. We find that for all $n$-vertex graphs $G$ with $k$ connected components, the number of such functions grows as $(ch)^{n - k}$ for some $1 \le c \le 2$. In particular, letting $α\approx 1.16234$ be the largest solution to $\tan{(1/x)} = x$, we prove that as $n \to \infty$ $$ c = α\sqrt{2} \approx 1.6438\ \ \text{when}\ \ G = L_{2,n} $$ and $$ 1.351 \approx α^2 \le c \le \arctan{(3/4)}^{-1} \approx 1.554\ \ \text{when}\ \ G = L_{n,n} $$ and $$ 1 + \frac{1}{2d} + O\left(\frac{1}{d^2}\right) \le c \le 1 + \frac{4\ln^2{d}}{d} + O\left(\frac{1}{d}\right)\ \ \text{(w.h.p.) when}\ \ G = G(n, d/n) $$ |
| title | Lipschitz Functions on Sparse Graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2401.07223 |