Search

We use known characterizations of generalized Paley graphs which are cartesian decomposable to explicitly compute the spectra of the corresponding associated irreducible cyclic codes. As applications, we give reduction formulas for the number of rational points in Artin-Schreier curves defined over extension fields and to the computation of Gaussian periods., 20 pages, 2 tables. Added information on Cartesian products of graphs. A general reviwe was made, with small additions improving readability. Some typos corrected. arXiv admin note: text overlap with arXiv:1908.08097

We prove that the degree 4 sum-of-squares (SOS) relaxation of the clique number of the Paley graph on a prime number $p$ of vertices has value at least $\Omega(p^{1/3})$. This is in contrast to the widely believed conjecture that the actual clique number of the Paley graph is $O(\mathrm{polylog}(p))$. Our result may be viewed as a derandomization of that of Deshpande and Montanari (2015), who showed the same lower bound (up to $\mathrm{polylog}(p)$ terms) with high probability for the Erd\H{o}s-R\'{e}nyi random graph on $p$ vertices, whose clique number is with high probability $O(\log(p))$. We also show that our lower bound is optimal for the Feige-Krauthgamer construction of pseudomoments, derandomizing an argument of Kelner. Finally, we present numerical experiments indicating that the value of the degree 4 SOS relaxation of the Paley graph may scale as $O(p^{1/2 - \epsilon})$ for some $\epsilon > 0$, and give a matrix norm calculation indicating that the pseudocalibration proof strategy for SOS lower bounds for random graphs will not immediately transfer to the Paley graph. Taken together, our results suggest that degree 4 SOS may break the "$\sqrt{p}$ barrier" for upper bounds on the clique number of Paley graphs, but prove that it can at best improve the exponent from $1/2$ to $1/3$., Comment: 60 pages, 2 figures, 1 table

It is proved that with finitely many possible exceptions, each cyclotomic scheme over a finite field is determined up to isomorphism by the tensor of 2 2 -dimensional intersection numbers; for infinitely many schemes, this result cannot be improved. As a consequence, the Weisfeiler–Leman dimension of a Paley graph or tournament is at most 3 3 with possible exception of several small graphs.

The automorphism group of the Zetterberg code Z of length 17 (also a quadratic residue code) is a rank three group whose orbits on the coordinate pairs determine two strongly regular graphs equivalent to the Paley graph attached to the prime 17. As a consequence, codewords of a given weight of Z are the characteristic vectors of the blocks of a PBIBD with two associate classes of cyclic type. More generally, this construction of PBIBDs is extended to quadratic residue codes of length $$\equiv 1 \pmod {8},$$ to the adjacency codes of triangular and lattice graphs, and to the adjacency codes of various rank three graphs. A remarkable fact is the existence of 2-designs held by the quadratic residue code of length 41 for code weights 9 and 10.

An incidence of a graph G is a vertex-edge pair ( v , e ) such that the vertex v is incident with the edge e. A proper incidence k-coloring of a graph is a coloring of its incidences involving k colors so that two incidences ( u , e ) and ( w , f ) receive distinct colors if and only if u = w , or e = f , or u w ∈ { e , f } . In this paper, we present some idea of using the incidence coloring to model a kind of multi-frequency assignment problem, in which each transceiver can be simultaneously in both sending and receiving modes, and then establish some theoretical and algorithmic aspects of the incidence coloring. Specifically, we conjecture that if G is the Mycielskian of some graph then it has a proper incidence ( Δ ( G ) + 2 ) -coloring. Actually, our conjecture is motivated by the “ ( Δ + 2 ) conjecture” of Brualdi and Quinn Massey in 1993, which states that every graph G has a proper incidence ( Δ ( G ) + 2 ) -coloring, and was disproved in 1997 by Guiduli, who pointed out that the Paley graphs with large maximum degree are counterexamples (yet they are all known counterexamples to the “ ( Δ + 2 ) conjecture”, and are not Mycielskians of any graph). To support our conjecture, we prove in this paper that if G is the Mycielskian of a graph H with | H | ≥ 3 Δ ( H ) + 2 , then we can construct a proper incidence ( Δ ( G ) + 1 ) -coloring of G in cubic time, and if G is the Mycielskian of an incidence ( Δ ( H ) + 1 ) -colorable graph H with | H | ≤ 2 Δ ( H ) , or the Mycielskian of an incidence ( Δ ( H ) + 2 ) -colorable graph H with | H | ≥ 2 Δ ( H ) + 1 , then G has a proper incidence ( Δ ( G ) + 2 ) -coloring. The minimum positive integer k such that the Mycielskian of a cycle or a path has a proper incidence k-coloring is also determined.

