|
| |
|
|
A263626
|
|
Number of inequivalent self-complementary Seidel matrices of order n.
|
|
2
|
|
|
|
1, 1, 0, 1, 1, 4, 0, 19, 10, 360, 0, 25112, 720, 6975976, 0, 7030565576, 703760, 25473667704064, 0, 333377175390634880, 9168331776, 15881995583375102901824, 0, 2775171714758797872451279104, 1601371799340544, 1790676527377592615808645709379328, 0, 4291738728096066980970104665682237420544, 3837878966366932639744, 38401679870039848205115101680007123726281532416, 0
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,6
|
|
|
COMMENTS
|
On p. 9 of their arxiv paper, Greaves et al. (2014-2015) state that "The number of self-complementary Seidel matrices is known explicitly" and refer to Sozański (1980). The authors apparently refer to formula (20) in Theorem 2 (p. 139) in Sozański (1980). (See also p. 218 in Greaves et al. (2016).)
The so-called "Seidel matrix" of a graph G was apparently introduced by the Dutch mathematician Johan Jacob Seidel (1967, 1968, and with van Lint in 1966). They are not related to the so-called Euler-Seidel (or just Seidel) matrices named after Leonhard Euler and Philipp Ludwig von Seidel.
A Seidel matrix S = S(G) of a simple labeled graph G with vertex set V = {v_1, ..., v_n} is an n x n symmetric matrix with rows and columns corresponding to the n vertices such that S(i,j) is defined in the following way: S(i,j) = 0 iff i = j; S(i,j) = -1 iff vertex v_i is connected to vertex v_j (i <> j), and S(i,j) = 1 iff vertex v_i is not connected to vertex v_j (i <> j). Thus, S(G) = J - I - 2*A(G), where J is an n x n matrix of 1's, I is the n x n identity matrix, and A(G) is the adjancecy matrix of the labeled graph G.
Two Seidel matrices S1 and S2 are said to be equivalent if S1 can be obtained from S2 by a sequence of simultaneous row i to j and column i to j permutations or by a simultaneous multiplication of a row i and a column i by -1.
Thus, Seidel matrices S1 and S2 are equivalent iff there is a symmetric signed permutation matrix P such that S1 = P*S2*P^T.
A Seidel matrix S is called "self-complementary" if S is equivalent to -S. Thus, S is self-complementary iff there is a symmetric signed permutation matrix P such that S = -P*S*P^T. The sequence a(n) counts equivalence classes of self-complementary n x n Seidel matrices.
In terms of a labeled graph G with Seidel matrix S and vertex set V, a simultaneous row i to j and column i to j permutation of S corresponds to exchanging labels between vertices v_i and v_j. On the other hand, a simultaneous multiplication of row i and column i by -1 corresponds to what Mallows and Sloane (1975) call "switching at node" v_i: if A(i) is the set of vertices in V to which v_i is connected and B(i) is the set of vertices in V to which v_i is not connected, "switching at node v_i" means switching the sets A(i) and B(i) (the vertices connected with the vertices non-connected to v_i). Of course, either A(i) or B(i) may be empty.
Mallows and Sloane (1975) proved that the number of equivalence classes of Seidel matrices of order n is equal to the number of unlabeled even graphs (known colloquially as unlabeled "Euler graphs"). See sequence A002854.
The equivalence class of graphs corresponding to a self-complementary Seidel matrix is closed under complementation.
For simplicity, in the examples below that illustrate equivalence classes Seidel matrices, we only include unlabeled graphs on n = 3 or n = 4 nodes rather than labeled ones. (End)
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = 0 for 3 == n mod 4 (see the references).
a(n) = Sum_{p in M2(n)} 2^(I2(p) - I1(p))/f(p), where
p = (p[1], ..., p[n]) is a partition of n written in frequency or multiplicity notation with p[i] >= 0 for i = 1..n and Sum_{i=1..n} i*p[i] = n;
M2(n) is the set of all partitions p of n with either (a) p[i] = 0 for all odd i or (b) p[1] = 1 or 2, and p[i] = 0 for i >= 2 with 0 <> (i mod 4);
f(p) = Product_{i=1..n} p[i]!*i^p[i];
J(p) = Sum_{j=1..floor((n-1)/2)} p[2*j+1];
I1(p) = Sum_{i=1..n} p[i] - if(J(p) == 0, 0, 1); and
I2(p) = (Sum_{1 <= i, j <= n} p[i]*p[j]*gcd(i,j) - J(p))/2.
(This is modification of formula (20) in Theorem 2 (p. 139) in Sozański (1980).)
Note that, if we take sum over all partitions of n, rather than just over M2(n), then we get A002854(n).
If, on the other hand, we consider Sum_{p in M1(n)} 2^I2(p)/f(p), where M1(n) is the set of all partitions p of n with p[1] in {0,1} and p[i] = 0 for i >= 2 with 0 <> (i mod 4), then we get A000171(n).
Finally, if we consider Sum_{p} 2^I2(p)/f(p) over all partitions p of n, then we get A000088(n). (End)
|
|
|
EXAMPLE
|
For n = 3, we have the following A000088(3) = 4 unlabeled graphs on 3 nodes:
(1) o (2) o (3) o (4) o
/ \ / / \
o o o o o o o-- o
Graphs (1) and (2) form one equivalence class and graphs (3) and (4) form another equivalence class (under the Seidel-Mallows-Sloane "switching" equivalence relation). The complement of (1) is (4) and the complement of (2) is (3), so there are no self-complementary classes; i.e., a(3) = 0. (Here, the number of equivalence classes is A002854(3) = 2.)
For n = 4, the A000088(4) = 11 unlabeled graphs are listed in Mallows and Sloane (1975). There are A002854(4) = 3 equivalence classes, only one of which is self-complementary:
(1) o o (2) o -- o (3) o--o (4) o o (5) o--o
| | | | /| | /|
o o o o o--o o--o o--o
Thus, a(4) = 1. (End)
|
|
|
PROG
|
(PARI) a(n)={local(p=vector(n));
my(S=0, J() = sum(j=0, floor((n-1)/2), p[2*j+1]),
I1() = sum(i=1, n, p[i]) - if(J() == 0, 0, 1),
I2() = (sum(i=1, n, sum(j=1, n, p[i]*p[j]*gcd(i, j))) - J())/2,
M2() = sum(i=1, n, if(1 == (i%2), p[i], 0))*(abs((p[1]-1)*(p[1]-2)) + sum(j=2, n, if(0!=(j%4), p[j], 0))),
M() = I2() - I1(),
inc()=!forstep(i=n, 1, -1, p[i]<n\i && p[i]++ && return; p[i]=0), t); until(inc(), t=0; for( i=1, n, if( n < t+=i*p[i], until(i++>n, p[i]=n); next(2))); t==n && S+=if(M2() == 0, 2^M()/prod(i=1, n, i^p[i]*p[i]!), 0)); S} \\ This is a modification of M. F. Hasler's PARI program from A002854. - Petros Hadjicostas, Mar 02 2021
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
Terms a(13) to a(21) copied from Table I (p. 140) in Sozański (1980). - Petros Hadjicostas, Feb 27 2021
|
|
|
STATUS
|
approved
|
| |
|
|
