Asymptotic enumeration of sparse 0-1 matrices with irregular row and column sums

Let s=(s₁,…,s_m) and t=(t₁,…,t_n) be vectors of non-negative integer-valued functions with equal sum . Let N(s,t) be the number of m×n matrices with entries from {0,1} such that the ith row has row sum s_i and the jth column has column sum t_j. Equivalently, N(s,t) is the number of labelled bipartite graphs with degrees of the vertices in one side of the bipartition given by s and the degrees of the vertices in the other side given by t. We give an asymptotic formula for N(s,t) which holds when S→∞ with 1?st=o(S^2/3), where and . This extends a result of McKay and Wang [Linear Algebra Appl. 373 (2003) 273-288] for the semiregular case (when s_i=s for 1?i?m and t_j=t for 1?j?n). The previously strongest result for the non-semiregular case required 1?max{s,t}=o(S^1/4), due to McKay [Enumeration and Design, Academic Press, Canada, 1984, pp. 225-238].     

On the number of matrices and a random matrix with prescribed row and column sums and 0-1 entries

We consider the set Σ(R,C) of all m×n matrices having 0-1 entries and prescribed row sums R=(r₁,…,rm) and column sums C=(c₁,…,cn). We prove an asymptotic estimate for the cardinality |Σ(R,C)| via the solution to a convex optimization problem. We show that if Σ(R,C) is sufficiently large, then a random matrix D∈Σ(R,C) sampled from the uniform probability measure in Σ(R,C) with high probability is close to a particular matrix Z=Z(R,C) that maximizes the sum of entropies of entries among all matrices with row sums R, column sums C and entries between 0 and 1. Similar results are obtained for 0-1 matrices with prescribed row and column sums and assigned zeros in some positions.     

Presentations of alternating semigroups

One presentation of the alternating groupA _n hasn?2 generatorss ₁,…,s_n?2 and relationss ₁ ³ =s _i ² =(s_1?1s_i)³=(s_js_k)²=1, wherei>1 and |j?k|>1. Against this backdrop, a presentation of the alternating semigroupA _n ^c )A _n is introduced: It hasn?1 generatorss ₁,…,S _n?2,e, theA _n-relations (above), and relationse ²=e, (es ₁)⁴, (es _j)²=(es _j)⁴,es _i=s _i s ₁ ^-1 es ₁, wherej>1 andi≥1.     

Thue-Morse at multiples of an integer

Let t=(tn)_n?0 be the classical Thue-Morse sequence defined by , where s₂ is the sum of the bits in the binary representation of n. It is well known that for any integer k?1 the frequency of the letter “1” in the subsequence t₀,tk,t2k,… is asymptotically 1/2. Here we prove that for any k there is an n?k+4 such that tkn=1. Moreover, we show that n can be chosen to have Hamming weight ?3. This is best in a twofold sense. First, there are infinitely many k such that tkn=1 implies that n has Hamming weight ?3. Second, we characterize all k where the minimal n equals k, k+1, k+2, k+3, or k+4. Finally, we present some results and conjectures for the generalized problem, where s₂ is replaced by sb for an arbitrary base b?2.     

A contribution to the Zarankiewicz problem

Given positive integers let z(m,n,s,t) be the maximum number of ones in a (0,1) matrix of size m×n that does not contain an all ones submatrix of size s×t. We show that if s?2 and t?2, then for every k=0,…,s-2,

z(m,n,s,t)?(s-k-1)^1/tnm^1-1/t+kn+(t-1)m^1+k/t.     

Davenport constant with weights and some related questions, II

Let G be a finite abelian group of order n and let A⊆Z be non-empty. Generalizing a well-known constant, we define the Davenport constant of G with weight A, denoted by DA(G), to be the least natural number k such that for any sequence (x₁,…,xk) with xi∈G, there exists a non-empty subsequence (xj₁,…,xjl) and a₁,…,al∈A such that . Similarly, for any such set A, EA(G) is defined to be the least t∈N such that for all sequences (x₁,…,xt) with xi∈G, there exist indices j₁,…,jn∈N,1?j₁<?<jn?t, and ?₁,…,?n∈A with . In the present paper, we establish a relation between the constants DA(G) and EA(G) under certain conditions. Our definitions are compatible with the previous generalizations for the particular group G=Z/nZ and the relation we establish had been conjectured in that particular case.     

Newman's phenomenon for generalized Thue-Morse sequences

