Paley-like quasi-random graphs arising from polynomials
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_ | 1866917112702828544 |
|---|---|
| author | Kim, Seoyoung Yip, Chi Hoi Yoo, Semin |
| author_facet | Kim, Seoyoung Yip, Chi Hoi Yoo, Semin |
| contents | Paley graphs and Paley sum graphs are classical examples of quasi-random graphs. In this paper, we provide new constructions of families of quasi-random graphs that behave like Paley graphs but are neither Cayley graphs nor Cayley sum graphs. These graphs give a unified perspective of studying various graphs arising from polynomials over finite fields, such as Paley graphs, Paley sum graphs, and graphs arising from Diophantine tuples and their generalizations. We also obtain lower bounds on the clique and independence numbers of the graphs in these families. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_09319 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Paley-like quasi-random graphs arising from polynomials Kim, Seoyoung Yip, Chi Hoi Yoo, Semin Combinatorics Number Theory 05C48, 05C50, 11B30, 11T06, 05D10 Paley graphs and Paley sum graphs are classical examples of quasi-random graphs. In this paper, we provide new constructions of families of quasi-random graphs that behave like Paley graphs but are neither Cayley graphs nor Cayley sum graphs. These graphs give a unified perspective of studying various graphs arising from polynomials over finite fields, such as Paley graphs, Paley sum graphs, and graphs arising from Diophantine tuples and their generalizations. We also obtain lower bounds on the clique and independence numbers of the graphs in these families. |
| title | Paley-like quasi-random graphs arising from polynomials |
| topic | Combinatorics Number Theory 05C48, 05C50, 11B30, 11T06, 05D10 |
| url | https://arxiv.org/abs/2405.09319 |