Infinite analogues of the Paley graphs are constructed, based on uncountably many infinite but locally finite fields. Weil's estimate for character sums shows that they are all isomorphic to the random or universal graph of Erd\H os, R\'enyi and Rado. Automorphism groups and connections with model theory are considered., Comment: 10 pages/

A 2-edge-colored graph is a pair $$(G, \sigma )$$(G,σ) where G is a graph, and $$\sigma :E(G)\rightarrow \{\text {'}+\text {'},\text {'}-\text {'}\}$$σ:E(G)→{'+','-'} is a function which marks all edges with signs. A 2-edge-colored coloring of the 2-edge-colored graph $$(G, \sigma )$$(G,σ) is a homomorphism into a 2-edge-colored graph $$(H, \delta )$$(H,δ). The 2-edge-colored chromatic number of the 2-edge-colored graph $$(G, \sigma )$$(G,σ) is the minimum order of H. In this paper we show that for every 2-dimensional grid $$(G, \sigma )$$(G,σ) there exists a homomorphism from $$(G, \sigma )$$(G,σ) into the 2-edge-colored Paley graph $$SP_9$$SP9. Hence, the 2-edge-colored chromatic number of the 2-edge-colored grids is at most 9. This improves the upper bound on this number obtained recently by Bensmail. Additionally, we show that 2-edge-colored chromatic number of the 2-edge-colored grids with 3 columns is at most 8.

This article analyzes new promising topological solutions for the on-chip communication subsystem for network-on-chip (NoCs). A study of Paley graphs as a subclass of circulant graphs is given. The main parameters (diameter, average path length, graph density, number of edges and degrees of vertices) of modifications of Paley graphs are studied using the direct product of Paley graphs with Paley graphs and ring graph. Other types of products of graphs are considered, namely strong, tensor and lexicographic. Due to the more preferable characteristics, the direct product of the graphs was chosen as the most suitable among the considered ones. A comparative analysis of obtained graphs is provided.

Two graphs are co-spectral if their respective adjacency matrices have the same multi-set of eigenvalues. A graph is said to be determined by its spectrum if all graphs that are co-spectral with it are isomorphic to it. We consider these properties in relation to logical definability. We show that any pair of graphs that are elementarily equivalent with respect to the three-variable counting first-order logic $C^3$ are co-spectral, and this is not the case with $C^2$, nor with any number of variables if we exclude counting quantifiers. We also show that the class of graphs that are determined by their spectra is definable in partial fixed-point logic with counting. We relate these properties to other algebraic and combinatorial problems., 17 pages

