Page 154 - Ellingham, Mark, Mariusz Meszka, Primož Moravec, Enes Pasalic, 2014. 2014 PhD Summer School in Discrete Mathematics. Koper: University of Primorska Press. Famnit Lectures, 3.
P. 154
4.6 Graph theoretic aspects of Boolean functions
a k -subset D of G with 1G ∈ D is a (v, k , λ, µ)-PDS if and only if the following equation
holds:
DD(−1) = (k − µ)1G + (λ − µ)D + µG , (4.16)
where in R[G ] we denote D = g ∈G d g g and D(t ) = g ∈G d g g t , for d g ∈ R. Combinato-
rial objects associated with partial difference sets are strongly regular graphs. A graph Γ
with v vertices is called a (v, k , λ, µ) strongly regular graph (SRG) if each vertex is adjacent
to exactly k other vertices, any two adjacent vertices have exactly λ common neighbours,
and any two non-adjacent vertices have exactly µ common neighbours. Given a group G
of order v and a k -subset D of G with 1G ∈ D and D−1 = D, the graph Γ = (V, E ) is called
the Cayley graph generated by D in G and is defined as follows:
1. The vertex set V is G ;
2. Two vertices g , h are joined by an edge if and only if g h−1 ∈ D.
The following result links together the notions of partial difference set and the property
of a graph being strongly regular.
Theorem 4.6.1 [13] Let Γ be the Cayley graph generated by a k -subset D of a multiplica-
tive group G with order v . Then Γ is a (v, k , λ, µ) strongly regular graph if and only if D is
a (v, k , λ, µ)-PDS with 1G ∈ D and D−1 = D.
Note that in the binary case, when Boolean functions f : n → 2 are considered, the
2
Cayley graph is induced with respect to a subset of the elementary additivie Abelian 2-
group n . Since the condition that for d ∈D we must have −d ∈ D, any D ⊆ 2n will
2
define the Cayley graph (each element is its own additive inverse) so that there is an edge
between g and h if and only if h ⊕ g ∈ D. The Cayley graph Γf = ( n , E f ) associated to a
2
Boolean function f is defined by selecting D = {x ∈ n : f (x ) = 1} (D is called the support
2
set of f ) and defining the set of edges as,
E f = {(u , w ) ∈ n × n | f (u ⊕ w) = 1},
2 2
where for convenience we use the boldface to denote the elements of n so that u =
2
(u 1, . . . , u n ). The operation ⊕ over n is of course the componentwise modulo 2 addition.
2
Furthermore, we specify the elements of n by using the decimal representation of their
2
indices, thus u0 = (0, . . . , 0), u1 = (1, . . . , 0), . . ., u2n −1 = (1, . . . , 1).
A graph is called regular of degree (valency) r if every vertex has degree (valency)
r , that is, the number of edges incident to it is r . The Cayley graph Γf associated to
any Boolean function f is obviously D regular. On the other hand, such a graph with
parameters ( n , D, d , e ) is called strongly regular graph (SRG) if there exist nonnegative
2
integers e , d such that for all vertices u , v the number of vertices adjacent to both u and
v is e if u , v are adjacent, respectively, this number is d if u , v are nonadjacent. An easy
a k -subset D of G with 1G ∈ D is a (v, k , λ, µ)-PDS if and only if the following equation
holds:
DD(−1) = (k − µ)1G + (λ − µ)D + µG , (4.16)
where in R[G ] we denote D = g ∈G d g g and D(t ) = g ∈G d g g t , for d g ∈ R. Combinato-
rial objects associated with partial difference sets are strongly regular graphs. A graph Γ
with v vertices is called a (v, k , λ, µ) strongly regular graph (SRG) if each vertex is adjacent
to exactly k other vertices, any two adjacent vertices have exactly λ common neighbours,
and any two non-adjacent vertices have exactly µ common neighbours. Given a group G
of order v and a k -subset D of G with 1G ∈ D and D−1 = D, the graph Γ = (V, E ) is called
the Cayley graph generated by D in G and is defined as follows:
1. The vertex set V is G ;
2. Two vertices g , h are joined by an edge if and only if g h−1 ∈ D.
The following result links together the notions of partial difference set and the property
of a graph being strongly regular.
Theorem 4.6.1 [13] Let Γ be the Cayley graph generated by a k -subset D of a multiplica-
tive group G with order v . Then Γ is a (v, k , λ, µ) strongly regular graph if and only if D is
a (v, k , λ, µ)-PDS with 1G ∈ D and D−1 = D.
Note that in the binary case, when Boolean functions f : n → 2 are considered, the
2
Cayley graph is induced with respect to a subset of the elementary additivie Abelian 2-
group n . Since the condition that for d ∈D we must have −d ∈ D, any D ⊆ 2n will
2
define the Cayley graph (each element is its own additive inverse) so that there is an edge
between g and h if and only if h ⊕ g ∈ D. The Cayley graph Γf = ( n , E f ) associated to a
2
Boolean function f is defined by selecting D = {x ∈ n : f (x ) = 1} (D is called the support
2
set of f ) and defining the set of edges as,
E f = {(u , w ) ∈ n × n | f (u ⊕ w) = 1},
2 2
where for convenience we use the boldface to denote the elements of n so that u =
2
(u 1, . . . , u n ). The operation ⊕ over n is of course the componentwise modulo 2 addition.
2
Furthermore, we specify the elements of n by using the decimal representation of their
2
indices, thus u0 = (0, . . . , 0), u1 = (1, . . . , 0), . . ., u2n −1 = (1, . . . , 1).
A graph is called regular of degree (valency) r if every vertex has degree (valency)
r , that is, the number of edges incident to it is r . The Cayley graph Γf associated to
any Boolean function f is obviously D regular. On the other hand, such a graph with
parameters ( n , D, d , e ) is called strongly regular graph (SRG) if there exist nonnegative
2
integers e , d such that for all vertices u , v the number of vertices adjacent to both u and
v is e if u , v are adjacent, respectively, this number is d if u , v are nonadjacent. An easy
