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.     

Properties of (0, 1)-matrices with no triangles

We study (0, 1)-matrices which contain no triangles (submatrices of order 3 with row and column sums 2) previously studied by Ryser. Let the row intersection of row i and row j of some matrix, when regarded as a vector, have a 1 in a given column if both row i and row j do and a zero otherwise. For matrices with no triangles, columns sums ?2, we find that the number of linearly independent row intersections is equal to the number of distinct columns. We then study the extremal (0, 1)-matrices with no triangles, column sums ?2, distinct columns, i.e., those of size mx(^m₂). The number of columns of column sum l is m ? l + 1 and they form a (l ? 1)-tree. The ((^m₂)) columns have a unique SDR of pairs of rows with 1's. Also, these matrices have a fascinating inductive buildup. We finish with an algorithm for constructing these matrices.     

A bijection between certain non-crossing partitions and sequences

We present a bijection between non-crossing partitions of the set [2n+1] into n+1 blocks such that no block contains two consecutive integers, and the set of sequences such that 1?s_i?i, and if s_i=j, then s_i-r?j-r for 1?r?j-1.     

On a characterization of irreducibility of a non-negative matrix

Let A denote an n×n matrix with all its elements real and non-negative, and let r_i be the sum of the elements in the ith row of A, i=1,…,n. Let B=A?D(r₁,…,r_n), where D(r₁,…,r_n) is the diagonal matrix with r_i at the position (i,i). Then it is proved that A is irreducible if and only if rank B=n?1 and the null space of B^T contains a vector d whose entries are all non-null.     

Enumeration of arrays of a given size

Enumeration of arrays whose row and column sums are specified have been studied by a number of people. It has been determined that the function that enumerates square arrays of dimension n, whose rows and columns sum to a fixed non-negative integer r, is a polynomial in r of degree (n ? 1)².In this paper we consider rectangular arrays whose rows sum to a fixed non-negative integer r and whose columns sum to a fixed non-negative integer s, determined by ns = mr. in particular, we show that the functions which enumerate 2 × n and 3 × n arrays with fixed row sums $\text{nr}\text{(2, n)}$ and $\text{nr}\text{(3, n)}$, where the symbol (a, b) denotes the greatest common divisor of a and b, and fixed column sums, are polynomials in r of degrees (n ? 1) and 2(n ? 1) respectively. We have found simple formulas to evaluate these polynomials for negative values, - r, and we show that for certain small negative integers our polynomials will always be zero. We also considered the generating functions of these polynomials and show that they are rational functions of degrees less than zero, whose denominators are of the forms (1 ? y)ⁿ and (1 ? y)²ⁿ?1 respectively and whose numerators are polynomials in y whose coefficients satisfy certain properties. In the last section we list the actual polynomials and generating functions in the 2 × n and 3 × n cases for small specific values of n.     

E-optimality of some row and column designs

In this paper we consider experimental settings where treatments are being tested in b ₁ rows and b ₂ columns of sizes k _1i and k _2j , respectively, i=1,2,..., b ₁, j=1,2,..., b ₂. Some sufficient conditions for designs to be E-optimal in these classes are derived and some necessary and sufficient conditions for the E-optimality of some special classes of row and column designs are presented. Examples are also given to illustrate this theory.     

Properties of (0, 1)-matrices without certain configurations

We generalize results of Ryser on (0, 1)-matrices without triangles, 3 × 3 submatrices with row and column sums 2. The extremal case of matrices without triangles was previously studied by the author. Let the row intersection of row i and row j (i ≠ j) of some matrix, when regarded as a vector, have a 1 in a given column if both row i and row j do not 0 otherwise. For matrices satisfying some conditions on forbidden configurations and column sums ? 2, we find that the number of linearly independent row intersections is equal to the number of distinct columns. The extremal matrices with m rows and $\text{(}\text{m}\text{2}\text{)}$ distinct columns have a unique SDR of pairs of rows with 1's. A triangle bordered with a column of 0's and its (0, 1)-complement are also considered as forbidden configurations. Similar results are obtained and the extremal matrices are closely related to the extremal matrices without triangles.     

Intersection patterns of convex sets

LetK ₁,…K_n be convex sets inR ^d. For 0≦i denote byf _ithe number of subsetsS of {1,2,…,n} of cardinalityi+1 that satisfy ∩{K _i∶i∈S}≠Ø. We prove:Theorem.If f _d+r=0 for somer r>=0, then {fx161-1} This inequality was conjectured by Katchalski and Perles. Equality holds, e.g., ifK ₁=…=K_r=R^d andK _r+1,…,K_n aren?r hyperplanes in general position inR ^d. The proof uses multilinear techniques (exterior algebra). Applications to convexity and to extremal set theory are given.     