Let t_j=(-1)^s(j) be the Thue-Morse sequence with s(j) denoting the sum of the digits in the binary expansion of j. A well-known result of Newman [On the number of binary digits in a multiple of three, Proc. Amer. Math. Soc. 21 (1969) 719-721] says that t₀+t₃+t₆+?+t_3k>0 for all k?0.In the first part of the paper we show that t₁+t₄+t₇+?+t_3k+1<0 and t₂+t₅+t₈+?+t_3k+2?0 for k?0, where equality is characterized by means of an automaton. This sharpens results given by Dumont [Discrépance des progressions arithmétiques dans la suite de Morse, C. R. Acad. Sci. Paris Sér. I Math. 297 (1983) 145-148]. In the second part we study more general settings. For a,g?2 let ω_a=exp(2πi/a) and , where s_g(j) denotes the sum of digits in the g-ary digit expansion of j. We observe trivial Newman-like phenomena whenever a|(g-1). Furthermore, we show that the case a=2 inherits many Newman-like phenomena for every even g?2 and large classes of arithmetic progressions of indices. This, in particular, extends results by Drmota and Ska?ba [Rarified sums of the Thue-Morse sequence, Trans. Amer. Math. Soc. 352 (2000) 609-642] to the general g-case.     

Approximating reversal distance for strings with bounded number of duplicates

For a string A=a₁…a_n, a reversalρ(i,j), 1?i?j?n, transforms the string A into a string A^′=a₁…a_i-1a_ja_j-1…a_ia_j+1…a_n, that is, the reversal ρ(i,j) reverses the order of symbols in the substring a_i…a_j of A. In the case of signed strings, where each symbol is given a sign + or -, the reversal operation also flips the sign of each symbol in the reversed substring. Given two strings, A and B, signed or unsigned, sorting by reversals (SBR) is the problem of finding the minimum number of reversals that transform the string A into the string B.Traditionally, the problem was studied for permutations, that is, for strings in which every symbol appears exactly once. We consider a generalization of the problem, k-SBR, and allow each symbol to appear at most k times in each string, for some k?1. The main result of the paper is an O(k²)-approximation algorithm running in time O(n). For instances with , this is the best known approximation algorithm for k-SBR and, moreover, it is faster than the previous best approximation algorithm.     

A new characterization of dual bases in finite fields and its applications

We propose a new characterization of dual bases in finite fields. Let A=(α₁,…,α_n) be a basis of F over F_q and its dual basis B=(β₁,…,β_n) with the transition matrix C∈GL_n(F_q) such that (β₁,…,β_n)=(α₁,…,α_n)C. We show that holds for all 1?k?n, where T_k∈M_n(F_q) satisfies α_k(α₁,…,α_n)=(α₁,…,α_n)T_k. Conversely, suppose F=F_q(α_k^′) and for some 1?k^′?n and G∈GL_n(F_q), then B is equivalent to (α₁,…,α_n)G. As applications, we can construct the dual basis of a given basis A or determine whether the dual basis of A satisfies the desired conditions from T_k. This generalizes the results obtained by Liao and Sun for normal bases. Furthermore, we give a simple proof of the theorem of Gollmann, Wang and Blake for polynomial bases.     

Two equivalent measures on weighted hypergraphs

Let H=(N,E,w) be a hypergraph with a node set N={0,1,…,n-1}, a hyperedge set E⊆2^N, and real edge-weights w(e) for e∈E. Given a convex n-gon P in the plane with vertices x₀,x₁,…,x_n-1 which are arranged in this order clockwisely, let each node i∈N correspond to the vertex x_i and define the area A_P(H) of H on P by the sum of the weighted areas of convex hulls for all hyperedges in H. For 0?i<j<k?n-1, a convex three-cut C(i,j,k) of N is {{i,…,j-1}, {j,…,k-1}, {k,…,n-1,0,…,i-1}} and its size c_H(i,j,k) in H is defined as the sum of weights of edges e∈E such that e contains at least one node from each of {i,…,j-1}, {j,…,k-1} and {k,…,n-1,0,…,i-1}. We show that the following two conditions are equivalent:

•

A_P(H)?A_P(H^′) for all convex n-gons P.

•

c_H(i,j,k)?c_H^′(i,j,k) for all convex three-cuts C(i,j,k).

From this property, a polynomial time algorithm for determining whether or not given weighted hypergraphs H and H^′ satisfy “A_P(H)?A_P(H^′) for all convex n-gons P” is immediately obtained.     

Degree complete graphs

Ryser [Combinatorial Mathematics, Carus Mathematical Monograph, vol. 14, Wiley, New York, 1963] introduced a partially ordered relation ‘?’ on the nonnegative integral vectors. It is clear that if S=(s₁,s₂,…,s_n) is an out-degree vector of an orientation of a graph G with vertices 1,2,…,n, then

(Π)     

Equitable specialized block-colourings for 4-cycle systems—I

