A new Yang number and consequences

Base sequences BS(m, n) are quadruples (A; B; C; D) of {±1}-sequences, A and B of length m and C and D of length n, the sum of whose non-periodic auto-correlation functions is zero. Base sequences and some special subclasses of BS(n + 1, n) known as normal and near-normal sequences, NS(n) and NN(n), as well as T-sequences and orthogonal designs play a prominent role in modern constructions of Hadamard matrices. In our previous papers (Doković, Classification of near-normal sequences, arXiv:0903.4390v1 [math.CO] 25 Mar (2009); Doković, Some new near-normal sequences, arXiv:0907.3129v1 [math.CO] 17 Jul (2009)) we have classified the near-normal sequences NN(s) for all even integers s ≤ 32 (they do not exist for odd s > 1). We now extend the classification to the case s = 34. Moreover we construct the first example of near-normal sequences NN(36). Consequently, we construct for the first time T-sequences of length 73. For all smaller lengths, T-sequences were already known. Another consequence is that 73 is a Yang number, and a few important consequences of this fact are given.     

Modular sequences and modular Hadamard matrices

For every n divisible by 4, we construct a square matrix H of size n, with coefficients ± 1, such that H · H^t ≡ nI mod 32. This solves the 32‐modular version of the classical Hadamard conjecture. We also determine the set of lengths of 16‐modular Golay sequences. © 2001 John Wiley & Sons, Inc. J Combin Designs 9: 187–214, 2001     

A Hadamard matrix of order 428

Four Turyn type sequences of lengths 36, 36, 36, 35 are found by a computer search. These sequences give new base sequences of lengths 71, 71, 36, 36 and are used to generate a number of new T‐sequences. The first order of many new Hadamard matrices constructible using these new T‐sequences is 428. © 2004 Wiley Periodicals, Inc.     

Automorphisms of higher‐dimensional Hadamard matrices

This article derives from first principles a definition of equivalence for higher‐dimensional Hadamard matrices and thereby a definition of the automorphism group for higher‐dimensional Hadamard matrices. Our procedure is quite general and could be applied to other kinds of designs for which there are no established definitions for equivalence or automorphism. Given a two‐dimensional Hadamard matrix H of order ν, there is a Product Construction which gives an order ν proper n‐dimensional Hadamard matrix P⁽ⁿ⁾(H). We apply our ideas to the matrices P⁽ⁿ⁾(H). We prove that there is a constant c > 1 such that any Hadamard matrix H of order ν > 2 gives rise via the Product Construction to cν inequivalent proper three‐dimensional Hadamard matrices of order ν. This corrects an erroneous assertion made in the literature that ”P⁽ⁿ⁾(H) is equivalent to “P⁽ⁿ⁾(H′) whenever H is equivalent to H′.” We also show how the automorphism group of P⁽ⁿ⁾(H) depends on the structure of the automorphism group of H. As an application of the above ideas, we determine the automorphism group of P⁽ⁿ⁾(Hk) when Hk is a Sylvester Hadamard matrix of order 2^k. For ν = 4, we exhibit three distinct families of inequivalent Product Construction matrices P⁽ⁿ⁾(H) where H is equivalent to H₂. These matrices each have large but non‐isomorphic automorphism groups. © 2008 Wiley Periodicals, Inc. J Combin Designs 16: 507–544, 2008     

Bounds on the number of Hadamard designs of even order

A new lower bound on the number of non‐isomorphic Hadamard symmetric designs of even order is proved. The new bound improves the bound on the number of Hadamard designs of order 2n given in [12] by a factor of 8n ? 1 for every odd n > 1, and for every even n such that 4n ? 1 > 7 is a prime. For orders 8, 10, and 12, the number of non‐isomorphic Hadamard designs is shown to be at least 22,478,260, 1.31 × 10¹⁵, and 10²⁷, respectively. For orders 2n = 14, 16, 18 and 20, a lower bound of (4n ? 1)! is proved. It is conjectured that (4n ? 1)! is a lower bound for all orders 2n ≥ 14. © 2001 John Wiley & Sons, Inc. J Combin Designs 9: 363‐378, 2001     

Sequences in abelian groups G of odd order without zero-sum subsequences of length exp(G)

We present a new construction for sequences in the finite abelian group without zero-sum subsequences of length n, for odd n. This construction improves the maximal known cardinality of such sequences for r > 4 and leads to simpler examples for r > 2. Moreover we explore a link to ternary affine caps and prove that the size of the second largest complete caps in AG(5, 3) is 42.      