Shannon OR-capacity $C_{\rm OR}(G)$ of a graph $G$, that is the traditionally more often used Shannon AND-capacity of the complementary graph, is a homomorphism monotone graph parameter satisfying $C_{\rm OR}(F\times G)\le\min\{C_{\rm OR}(F),C_{\rm OR}(G)\}$ for every pair of graphs, where $F\times G$ is the categorical product of graphs $F$ and $G$. Here we initiate the study of the question when could we expect equality in this inequality. Using a strong recent result of Zuiddam, we show that if this "Hedetniemi-type" equality is not satisfied for some pair of graphs then the analogous equality is also not satisfied for this graph pair by some other graph invariant that has a much "nicer" behavior concerning some different graph operations. In particular, unlike Shannon capacity or the chromatic number, this other invariant is both multiplicative under the OR-product and additive under the join operation, while it is also nondecreasing along graph homomorphisms. We also present a natural lower bound on $C_{\rm OR}(F\times G)$ and elaborate on the question of how to find graph pairs for which it is known to be strictly less, than the upper bound $\min\{C_{\rm OR}(F),C_{\rm OR}(G)\}$. We present such graph pairs using the properties of Paley graphs., Comment: 14 pages

Let $$k \ge 2$$ be an integer. Let q be a prime power such that $$q \equiv 1 ({\mathrm{mod}}\,\,k)$$ if q is even, or, $$q \equiv 1 ({\mathrm{mod}}\,\,2k)$$ if q is odd. The generalized Paley graph of order q, $$G_k(q)$$ , is the graph with vertex set $$\mathbb {F}_q$$ where ab is an edge if and only if $${a-b}$$ is a kth power residue. We provide a formula, in terms of finite field hypergeometric functions, for the number of complete subgraphs of order four contained in $$G_k(q)$$ , $$\mathcal {K}_4(G_k(q))$$ , which holds for all k. This generalizes the results of Evans, Pulham and Sheehan on the original ( $$k=2$$ ) Paley graph. We also provide a formula, in terms of Jacobi sums, for the number of complete subgraphs of order three contained in $$G_k(q)$$ , $$\mathcal {K}_3(G_k(q))$$ . In both cases, we give explicit determinations of these formulae for small k. We show that zero values of $$\mathcal {K}_4(G_k(q))$$ (resp. $$\mathcal {K}_3(G_k(q))$$ ) yield lower bounds for the multicolor diagonal Ramsey numbers $$R_k(4)=R(4,4,\ldots ,4)$$ (resp. $$R_k(3)$$ ). We state explicitly these lower bounds for small k and compare to known bounds. We also examine the relationship between both $$\mathcal {K}_4(G_k(q))$$ and $$\mathcal {K}_3(G_k(q))$$ , when q is prime, and Fourier coefficients of modular forms.

The main objective of the study conducted in this article is to introduce a new algorithm of encryption and decryption of a sensitive message after transforming it into a binary message. Our proposed encryption algorithm is based on the study of a particular graph constructed algebraically from the quadratic residues. We have exploited the Paley graph to introduce an abstract way of encryption of such message bit according to the other message bits by the intermidiate study of the neighborhood of a graph vertex. The strong regularity of the Paley graphs and the unknown behavior of the quadratic residues will play a very important role in the cryptanalysis part which allows to say that the brute force attack remains for the moment the only way to obtain the set of possible messages.

The rank three subgroups of a one-dimensional affine group over a finite field were classified in 1978 by Foulser and Kallaher. Although one can use their results for a classification of corresponding rank three graphs, the author did not find such a classification in a literature. The goal of this note is to present such a classification. It turned out that graph classification is much simpler than the group one. More precisely, it is shown that the graphs in the title are either the Paley graphs or one of the graphs constructed by Van Lint and Schrijver or by Peisert. Our approach is based on elementary group theory and does not use the classification of rank three affine groups.

A complete classification is given of 2-distance-transitive circulants, which shows that a 2-distance-transitive circulant is a cycle, a Paley graph of prime order, a regular complete multipartite graph, or a regular complete bipartite graph of order twice an odd integer minus a 1-factor.

