0,3

Theorem 3.7, p. 9, of Chappelon.

Abstract: A Steinhaus matrix is a binary square matrix of size n which is symmetric, with diagonal of zeros, and whose upper-triangular coefficients satisfy a_{i,j}=a_{i-1,j-1}+a_{i-1,j} for all 2 <= i<j <= n. Steinhaus matrices are determined by their first row. A Steinhaus graph is a simple graph whose adjacency matrix is a Steinhaus matrix.

We give a short new proof of a theorem, due to Dymacek, which states that even Steinhaus graphs, i.e. those with all vertex degrees even, have doubly-symmetric Steinhaus matrices. In 1979 Dymacek conjectured that the complete graph on two vertices K_2 is the only regular Steinhaus graph of odd degree.

Using Dymacek's theorem, we prove that if (a_{i,j})_{1 <= i,j <= n} is a Steinhaus matrix associated to a regular Steinhaus graph of odd degree then its sub-matrix (a_{i,j})_{2 <= i,j <= n-1} is a multi-symmetric matrix, that is a doubly-symmetric matrix where each row of its upper-triangular part is a symmetric sequence.

We prove that the multi-symmetric Steinhaus matrices of size $n$ whose Steinhaus graphs are regular modulo 4, i.e. where all vertex degrees are equal modulo 4, only depend on ceil (n/24} parameters for every even number n, and on ceil (n/30} parameters in the odd case. This result permits us to verify the Dymacek's conjecture up to 1500 vertices in the odd case.

Jonathan Chappelon, Regular Steinhaus graphs of odd degree

a(n) = 2^ceiling(n/6) for n even, 2^ceiling((n-3)/6) for n odd.

Sequence in context: A010554 A062610 A025801 this_sequence A060548 A058762 A029252

Adjacent sequences: A140423 A140424 A140425 this_sequence A140427 A140428 A140429

easy,more,nonn

Jonathan Vos Post (jvospost3(AT)gmail.com), Jun 18 2008