Search

The paper gives a new proof of the old result of McConnell (Acta Arithm 8:127–151, 1963 [9]) stating that the automorphism group of a cyclotomic scheme over the finite field \(\mathbb F_q\) is a subgroup of \(A\varGamma L_1(q)\).

In this paper, we prove that the Paley graph conjecture implies that the Paley matrix has restricted isometry property (RIP) beating the square-root bottleneck for the sparsity level. Moreover, we show that the RIP of the Paley matrix implies an improved bound on the size of transitive subtournaments in the Paley tournament., Comment: 12 pages. arXiv admin note: text overlap with arXiv:2010.11179

This paper discusses some aspects of the history of the Paley graphs and their automorphism groups.

The Lov\'{a}sz theta number is a semidefinite programming bound on the clique number of (the complement of) a given graph. Given a vertex-transitive graph, every vertex belongs to a maximal clique, and so one can instead apply this semidefinite programming bound to the local graph. In the case of the Paley graph, the local graph is circulant, and so this bound reduces to a linear programming bound, allowing for fast computations. Impressively, the value of this program with Schrijver's nonnegativity constraint rivals the state-of-the-art closed-form bound recently proved by Hanson and Petridis. We conjecture that this linear programming bound improves on the Hanson-Petridis bound infinitely often, and we derive the dual program to facilitate proving this conjecture., Comment: Wavelets and Sparsity XVIII

We prove that the clique number of the Paley graph is at most $\sqrt{p/2} + 1$, and that any supposed additive decompositions of the set of quadratic residues can only come from co-Sidon sets., 7 pages. The second version already included a corollary to Theorem 1.2 due to George Shakan that confirms Sarkozy's conjecture for almost all primes

We show that the Waring number over a finite field F q , denoted as g ( k , q ) , when exists coincides with the diameter of the generalized Paley graph Γ ( k , q ) = C a y ( F q , R k ) with R k = { x k : x ∈ F q ∗ } . We find infinite new families of exact values of g ( k , q ) from a characterization of graphs Γ ( k , q ) which are also Hamming graphs proved by Lim and Praeger in 2009. Then, we show that every positive integer is the Waring number for some pair ( k , q ) with q not a prime. Finally, we find a lower bound for g ( k , p ) with p prime by using that Γ ( k , p ) is a circulant graph in this case.

Edge even graceful labeling is a novel graceful labelling, introduced in 2017 by Elsonbaty and Daoud. A graph G with p vertices and q edges is called an edge even graceful if there is a bijection f: E(G) → {2, 4,. . ., 2q} such that, when each vertex is assigned the sum of the labels of all edges incident to it mod 2k, where k = max (p, q), the resulting vertex labels are distinct. A labeling of G is called edge odd graceful labeling, if there exists a bijection f from the set of edges E(G) to the set {1,3,5,…,2q-1} such that the induced the map f* from the set of vertices V(G) to {0,1,2,.,.,2q-1} given by f*(u) = Σ uv∈E(G) f(uv) (mod 2q) is an injection. A graph which admits edge even (odd) graceful labeling is called an edge even (odd) graceful graph. Paley graphs are dense undirected graphs raised from the vertices as elements of an appropriate finite field by joining pairs of vertices that differ by a quadratic residue. In this paper, we study the construction of edge even (odd) graceful labeling for Paley graphs and prove that Paley graphs of prime order are edge even (odd) graceful.

We show that, every oriented graph with maximum average degree less than 28/9 admits a homomorphism into the Paley tournament with 11 vertices.

In this paper, we investigate the isoperimetric constant (or expansion constant) of a Paley graph, and the Kazhdan constant of the group and generating set associated with a Paley graph. ¶ We give two new upper bounds for the isoperimetric constant [math] for the Paley graph [math] . These bounds improve previously known eigenvalue bounds on [math] . Along with a known eigenvalue lower bound for [math] , they provide a narrow strip in which [math] must live. More precisely, we show that [math] , which implies that [math] . ¶ In addition, we show that the Kazhdan constant associated with the integers modulo [math] and the generating set for the Paley graph [math] approaches [math] as [math] tends to infinity, which is the best possible limit that the Kazhdan constant can be.