A presentation for the unipotent group over F2

We define Unipn(F₂) to be the group of invertible upper-triangular matrices over F₂, the field of 2 elements. Let s _i for i = 1,2,…,n - 1 denote the matrix whosne diagonal entries are all 1, and whose only other nonzero entry is in the ith row and (i + 1)st column. Then it is easy to see that the s _i generate Unipn(F2). Reiner [4] gave relations among the s _i, which he conjectured gave a presentation for Unip_n(F₂). We show that a subset of these relations suffice to present the group     

Refined enumerations of alternating sign matrices: monotone (<Emphasis Type="Italic">d</Emphasis>,<Emphasis Type="Italic">m</Emphasis>)-trapezoids with prescribed top and bottom row

Monotone triangles are plane integer arrays of triangular shape with certain monotonicity conditions along rows and diagonals. Their significance is mainly due to the fact that they correspond to n×n alternating sign matrices when prescribing (1,2,…,n) as bottom row of the array. We define monotone (d,m)-trapezoids as monotone triangles with m rows where the d−1 top rows are removed. (These objects are also equivalent to certain partial alternating sign matrices.) It is known that the number of monotone triangles with bottom row (k ₁,…,k _n ) is given by a polynomial α(n;k ₁,…,k _n ) in the k _i ’s. The main purpose of this paper is to show that the number of monotone (d,m)-trapezoids with prescribed top and bottom row appears as a coefficient in the expansion of a specialisation of α(n;k ₁,…,k _n ) with respect to a certain polynomial basis. This settles a generalisation of a recent conjecture of Romik et al. (Adv. Math. 222:2004–2035, 2009). Among other things, the result is used to express the number of monotone triangles with bottom row (1,2,…,i−1,i+1,…,j−1,j+1,…,n) (which is, by the standard bijection, also the number of n×n alternating sign matrices with given top two rows) in terms of the number of n×n alternating sign matrices with prescribed top and bottom row, and, by a formula of Stroganov for the latter numbers, to provide an explicit formula for the first numbers. (A formula of this type was first derived by Karklinsky and Romik using the relation of alternating sign matrices to the six-vertex model.)     

Wallman compactification and matrices of zeroes and ones

Let M be an m by n matrix (where m and n are any finite or infinite cardinals) such that the entries of M are 0's or 1's and M contains the zero row $\text{0}$ and the rows of M are closed under coordinatewise multiplication. We prove that M can be extended to an m by n′ ? n matrix M′ such that the entries of M′ are 0's or 1's and M′ contains the zero row 0?′ and the extension preserves the zero products. Moreover, the newly introduced columns (if any) are pairwise distinct. Furthermore, if E′ is any set of rows of M′ with the property that for every finite subset of rows r′_i of E′ there exists j < n′ such that r′_ij = 1, then every subset of rows of E′ has the same property. We rephrase this by saying that if E′ has the finite intersection property then E′ has a nonempty intersection. We also show (this time by Zorn's lemma) that there exists an extension of M with all the abovementioned properties such that the extension preserves products sums, complements and the newly introduced columns (if any) are pairwise distinct in a stricter sense. In effect, our result shows that the classical Wallman compactification theorem can be formulated purely combinatorially requiring no introduction of any topology on n.     

Least squares solutions to AX = B for bisymmetric matrices under a central principal submatrix constraint and the optimal approximation

A matrix A∈R^n×n is called a bisymmetric matrix if its elements a_i,j satisfy the properties a_i,j=a_j,i and a_i,j=a_n-j+1,n-i+1 for 1?i,j?n. This paper considers least squares solutions to the matrix equation AX=B for A under a central principal submatrix constraint and the optimal approximation. A central principal submatrix is a submatrix obtained by deleting the same number of rows and columns in edges of a given matrix. We first discuss the specified structure of bisymmetric matrices and their central principal submatrices. Then we give some necessary and sufficient conditions for the solvability of the least squares problem, and derive the general representation of the solutions. Moreover, we also obtain the expression of the solution to the corresponding optimal approximation problem.     

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.     

Zero-free regions of derivatives of Riemann zeta function

Zero-free regions of thekth derivative of the Riemann zeta function ζ^(k)(s) are investigated. It is proved that fork≥3, ζ^(k)(s) has no zero in the region Res≥(1·1358826...)k+2. This result is an improvement upon the hitherto known zero-free region Res≥(7/4)k+2 on the right of the imaginary axis. The known zero-free region on the left of the imaginary axis is also improved by proving that ζ ^k)(s) may have at the most a finite number of non-real zeros on the left of the imaginary axis which are confined to a semicircle of finite radiusr _k centred at the origin.     

On a problem of Erdős