A block-colouring of a 4-cycle system (V,B) of order v=1+8k is a mapping ?:B→C, where C is a set of colours. Every vertex of a 4-cycle system of order v=8k+1 is contained in blocks and r is called, using the graph theoretic terminology, the degree or the repetition number. A partition of degree r into s parts defines a colouring of type s in which the blocks containing a vertex x are coloured exactly with s colours. For a vertex x and for i=1,2,…,s, let B_x,i be the set of all the blocks incident with x and coloured with the ith colour. A colouring of type s is equitable if, for every vertex x, we have |B_x,i−B_x,j|≤1, for all i,j=1,…,s. In this paper we study bicolourings, tricolourings and quadricolourings, i.e. the equitable colourings of type s with s=2, s=3 and s=4, for 4-cycle systems.     

Matrices of zeros and ones with fixed row and column sum vectors

Let m and n be positive integers, and let R=(r₁,…,r_m) and S=(s₁,…,s_n) be nonnegative integral vectors. We survey the combinational properties of the set of all m × n matrices of 0's and 1's having r_i1's in row i ands_i 1's in column j. A number of new results are proved. The results can be also be formulated in terms of a set of bipartite graps with bipartition into m and n vertices having degree sequence R and S, respectively. They can also be formulated in terms of the set of hypergraphs with m vertices having degree sequence R and n edges whose cardinalities are given by S.     

Bounds on some van der Waerden numbers

For positive integers s and k₁,k₂,…,ks, the van der Waerden number w(k₁,k₂,…,ks;s) is the minimum integer n such that for every s-coloring of set {1,2,…,n}, with colors 1,2,…,s, there is a ki-term arithmetic progression of color i for some i. We give an asymptotic lower bound for w(k,m;2) for fixed m. We include a table of values of w(k,3;2) that are very close to this lower bound for m=3. We also give a lower bound for w(k,k,…,k;s) that slightly improves previously-known bounds. Upper bounds for w(k,4;2) and w(4,4,…,4;s) are also provided.     

The inversion formulae for automorphisms of polynomial algebras and rings of differential operators in prime characteristic

Let K be an arbitrary field of characteristic p>0. We find an explicit formula for the inverse of any algebra automorphism of any of the following algebras: the polynomial algebra P_n?K[x₁,…,x_n], the ring of differential operators D(P_n) on P_n, D(P_n)⊗P_m, the n’th Weyl algebra A_n or A_n⊗P_m, the power series algebra K[[x₁,…,x_n]], the subalgebra T_k1,…,kn of D(P_n) generated by P_n and the higher derivations , 0≤j<p^k_i, i=1,…,n (where k₁,…,k_n∈N), T_k1,…,kn⊗P_m or an arbitrary central simple (countably generated) algebra over an arbitrary field.     

Unextendible product bases and 1-factorization of complete graphs

Let f(k₁,…,k_m) be the minimal value of size of all possible unextendible product bases in the tensor product space . We have trivial lower bounds and upper bound k₁?k_m. Alon and Lovász determined all cases such that f(k₁,…,k_m)=n(k₁,…,k_m). In this paper we determine all cases such that f(k₁,…,k_m)=k₁?k_m by presenting a sharper upper bound. We also determine several cases such that f(k₁,…,k_m)=n(k₁,…,k_m)+1 by using a result on 1-factorization of complete graphs.     

Convolution identities and lacunary recurrences for Bernoulli numbers

We extend Euler's well-known quadratic recurrence relation for Bernoulli numbers, which can be written in symbolic notation as n(B₀+B₀)=−nBn−1−(n−1)Bn, to obtain explicit expressions for n(Bk+Bm) with arbitrary fixed integers k,m?0. The proof uses convolution identities for Stirling numbers of the second kind and for sums of powers of integers, both involving Bernoulli numbers. As consequences we obtain new types of quadratic recurrence relations, one of which gives B6k depending only on B2k,B2k+2,…,B4k.     

Matrices with different Gondran–Minoux and determinantal ranks over max-algebras

Let GMr(A) be the row Gondran–Minoux rank of a matrix, GMc(A) be the column Gondran–Minoux rank, and d(A) be the determinantal rank, respectively. The following problem was posed by M. Akian, S. Gaubert, and A. Guterman: Find the minimal numbers m and n such that there exists an (m × n)-matrix B with different row and column Gondran–Minoux ranks. We prove that in the case GMr(B) > GMc(B) the minimal m and n are equal to 5 and 6, respectively, and in the case GMc(B) > GMr(B) the numbers m = 6 and n = 5 are minimal. An example of a matrix $ A \in {\mathcal{M}_{5 \times 6}}\left( {{\mathbb{R}_{\max }}} \right) $ such that GMr(A) = GMc(A ^t) = 5 and GMc(A) = GMr(A ^t) = 4 is provided. It is proved that p = 5 and q = 6 are the minimal numbers such that there exists an (p×q)-matrix with different row Gondran–Minoux and determinantal ranks.