The main purpose of this paper is to investigate relationships between three graph symmetry properties: s -arc transitivity, s -geodesic transitivity, and s -distance transitivity. A well-known result of Weiss tells us that if a graph of valency at least 3 is s -arc transitive then s ? 7 . We show that for each value of s ? 3 , there are infinitely many s -arc transitive graphs that are t -geodesic transitive for arbitrarily large values of t . For 4 ? s ? 7 , the geodesic transitive graphs that are s -arc transitive can be explicitly described, and all but two of these graphs are related to classical generalized polygons. Finally, we show that the Paley graphs and the Peisert graphs, which are known to be distance transitive, are almost never 2-geodesic transitive, with just three small exceptions.

Regular graph is the type of graph whose degree of all vertices are same, and this property makes it very useful in design of key distribution algorithm. Keys in wireless sensor node need to be evenly distributed for efficient storage and good connectivity. In the past various methods have been proposed to overcome the problem of key predistribution for wireless sensor network. Among these, the balanced incomplete block design technique from the theory of combinatorics provides a meaningful enhancement in key predistribution. Also various improvements have been done over this technique for especial arrangement of sensor network. Here, we use Paley graph a class of regular graph to model our key distribution in a location-independent sensor environment, where locations of sensor nodes are assumed to be unknown prior to deployment or key distribution. Experiments were performed and presented here.

Let $X$ be a graph with adjacency matrix $A$. The \textsl{continuous quantum walk} on $X$ is determined by the unitary matrices $U(t)=\exp(itA)$. If $X$ is the complete graph $K_n$ and $a\in V(X)$, then \[1-|U(t)_{a,a}|\le2/n. \] In a sense, this means that a quantum walk on a complete graph stay home with high probability. In this paper we consider quantum walks on cones over an $\ell$-regular graph on $n$ vertices. We prove that if $\ell^2/n\to\infty$ as $n$ increases, than a quantum walk that starts on the apex of the cone will remain on it with probability tending to $1$ as $n$ increases. On the other hand, if $\ell\le2$ we prove that there is a time $t$ such that local uniform mixing occurs, i.e., all vertices are equally likely. We investigate when a quantum walk on strongly regular graph has a high probability of "staying at home", producing large families of examples with the stay-at-home property where the valency is small compared to the number of vertices., 21 pages

Duan and Winter studied the one-shot zero-error classical capacity of a quantum channel assisted by quantum non-signalling correlations, and formulated this problem as a semidefinite program depending only on the Kraus operator space of the channel. For the class of classical-quantum channels, they showed that the asymptotic zero-error classical capacity assisted by quantum non-signalling correlations, minimized over all classical-quantum channels with a confusability graph $G$, is exactly $\log \vartheta(G)$, where $\vartheta(G)$ is the celebrated Lov\'{a}sz theta function. In this paper, we show that the one-shot capacity for a classical-quantum channel, induced from a circulant graph $G$ defined by equal-sized cyclotomic cosets, is $\log \lfloor \vartheta(G) \rfloor$, which further implies that its asymptotic capacity is $\log \vartheta(G)$. This type of graphs include the cycle graphs of odd length, the Paley graphs of prime vertices, and the cubit residue graphs of prime vertices. Examples of other graphs are also discussed. This endows the Lov\'{a}sz $\theta$ function with a more straightforward operational meaning., Comment: 13 pages, 6 figures

A Diophantine m-tuple with property D ( n ) , where n is a non-zero integer, is a set of m positive integers { a 1 , . . . , a m } such that a i a j + n is a perfect square for all 1 ⩽ i j ⩽ m . It is known that M n = sup ⁡ { | S | : S is a D ( n ) m -tuple } exists and is O ( log ⁡ | n | ) . In this paper, we show that the Paley graph conjecture implies that the upper bound can be improved to ≪ ( log ⁡ | n | ) ϵ , for any ϵ > 0 .