Finding and discovering any class of graphs which are determined by their spectra is always an important and interesting problem in the spectral graph theory. The main aim of this study is to characterize two classes of multicone graphs which are determined by both their adjacency and Laplacian spectra. A multicone graph is defined to be the join of a clique and a regular graph. Let Kw denote a complete graph on w vertices, and let m be a positive integer number. In A.Z.Abdian (2016) it has been shown that multicone graphs Kw ▽ P17 and Kw ▽ S are determined by both their adjacency and Laplacian spectra, where P17 and S denote the Paley graph of order 17 and the Schlafli graph, respectively. In this paper, we generalize these results and we prove that multicone graphs Kw ▽mP17 and Kw▽mS are determined by their adjacency spectra as well as their Laplacian spectra.

Let $(M,g)$ be a compact manifold and let $-\Delta \phi_k = \lambda_k \phi_k$ be the sequence of Laplacian eigenfunctions. We present a curious new phenomenon which, so far, we only managed to understand in a few highly specialized cases: the family of functions $f_N:M \rightarrow \mathbb{R}_{\geq 0}$ $$ f_N(x) = \sum_{k \leq N}{ \frac{1}{\sqrt{\lambda_k}} \frac{|\phi_k(x)|}{\|\phi_k\|_{L^{\infty}(M)}}}$$ seems strangely suited for the detection of anomalous points on the manifold. It may be heuristically interpreted as the sum over distances to the nearest nodal line and potentially hints at a new phenomenon in spectral geometry. We give rigorous statements on the unit square $[0,1]^2$ (where minima localize in $\mathbb{Q}^2$) and on Paley graphs (where $f_N$ recovers the geometry of quadratic residues of the underlying finite field $\mathbb{F}_p$). Numerical examples show that the phenomenon seems to arise on fairly generic manifolds., Comment: 11 pages, 7 figures

Finding a reasonably good upper bound for the clique number of Paley graphs is an open problem in additive combinatorics. A recent breakthrough by Hanson and Petridis using Stepanov's method gives an improved upper bound on Paley graphs defined on a prime field $\mathbb{F}_p$, where $p \equiv 1 \pmod 4$. We extend their idea to the finite field $\mathbb{F}_q$, where $q=p^{2s+1}$ for a prime $p\equiv 1 \pmod 4$ and a non-negative integer $s$. We show the clique number of the Paley graph over $\mathbb{F}_{p^{2s+1}}$ is at most $\min \bigg(p^s \bigg\lceil \sqrt{\frac{p}{2}} \bigg\rceil, \sqrt{\frac{q}{2}}+\frac{p^s+1}{4}+\frac{\sqrt{2p}}{32}p^{s-1}\bigg)$., Comment: 13 pages; typos corrected

The critical group of a finite graph is an abelian group defined by the Smith normal form of the Laplacian. We determine the critical groups of the Peisert graphs, a certain family of strongly regular graphs similar to, but different from, the Paley graphs. It is further shown that the adjacency matrices of the two graphs defined over a field of order $$p^2$$ with $$p\equiv 3\pmod 4$$ are similar over the $$\ell $$ -local integers for every prime $$\ell $$ . Consequently, each such pair of graphs provides an example where all the corresponding generalized adjacency matrices are both cospectral and equivalent in the sense of Smith normal form.

The inertia bound gives an upper bound on the independence number of a graph by considering the inertia of matrices corresponding to the graph. The bound is known to be tight for graphs on 10 or fewer vertices as well as for all perfect graphs. The question has been asked as to whether the bound is always tight. We show that the bound is not tight for the Paley graph on 17 vertices as well as for the graph obtained from Paley 17 by deleting a vertex., 12 pages, 7 figures

Codes from neighbourhood designs of generalized Paley graphs $$GP(q,k)$$GP(q,k) of a finite field of order q and their complements are investigated. With certain q and k, we obtain the main parameters of such codes and their duals including bases of minimum-weight vectors for the codes.

We prove that the number of directions contained in a set of the form $A \times B \subset AG(2,p)$, where $p$ is prime, is at least $|A||B| - \min\{|A|,|B|\} + 2$. Here $A$ and $B$ are subsets of $GF(p)$ each with at least two elements and $|A||B, Comment: 8 pages