K4‐free graphs with no odd hole: Even pairs and the circular chromatic number

An odd hole in a graph is an induced cycle of odd length at least five. In this article we show that every imperfect K₄‐free graph with no odd hole either is one of two basic graphs, or has an even pair or a clique cutset. We use this result to show that every K₄‐free graph with no odd hole has circular chromatic number strictly smaller than 4. We also exhibit a sequence {H_n} of such graphs with lim_n→∞χ_c(H_n)=4. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 303–322, 2010     

Some new results on 1‐rotational 2‐factorizations of the complete graph

It is known that a necessary condition for the existence of a 1‐rotational 2‐factorization of the complete graph K_2n+1 under the action of a group G of order 2n is that the involutions of G are pairwise conjugate. Is this condition also sufficient? The complete answer is still unknown. Adapting the composition technique shown in Buratti and Rinaldi, J Combin Des, 16 (2008), 87–100, we give a positive answer for new classes of groups; for example, the groups G whose involutions lie in the same conjugacy class and having a normal subgroup whose order is the greatest odd divisor of |G|. In particular, every group of order 4t+2 gives a positive answer. Finally, we show that such a composition technique provides 2‐factorizations with a rich group of automorphisms. © 2009 Wiley Periodicals, Inc. J Combin Designs 18: 237–247, 2010     

Trace Representation of Legendre Sequences

In this paper, a Legendre sequence of period p for any odd prime p is explicitely represented as a sum of trace functions from GF(2 ⁿ ) to GF(2), where n is the order of 2 mod p.     

Independence,odd girth,and average degree

We prove several tight lower bounds in terms of the order and the average degree for the independence number of graphs that are connected and/or satisfy some odd girth condition. Our main result is the extension of a lower bound for the independence number of triangle‐free graphs of maximum degree at most three due to Heckman and Thomas [Discrete Math 233 (2001), 233–237] to arbitrary triangle‐free graphs. For connected triangle‐free graphs of order n and size m, our result implies the existence of an independent set of order at least (4n?m?1)/7. © 2010 Wiley Periodicals, Inc. J Graph Theory 67:96‐111, 2011     

On Hadamard matrices of order 2(p+1) with an automorphism of odd prime order p

In this paper, we investigate Hadamard matrices of order 2(p + 1) with an automorphism of odd prime order p. In particular, the classification of such Hadamard matrices for the cases p = 19 and 23 is given. Self‐dual codes related to such Hadamard matrices are also investigated. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 367–380, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10052     

Normal degree

The H‐normal degree n(A,H) associated with GCG‐LS algorithms is shown to be independent of H, thereby correcting an incompleteness in the literature. The normal degree n(A) for any normalizable matrix A when n(A)>1 is shown to sometimes occur sharply in the interval ≦n(A)≦m?1, where m is the degree of A's minimum polynomial, thereby clarifying previous estimates in the literature. Copyright © 2004 John Wiley & Sons, Ltd.     

Embeddings of Un(q2) and symmetric strongly regular graphs

In the geometric setting of the embedding of the unitary group U_n(q²) inside an orthogonal or a symplectic group over the subfield GF(q) of GF(q²), q odd, we show the existence of infinite families of transitive two‐character sets with respect to hyperplanes that in turn define new symmetric strongly regular graphs and two‐weight codes. © 2009 Wiley Periodicals, Inc. J Combin Designs 18: 248–253, 2010     

Facial non‐repetitive edge‐coloring of plane graphs

A sequence r₁, r₂, …, r_2n such that r_i=r_{n+ i} for all 1≤i≤n is called a repetition. A sequence S is called non‐repetitive if no block (i.e. subsequence of consecutive terms of S) is a repetition. Let G be a graph whose edges are colored. A trail is called non‐repetitive if the sequence of colors of its edges is non‐repetitive. If G is a plane graph, a facial non‐repetitive edge‐coloring of G is an edge‐coloring such that any facial trail (i.e. a trail of consecutive edges on the boundary walk of a face) is non‐repetitive. We denote π′_f(G) the minimum number of colors of a facial non‐repetitive edge‐coloring of G. In this article, we show that π′_f(G)≤8 for any plane graph G. We also get better upper bounds for π′_f(G) in the cases when G is a tree, a plane triangulation, a simple 3‐connected plane graph, a hamiltonian plane graph, an outerplanar graph or a Halin graph. The bound 4 for trees is tight. © 2010 Wiley Periodicals, Inc. J Graph Theory 66: 38–48, 2010     

A trace representation of binary Jacobi sequences

