On the directions determined by Cartesian products and the clique number of generalized Paley graphs

MaRDI QIDQ4991645zbMATH OpenFDO

Authors Chi Hoi Yip

Publication date 3 June 2021

Full work available at URL https://arxiv.org/abs/2010.01784, http://math.colgate.edu/~integers/v51/v51.pdf

zbMATH Keywords

affine Galois planecubic Paley graph

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Structural characterization of families of graphs (05C75) Graph operations (line graphs, products, etc.) (05C76) Arithmetic combinatorics; higher degree uniformity (11B30)

Abstract: It is known that the number of directions formed by a Cartesian product $AimesBsubsetAG(2,p)$ is at least $|A||B|-min|A|,|B|+2$, provided $p$ is prime and $|A||B|<p$. This implies the best known upper bound on the clique number of the Paley graph over $mathbb{F}_p$. In this paper, we extend this result to $AG(2,q)$, where $q$ is a prime power. We also give improved upper bounds on the clique number of generalized Paley graphs over $mathbb{F}_q$. In particular, for a cubic Paley graph, we improve the trivial upper bound $sqrtq$ to $0.769sqrtq+1$. In general, as an application of our key result on the number of directions, for any positive function $h$ such that $h(x)=o(x)$ as $xoinfty$, we improve the trivial upper bound $sqrtq$ to $sqrtq-h(p)$ for almost all non-squares $q$.

Recommendations

• On the directions determined by a Cartesian product in an affine Galois plane
• On the clique number of Paley graphs of prime power order
• CLIQUE NUMBERS OF PALEY GRAPHS
• Maximal cliques in the Paley graph of square order
• Refined estimates concerning sumsets contained in the roots of unity

Cites work

• Around Rédei's theorem
• CLIQUE NUMBERS OF PALEY GRAPHS
• Directions in AG(2,p^2).
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• scientific article; zbMATH DE number 3501652 (Why is no real title available?)
• scientific article; zbMATH DE number 3440485 (Why is no real title available?)
• scientific article; zbMATH DE number 2121181 (Why is no real title available?)
• New results on sum-product type growth over fields
• On generalised Paley graphs and their automorphism groups
• On the adjacency properties of generalized Paley graphs
• On the number of directions determined by a set of points in an affine Galois plane
• Open problems in additive combinatorics
• Refined estimates concerning sumsets contained in the roots of unity
• Squares and difference sets in finite fields
• THE CLIQUE NUMBERS AND CHROMATIC NUMBERS OF CERTAIN PALEY GRAPHS
• Uniform distribution of prime powers and sets of recurrence and van der Corput sets in \(\mathbb{Z}^k\)

Cited in

(15)

• On the directions determined by a Cartesian product in an affine Galois plane
• Bounds for regular induced subgraphs of strongly regular graphs
• Gauss sums and the maximum cliques in generalized Paley graphs of square order
• On maximal cliques of Cayley graphs over fields
• Van Lint-MacWilliams' conjecture and maximum cliques in Cayley graphs over finite fields
• On the clique number of Paley graphs of prime power order
• On eigenfunctions and maximal cliques of generalised Paley graphs of square order
• Paley-like graphs over finite fields from vector spaces
• Refined estimates concerning sumsets contained in the roots of unity
• Asymptotics for the number of directions determined by [n]×[n]$[n] \times [n]$ in Fp2${\mathbb F}_p^2$
• Generalized Paley graphs equienergetic with their complements
• Additive decompositions of large multiplicative subgroups in finite fields
• Restricted sumsets in multiplicative subgroups
• Exact values and improved bounds on the clique number of cyclotomic graphs
• Number of cliques of Paley-type graphs over finite commutative local rings

This page was built for publication: On the directions determined by Cartesian products and the clique number of generalized Paley graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4991645)