Let q ≡ 1 ( mod 4 ) be a prime power and P q the Paley graph of order q . It is shown that if P q contains no copy of G , where δ ( G ) ≥ 1 , then r 2 ( K 1 + G ) ≥ 2 q + 1 . In particular, if 4 n + 1 is a prime power, then r 2 ( K 3 + K ¯ n ) ≥ 8 n + 3 . Furthermore, the Paley graph P q for q = 1 ( mod 6 ) is generalized to H 0 ( q ) , H 1 ( q ) and H 2 ( q ) , which are ( q − 1 ) / 3 -regular, isomorphic to each other and form an edge-coloring of K q . It is shown that if H 0 ( q ) contains no copy of G with δ ( G ) ≥ 1 , then r 3 ( K 1 + G ) ≥ 3 q + 1 . Also, each pair of adjacent vertices in H 0 ( q ) has the same number of common neighbors. We shall compute this number for many H 0 ( p ) , where p is a prime for convenience of the algorithm. Each of computing data gives lower bounds for some three-color Ramsey numbers.

We examine the binary code from the row span of an adjacency matrix of the Paley graph of order q 2 , where q is a prime power such that q 2 ≡ 1 ( mod 8 ) . We show that the code and its dual are respectively [ q 2 , q 2 − 1 2 , q + 1 ] 2 and [ q 2 , q 2 + 1 2 , q ] 2 codes. We obtain spanning sets of minimum-weight vectors for these codes, and in the case of q a prime we show that the code can be used for partial permutation decoding using a certain information set.

For each prime power $n \equiv 1$ (mod 4), a pair of connected graphs on 4n-4 vertices, with reconstruction number at least 2n-1, is constructed.

In this paper, we present constructions of abelian Paley type sets by using multiplicative characters of finite fields and Arasu---Dillon---Player difference sets. The constructions produce many new Paley type sets and their configurations that were previous unknown in our classification of Paley type sets in finite fields of small orders.

The paper is concerned with Haar and Rademacher series in symmetric spaces, and also with the properties of spaces defined by the Paley function. In particular, the symmetric hull of the space of functions with uniformly bounded Paley function is found. Bibliography: 27 titles.

The generalized Paley graphs \(\text{ GP }(q,k)\) are a generalization of the well-known Paley graphs. Codes derived from the row span of adjacency and incidence matrices from Paley graphs have been studied in Ghinellie and Key (Adv Math Commun 5(1):93–108, 2011) and Key and Limbupasiriporn (Congr Numer 170:143–155, 2004). We examine the binary codes associated with the incidence designs of the generalized Paley graphs obtaining the code parameters \([\frac{qs}{2}, q-1, s]\) or \([qs, q-1,2s]\) where \(s=\frac{q-1}{k}\). By finding explicit PD-sets we show that these codes can be used for permutation decoding.

A graph is Cartesian decomposable if it is isomorphic to a Cartesian product of (more than one) strictly smaller graphs, each of which has more than one vertex and admits no such decomposition. These smaller graphs are called the Cartesian-prime factors of the Cartesian decomposition, and were shown, by Sabidussi and Vizing independently, to be uniquely determined up to isomorphism. We characterise by their parameters those generalised Paley graphs which are Cartesian decomposable, and we prove that for such graphs, the Cartesian-prime factors are themselves smaller generalised Paley graphs. This generalises a result of Lim and the second author which deals with the case where all the Cartesian-prime factors are complete graphs. These results contribute to the determination, by parameters, of generalised Paley graphs with automorphism groups larger than the 1-dimensional affine subgroups used to define them., 9 pages, submitted for publication

We propose a new model of weak random sources which we call sumset sources. A sumset source X is the sum of C independent sources, with each source on n bits source having min-entropy k. We show that extractors for this class of sources can be used to give extractors for most classes of weak sources that have been studied previously, including independent sources, affine sources (which generalizes oblivious bit-fixing sources), small space sources, total entropy independent sources, and interleaved sources. This provides a unified approach for randomness extraction. A known extractor for this class of sources, prior to our work, is the Paley graph function introduced by Chor and Goldreich, which works for the sum of 2 independent sources, where one has min-entropy at least 0.51n and the other has logarithmic min-entropy. To the best of our knowledge, the only other known construction is from the work of Kamp, Rao, Vadhan and Zuckerman, which can extract from the sum of exponentially many independent sources. Our main result is an explicit extractor for the sum of C independent sources for some large enough constant C, where each source has polylogarithmic min-entropy. We then use this extractor to obtain improved extractors for other well studied classes of sources including small-space sources, affine sources and interleaved sources.