Let s≥2 be an integer. Denote by f ₁(s) the least integer so that every integer l>f ₁(s) is the sum of s distinct primes. Erd?s proved that f ₁(s)<p ₁+p ₂+?+p _s +Cslogs, where p _i is the ith prime and C is an absolute constant. In this paper, we prove that f ₁(s)=p ₁+p ₂+?+p _s +(1+o(1))slogs=p ₂+p ₃+?+p _s+1+o(slogs). This answers a question posed by P. Erd?s.     

Properties of Euclidean and non-Euclidean distance matrices

A distance matrix D of order n is symmetric with elements $\text{?}\text{1}\text{2}\text{d}{}_{\mathrm{ij}}{}^2$, where d_ii=0. D is Euclidean when the $\text{1}\text{2}\text{n(n?1)}$ quantities d_ij can be generated as the distances between a set of n points, X (n×p), in a Euclidean space of dimension p. The dimensionality of D is defined as the least value of p=rank(X) of any generating X; in general p+1 and p+2 are also acceptable but may include imaginary coordinates, even when D is Euclidean. Basic properties of Euclidean distance matrices are established; in particular, when ρ=rank(D) it is shown that, depending on whether e^TD^?e is not or is zero, the generating points lie in either p=ρ?1 dimensions, in which case they lie on a hypersphere, or in p=ρ?2 dimensions, in which case they do not. (The notation e is used for a vector all of whose values are one.) When D is non-Euclidean its dimensionality p=r+s will comprise r real and s imaginary columns of X, and (r, s) are invariant for all generating X of minimal rank. Higher-ranking representations can arise only from p+1=(r+1)+s or p+1=r+ (s+1) or p+2=(r+1)+(s+1), so that not only are r, s invariant, but they are both minimal for all admissible representations X.     

Maximal sets of points in finite projective space,no t-linearly dependent

Consider a finite (t + r ? 1)-dimensional projective space PG(t + r ? 1, s) based on the Galois field GF(s), where s is prime or power of a prime. A set of k distinct points in PG(t + r ? 1, s), no t-linearly dependent, is called a (k, t)-set and such a set is said to be maximal if it is not contained in any other (k¹, t)-set with $\text{k}{}^1\text{> k}$. The number of points in a maximal (k, t)-set with the largest k is denoted by m_t(t + r, s). Our purpose in the paper is to investigate the conditions under which two or more points can be adjoined to the basic set of E_i, i = 1, 2, …, t + r, where E_i is a point with one in i-th position and zeros elsewhere. The problem has several applications in the theory of fractionally replicated designs and information theory.     

Positive periodic solutions for an integrodifferential model of mutualism

Sufficient conditions are obtained for the existence of positive periodic solutions of the following integrodifferential model of mutualism:

where r_i, K_i, α_i, σ_i, i = 1,2 are positive continuous ω-periodic functions, α_i > K_i, i = 1, 2, J_i ϵ C([0, ∞], [0, ∞)), and ∫^∞₀ J_i(s) ds = 1, i = 1, 2.     

The exact density function of the ratio of two dependent linear combinations of chi-square variables

A computable expression is derived for the raw moments of the random variableZ=N/D whereN= ₁ ⁿ m _iX_i+ _n ^+1s m _iX_i,D= _n ^+1s l _iX_i+ _s ^+1r n _iX_i, and theX _i's are independently distributed central chi-square variables. The first four moments are required for approximating the distribution ofZ by means of Pearson curves. The exact density function ofZ is obtained in terms of sums of generalized hypergeometric functions by taking the inverse Mellin transform of theh-th moment of the ratioN/D whereh is a complex number. The casen=1,s=2 andr=3 is discussed in detail and a general technique which applies to any ratio having the structure ofZ is also described. A theoretical example shows that the inverse Mellin transform technique yields the exact density function of a ratio whose density can be obtained by means of the transformation of variables technique. In the second example, the exact density function of a ratio of dependent quardratic forms is evaluated at various points and then compared with simulated values.     

A multiplicative inequality for vertex Folkman numbers

Let G be a graph and a₁,…,a_r be positive integers. The symbol G→(a₁,…,a_r) denotes that in every r-coloring of the vertex set V(G) there exists a monochromatic a_i-clique of color i for some i∈{1,…,r}. The vertex Folkman numbers F(a₁,…,a_r;q)=min{|V(G)|:G→(a₁,…,a_r) and K_q?G} are considered. Let a_i, b_i, c_i, i∈{1,…,r}, s, t be positive integers and c_i=a_ib_i, 1?a_i?s,1?b_i?t. Then we prove that

F(c₁,c₂,…,c_r;st+1)?F(a₁,a₂,…,a_r;s+1)F(b₁,b₂,…,b_r;t+1).