Dense triangle-free $(n, d, λ)$-graphs for all orders
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914629975801856 |
|---|---|
| author | Kim, Jaehoon Lee, Hyunwoo |
| author_facet | Kim, Jaehoon Lee, Hyunwoo |
| contents | In 1994, Alon construct a triangle-free $(n,d,λ)$-graph with $d = Ω(n^{2/3})$ and $λ= O(d^{1/2})$ for an exponentially increasing sequence of integers $n$. Using his ingenious construction, we deduce that there exist triangle-free $(n,d,λ)$-graphs with $d = Ω(n^{2/3})$ and $λ= O( (d \log n)^{1/2} )$ for all sufficiently large $n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_02214 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Dense triangle-free $(n, d, λ)$-graphs for all orders Kim, Jaehoon Lee, Hyunwoo Combinatorics In 1994, Alon construct a triangle-free $(n,d,λ)$-graph with $d = Ω(n^{2/3})$ and $λ= O(d^{1/2})$ for an exponentially increasing sequence of integers $n$. Using his ingenious construction, we deduce that there exist triangle-free $(n,d,λ)$-graphs with $d = Ω(n^{2/3})$ and $λ= O( (d \log n)^{1/2} )$ for all sufficiently large $n$. |
| title | Dense triangle-free $(n, d, λ)$-graphs for all orders |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2401.02214 |