In this paper, we present a construction of abelian Paley type group schemes which are inequivalent to Paley group schemes. We then determine the equivalence amongst their configurations, the Hadamard designs or the Paley type strongly regular graphs obtained from these group schemes, up to isomorphism. We also give constructions of several families of non-abelian Paley type group schemes using strong multiplier groups of the abelian Paley type group schemes, and present the first family of p-groups of non-square order and of non-prime exponent that contain Paley type group schemes for all odd primes p.

By an edge-coloring induced by generalization of Paley graph and computer searching, we show that that Ramsey numbers of Kn − e in three colors for n = 6, 7, 8, 9 are at least 472, 1102, 3208, 5962, respectively.

In this paper we give some necessary and sufficient conditions for Dembowski–Ostrom polynomials to be planar. These conditions give a simple explanation of the Coulter–Matthews and Ding–Yin commutative semifields and enable us to obtain permutation polynomials from some of the Zha–Kyureghyan–Wang commutative semifields. We then give a generalization of Feng’s construction of Paley type group schemes in extra-special p-groups of exponent p and construct a family of Paley type group schemes in what we call the flag groups of finite fields. We also determine the strong multiplier groups of these group schemes. In the last section of this paper, we give a straightforward generalization of the twin prime power construction of difference sets to a construction of Hadamard designs from twin Paley type association schemes.

We examine the $p$-ary codes from incidence matrices of Paley graphs $P(q)$ where $q\equiv 1$(mod $4$) is a prime power, and show that the codes are $[\frac{q(q-1)}{4},q-1,\frac{q-1}{2}]$2 or $[\frac{q(q-1)}{4},q,\frac{q-1}{2}]$p for $p$ odd. By finding PD-sets we show that for $q > 9$ the $p$-ary codes, for any $p$, can be used for permutation decoding for full error-correction. The binary code from the line graph of $P(q)$ is shown to be the same as the binary code from an incidence matrix for $P(q)$.

We establish the boundedness in L q spaces, 1 < q 2, of a \vertical" Littlewood{Paley{Stein operator associated with a reversible random walk on a graph. This result extends to certain non-reversible random walks, including centered random walks on any nitely generated discrete group.

Let K"n-e be a graph obtained from a complete graph of order n by dropping an edge, and let G"p be a Paley graph of order p. It is shown that if G"p contains no K"n-e, then r(K"n"+"1-e)>=2p+1. For example, G"1"4"9"3 contains no K"1"3-e, so r(K"1"4-e)>=2987, improving the old bound 2557. It is also shown that r(K"[email protected]?+G)@?4r(G,K"[email protected]?+G)-2, implying that r(K"n-e)@?4r(K"n"-"2,K"n-e)-2.

Let $\mathbb{Z}_n$ be the ring of residue classes modulo $n$, and let $\mathbb{Z}_n^{\ast}$ be the group of its units. 90 years ago, Brauer obtained a formula for the number of representations of $c\in \mathbb{Z}_n$ as the sum of $k$ units. Recently, Yang and Tang in [Q. Yang, M. Tang, On the addition of squares of units and nonunits modulo $n$, J. Number Theory., 155 (2015) 1--12] gave a formula for the number of solutions of the equation $x_1^2+x_2^2=c$ with $x_{1},x_{2}\in \mathbb{Z}_n^{\ast}$. In this paper, we generalize this result. We find an explicit formula for the number of solutions of the equation $x^2_{1}+\cdots+x^2_{k}=c$ with $x_{1},\ldots,x_{k}\in \mathbb{Z}_n^{\ast}$., Comment: To appear in Journal of Number Theory