We determine the trace function representation, or equivalently, the Fourier spectral sequences of binary Jacobi sequences of period pq, where p and q are two distinct odd primes. This includes the twin-prime sequences of period p(p+2) whenever both p and p+2 are primes, corresponding to cyclic Hadamard difference sets.     

3‐Factor‐Criticality of Vertex‐Transitive Graphs

A graph of order n is p ‐factor‐critical, where p is an integer of the same parity as n, if the removal of any set of p vertices results in a graph with a perfect matching. 1‐factor‐critical graphs and 2‐factor‐critical graphs are factor‐critical graphs and bicritical graphs, respectively. It is well known that every connected vertex‐transitive graph of odd order is factor‐critical and every connected nonbipartite vertex‐transitive graph of even order is bicritical. In this article, we show that a simple connected vertex‐transitive graph of odd order at least five is 3‐factor‐critical if and only if it is not a cycle.     

On confidence sequences for the mean vector of a multivariate normal distribution

Let X₁, X₂,… be idd random vectors with a multivariate normal distribution N(μ, Σ). A sequence of subsets {R_n(a₁, a₂,…, a_n), n ≥ m} of the space of μ is said to be a (1 − α)-level sequence of confidence sets for μ if P(μ R_n(X₁, X₂,…, X_n) for every n ≥ m) ≥ 1 − α. In this note we use the ideas of Robbins Ann. Math. Statist. 41 (1970) to construct confidence sequences for the mean vector μ when Σ is either known or unknown. The constructed sequence R_n(X₁, X₂, …, X_n) depends on Mahalanobis' or Hotelling's according as Σ is known or unknown. Confidence sequences for the vector-valued parameter in the general linear model are also given.     

List multicoloring problems involving the k‐fold Hall numbers

We show that the four‐cycle has a k‐fold list coloring if the lists of colors available at the vertices satisfy the necessary Hall's condition, and if each list has length at least ?5k/3?; furthermore, the same is not true with shorter list lengths. In terms of h^(k)(G), the k ‐fold Hall number of a graph G, this result is stated as h^(k)(C₄)=2k??k/3?. For longer cycles it is known that h^(k)(C_n)=2k, for n odd, and 2k??k/(n?1)?≤h^(k)(C_n)≤2k, for n even. Here we show the lower bound for n even, and conjecture that this is the right value (just as for C₄). We prove that if G is the diamond (a four‐cycle with a diagonal), then h^(k)(G)=2k. Combining these results with those published earlier we obtain a characterization of graphs G with h^(k)(G)=k. As a tool in the proofs we obtain and apply an elementary generalization of the classical Hall–Rado–Halmos–Vaughan theorem on pairwise disjoint subset representatives with prescribed cardinalities. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 16–34, 2010.     

Periods in missing lengths of rainbow cycles

A cycle in an edge‐colored graph is said to be rainbow if no two of its edges have the same color. For a complete, infinite, edge‐colored graph G, define Then ??(G) is a monoid with respect to the operation n°m=n+ m?2, and thus there is a least positive integer π(G), the period of ??(G), such that ??(G) contains the arithmetic progression {N+ kπ(G)|k?0} for some sufficiently large N. Given that n∈??(G), what can be said about π(G)? Alexeev showed that π(G)=1 when n?3 is odd, and conjectured that π(G) always divides 4. We prove Alexeev's conjecture: Let p(n)=1 when n is odd, p(n)=2 when n is divisible by four, and p(n)=4 otherwise. If 2<n∈??(G) then π(G) is a divisor of p(n). Moreover, ??(G) contains the arithmetic progression {N+ kp(n)|k?0} for some N=O(n²). The key observations are: If 2<n=2k∈??(G) then 3n?8∈??(G). If 16≠n=4k∈??(G) then 3n?10∈??(G). The main result cannot be improved since for every k>0 there are G, H such that 4k∈??(G), π(G)=2, and 4k+ 2∈??(H), π(H)=4. © 2009 Wiley Periodicals, Inc. J Graph Theory     

Odd‐sized partitions of Russell‐sets

In the setting of ZF, i.e., Zermelo–Fraenkel set theory without the Axiom of Choice (AC), we study partitions of Russell‐sets into sets each with exactly n elements (called n ‐ary partitions), for some integer n. We show that if n is odd, then a Russell‐set X has an n ‐ary partition if and only if |X | is divisible by n. Furthermore, we establish that it is relative consistent with ZF that there exists a Russell‐set X such that |X | is not divisible by any finite cardinal n > 1 (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)