For a prime $p$ we define the Paley graph to be the graph with the set of vertices $\mathbb{Z}/p\mathbb{Z}$, and with edges connecting vertices whose sum is a quadratic residue. Paley graphs are notoriously difficult to study, particularly finding bounds for their clique numbers. For this reason, it is desirable to have a random model. A well known result of Graham and Ringrose shows that the clique number of the Paley graph is $\Omega(\log p\log\log\log p)$ (even $\Omega(\log p\log\log p)$, under the generalized Riemann hypothesis) for infinitely many primes $p$ -- a behaviour not detected by the random Cayley graph which is hence deficient as a random model for for the Paley graph. In this paper we give a new probabilistic model which incorporates some multiplicative structure and as a result captures the Graham-Ringrose phenomenon. We prove that if we sample such a random graph independently for every prime, then almost surely (i) for infinitely many primes $p$ the clique number is $\Omega(\log p\log\log p)$, whilst (ii) for almost all primes the clique number is $(2+o(1))\log p$., Comment: 13 pages

We determine new upper bounds for the clique numbers of strongly regular graphs in terms of their parameters. These bounds improve on the Delsarte bound for infinitely many feasible parameter tuples for strongly regular graphs, including infinitely many parameter tuples that correspond to Paley graphs., Comment: 13 pages

In the past decade, there has been a stream of work in designing approximation schemes for dense instances of NP-Hard problems. These include the work of Arora, Karger and Karpinski from 1995 and that of Frieze and Kannan from 1996. We address the problem of proving hardness results for (fully) dense problems, which has been neglected despite the fruitful effort put in upper bounds. In this work, we prove hardness results of dense instances of a broad family of CSP problems, as well as a broad family of ranking problems which we refer to as CSP-Rank. Our techniques involve a construction of a pseudorandom hypergraph coloring, which generalizes the well-known Paley graph, recently used by Alon to prove hardness of feedback arc-set in tournaments.

Let (K, + ,*) be an odd order presemifield with commutative multiplication. We show that the set of nonzero squares of (K, *) is a skew Hadamard difference set or a Paley type partial difference set in (K, +) according as q is congruent to 3 modulo 4 or q is congruent to 1 modulo 4. Applying this result to the Coulter---Matthews presemifield and the Ding---Yuan variation of it, we recover a recent construction of skew Hadamard difference sets by Ding and Yuan [7]. On the other hand, applying this result to the known presemifields with commutative multiplication and having order q congruent to 1 modulo 4, we construct several families of pseudo-Paley graphs. We compute the p-ranks of these pseudo-Paley graphs when q = 34, 36, 38, 310, 54, and 74. The p-rank results indicate that these graphs seem to be new. Along the way, we also disprove a conjecture of Rene Peeters [17, p. 47] which says that the Paley graphs of nonprime order are uniquely determined by their parameters and the minimality of their relevant p-ranks.

In this paper, we propose a novel model to study the efficiency of detecting latent connection relationships, represented by a given set of graphs, among N users. A subset of active nodes transmit following a common codebook over a multiple access Boolean channel. To maximize the error exponent of the structure detection, we formulate an optimization problem whose objective is to max-minimize the pairwise Chernoff information, and the constraint is a probability simplex due to the users' multiple dependency relationships, which are further shown to have close relationship to the internal connectivity of graphs. Case studies are provided to show certain inherent properties of the optimal solution. In addition, we present a particular case with two equally weighted complementary Paley graphs of prime square order, whose optimal solution for the codebook is proved and the resulting exponent is shown to be O(1/N). The case study demonstrates how the fundamental graph discrepancy property affects the solution to the problem.

The performance guarantees in recovery of a sparse vector in a compressed sensing scenario, besides the reconstruction technique, depends on the choice of the sensing matrix. The so-called restricted isometry property (RIP) is one of the well-used tools to determine and compare the performance of various sensing matrices. It is a standard result that random (Gaussian) matrices satisfy RIP with high probability. However, the design of deterministic matrices that satisfy RIP has been a great challenge for many years now. The common design technique is through the coherence value (maximum modulus correlation between the columns). In this paper, based on the Paley graphs, we introduce deterministic matrices of size q+1/2 × q with q a prime power, such that the corresponding Gram matrix is real-valued. We show that the coherence of these matrices are less than twice the Welch bound, which is a lower bound valid for general matrices. It should be mentioned that the introduced matrix differs from the equiangular tight frame (ETF) of size q-1/2 × q arising from the Paley difference set.

The local minimum degree of a graph is the minimum degree that can be reached by means of local complementation. For any n, there exist graphs of order n which have a local minimum degree at least 0.189n, or at least 0.110n when restricted to bipartite graphs. Regarding the upper bound, we show that the local minimum degree is at most \(\frac{3}{8}n+o(n)\) for general graphs and \(\frac{n}{4}+o(n)\) for bipartite graphs, improving the known \(\frac{n}{2}\) upper bound. We also prove that the local minimum degree is smaller than half of the vertex cover number (up to a logarithmic term). The local minimum degree problem is NP-Complete and hard to approximate. We show that this problem, even when restricted to bipartite graphs, is in W[2] and FPT-equivalent to the EvenSet problem, whose W[1]-hardness is a long standing open question. Finally, we show that the local minimum degree is computed by a \(\mathcal O^*(1.938^n)\)-algorithm, and a \(\mathcal O^*(1.466^n)\)-algorithm for the bipartite graphs.

Let q=pe ? 1(mod 4) be a prime power, and let ?(q) be the Paley graph over the finite field $${\mathbb F}_q$$ . Denote by ?(q) the subgraph of ?(q) induced on the set of non-zero squares of $${\mathbb F}_q$$ . In this paper the full automorphism group of ?(q) is determined affirming the conjecture of Brouwer [Des. Codes Cryptograph. 21, 69--76 (2000)]. The proof combines spectral and Schur ring techniques.

A set of permutations of length v is t-suitable if every element precedes every subset of t − 1 others in at least one permutation. The maximum length of a t-suitable set of N permutations depends heavily on the relation between t and N. Two classical results, due to Dushnik and Spencer, are revisited. Dushnik’s result determines the maximum length when \(t > \sqrt{2N}\). On the other hand, when t is fixed Spencer’s uses a strong connection with binary covering arrays of strength t − 1 to obtain a lower bound on the length that is doubly exponential in t. We explore intermediate values for t, by first considering directed packings and related Golomb rulers, and then by examining binary covering arrays whose number of rows is approximately equal to their number of columns. These in turn are constructed from Hadamard and Paley matrices, for which we present some computational data and questions.

A well-known conjecture in analytic number theory states that for every pair of sets $X,Y\subset\mathbb{Z}/p\mathbb{Z}$, each of size at least $\log ^C p$ (for some constant $C$) we have that the number of pairs $(x,y)\in X\times Y$ such that $x+y$ is a quadratic residue modulo $p$ differs from $\frac12|X||Y|$ by $o\left(|X||Y|\right)$. We address the probabilistic analogue of this question, that is for every fixed $\delta>0$, given a finite group $G$ and $A\subset G$ a random subset of density $\frac12$, we prove that with high probability for all subsets $|X|,|Y|\geq \log ^{2+\delta} |G|$, the number of pairs $(x,y)\in X\times Y$ such that $xy\in A$ differs from $\frac12|X||Y|$ by $o\left(|X||Y|\right)$., Comment: 12 pages. To appear in the European Journal of Combinatorics. This is the version accepted for publication, incorporating the referees' suggestions

The Kuramoto model (KM) of coupled phase oscillators on complete, Paley, and Erdos-Renyi (ER) graphs is analyzed in this work. As quasirandom graphs, the complete, Paley, and ER graphs share many structural properties. For instance, they exhibit the same asymptotics of the edge distributions, homomorphism densities, graph spectra, and have constant graph limits. Nonetheless, we show that the asymptotic behavior of solutions in the KM on these graphs can be qualitatively different. Specifically, we identify twisted states, steady state solutions of the KM on complete and Paley graphs, which are stable for one family of graphs but not for the other. On the other hand, we show that the solutions of the IVPs for the KM on complete and random graphs remain close on finite time intervals, provided they start from close initial conditions and the graphs are sufficiently large. Therefore, the results of this paper elucidate the relation between the network structure and dynamics in coupled nonlinear dynamical systems. Furthermore, we present new results on synchronization and stability of twisted states for the KM on Cayley and random graphs., Journal of Nonlinear Science, 2015

In this paper we consider cocyclic weighing matrices. Cocyclic development of a weighing matrix is shown to be related to regular group actions on the points of the associated group divisible design. We show that a cocyclic weighing matrix is equivalent to a relative difference set with central forbidden subgroup of order two. We then set out an agenda for studying a known cocyclic weighing matrix and carry it out for the Paley conference matrix and for the type I Paley Hadamard matrix. Using a connection with certain near fields, we determine all the regular group actions on the group divisible design associated to such a Paley matrix. It happens that all the regular actions of the Paley type I Hadamard matrix have already been described in the literature, however, new regular actions are identified for the Paley conference matrix. This allows us to determine all the extension groups and indexing groups for the cocycles of the aforementioned Paley matrices, and gives new families of normal and non-normal relative difference sets with forbidden subgroup of size two.

We conjecture that all locally Paley graphs are known. For locally Paley( p) with p < 100000 this is true.

We demonstrate the criterion by super-polynomial lower bounds for explicit Boolean functions, associated with bipartite Paley graphs and partial t-designs. We then derive exponential lower bounds for clique-like graph functions of Tardos, thus establishing an exponential gap between the monotone real and non-monotone Boolean circuit complexities. Since we allow real gates, the criterion also implies corresponding lower bounds for the length of cutting planes proof in the propositional calculus.

Copyright (c) 1996 Elsevier Science B.V. All rights reserved. Determining the clique number of the Paley graph of order q, q≡1 (mod 4r a prime power, is a difficult problem. However, the work of Blokhuis implies that in the Paley graph of order q 2 , where q is any odd prime power, the clique number is in fact q. In this paper we construct maximal cliques of size (1r/(2r(q+1r or (1r/(2r(q+3r, accordingly as q≡1 (mod 4r or q≡3 (mod 4r, in the Paley graph of order q 2 . It is believed that these are the largest maximal cliques which are not maximum. We also briefly discuss maximal cliques in some graphs naturally associated with the interior and exterior points of a conic in PG(2,qr for odd prime powers q.

In this article we introduce the concept of (p alpha)-switching trees and use it to provide sufficient conditions on the abelian groups G and H for when CAY (G x H S boolean OR B) is Hamilton-decomposable given that CAY (G S) is Hamilton-decomposable and B is a basis for H. Applications of this result to elementary abelian groups and Paley graphs are given. (C) 2013 Elsevier B.V. All rights reserved.

Let m and n be nonnegative integers and k be a positive integer. A graph G is said to have property P(m, n, k) if for any set of m + n distinct vertices of G there are at least k other vertices, each of which is adjacent to the first m vertices of the set but not adjacent to any of the latter n vertices. The problem that arises is that of characterising graphs having property P(m, n, k). This problem has been considered by several authors and a number of results have been obtained. In this paper, we establish a lower bound on the order of a graph having property P(m, n, k). Further, we show that all sufficiently large Paley graphs satisfy properties P(1, n, k) and P(n, 1, k).

The restricted isometry property (RIP) is a well-known matrix condition that provides state-of-the-art reconstruction guarantees for compressed sensing. While random matrices are known to satisfy this property with high probability, deterministic constructions have found less success. In this paper, we consider various techniques for demonstrating RIP deterministically, some popular and some novel, and we evaluate their performance. In evaluating some techniques, we apply random matrix theory and inadvertently find a simple alternative proof that certain random matrices are RIP. Later, we propose a particular class of matrices as candidates for being RIP, namely, equiangular tight frames (ETFs). Using the known correspondence between real ETFs and strongly regular graphs, we investigate certain combinatorial implications of a real ETF being RIP. Specifically, we give probabilistic intuition for a new bound on the clique number of Paley graphs of prime order, and we conjecture that the corresponding ETFs are RIP in a manner similar to random matrices., 24 pages