Prime interchange graphs of classes of matrices of zeros and ones

Let R = (r₁,…, r_m) and S = (s₁,…, s_n) be nonnegative integral vectors, and let $\text{U}$(R, S) denote the class of all m × n matrices of 0's and 1's having row sum vector R and column sum vector S. An invariant position of $\text{U}$(R, S) is a position whose entry is the same for all matrices in $\text{U}$(R, S). The interchange graph G(R, S) is the graph where the vertices are the matrices in $\text{U}$(R, S) and where two matrices are joined by an edge provided they differ by an interchange. We prove that when 1 ≤ r_i ≤ n ? 1 (i = 1,…, m) and 1 ≤ s_j ≤ m ? 1 (j = 1,…, n), G(R, S) is prime if and only if $\text{U}$(R, S) has no invariant positions.     

Duality between some linear preserver problems. II. Isometries with respect to c-special norms and matrices with fixed singular values

Let $\text{F}{}_{\mathrm{m\times n}}$ (m?n) denote the linear space of all m × n complex or real matrices according as $\text{F}$=$\text{C}$ or $\text{R}$. Let c=(c₁,…,c_m)≠0 be such that c₁???c_m?0. The c-spectral norm of a matrix A?$\text{F}$_m×n is the quantity

$\text{6A6}{}_{\mathrm{c}}\text{∑}\text{i=I}\text{m}\text{c}{}_{\mathrm{i}}\text{σ}{}_{\mathrm{i}}\text{(A)}$

. where σ₁(A)???σ_m(A) are the singular values of A. Let d=(d₁,…,d_m)≠0, where d₁???d_m?0. We consider the linear isometries between the normed spaces $\text{(}\text{F}{}_{\mathrm{m\times }}{}_{\mathrm{n}}\text{,∥·∥}{}_{\mathrm{<mtext>c</mtext>}}\text{)}$ and $\text{(}\text{F}{}_{\mathrm{m\times }}{}_{\mathrm{n}}\text{,∥·∥}{}_{\mathrm{d}}\text{)}$, and prove that they are dual transformations of the linear operators which map $\text{L}$(d) onto $\text{L}$(c), where

$\text{L}\text{(c)= {X?}\text{F}{}_{\mathrm{m\times n}}\text{:X}\text{has singular values}\text{c}{}_1\text{,…,c}{}_{\mathrm{m}}\text{}}$

.     

On constant discrete programming problems

Let H be a subset of the set S_n of all permutations

$\text{1}\text{2}\text{???}\text{n}\text{s(1)}\text{s(2)}\text{???}\text{s(n)}$

C=6c_ij6 a real n?n matrix L_c(s)=c_1s(1)+c_2s(2)+???+c_ns(n) for s ? H. A pair (H, C) is the existencee of reals a₁,b₁,a₂,b₂,…a_n,b_n, for which c_ij=a₁+b_j if (i,j)?D(H), where D(H)={(i,j):(?h?H)(j=h(i))}.For a pair (H,C) the specifity of it is proved in the case, when H is either a special cyclic class of permutations or a special union of cyclic classes. Specific pairs with minimal sets H are in some sense described.     

On a class of relatively prime sequences

For each natural number n, let a₀(n) = n, and if a₀(n),…,a_i(n) have already been defined, let a_i+1(n) > a_i(n) be minimal with (a_i+1(n), a₀(n) … a_i(n)) = 1. Let g(n) be the largest a_i(n) not a prime or the square of a prime. We show that g(n) ～ n and that $\text{g(n) > n + cn}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{log}\text{(n)}$ for some c > 0. The true order of magnitude of g(n) ? n seems to be connected with the fine distribution of prime numbers. We also show that “most” a_i(n) that are not primes or squares of primes are products of two distinct primes. A result of independent interest comes of one of our proofs: For every sufficiently large n there is a prime $\text{p < n}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$ with [$\text{n}\text{p}$] composite.     

A note on the functional law of iterated logarithm for maxima of Gaussian sequences

Let {X_n, n ≥ 1} be a real-valued stationary Gaussian sequence with mean zero and variance one. Let M_n = max{X_t, i ≤ n} and H_n(t) = (M_[nt] ? b_n)a_n^?1 be the maximum resp. the properly normalised maximum process, where $\text{c}{}_{\mathrm{n}}\text{= (2}\text{log}\text{n)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$, $\text{a}{}_{\mathrm{n}}\text{=}\text{(}\text{log log}\text{n)}\text{c}{}_{\mathrm{n}}$ and $\text{b}{}_{\mathrm{n}}\text{= c}{}_{\mathrm{n}}\text{?}\text{1}\text{2}\text{(}\text{log}\text{(4π}\text{log}\text{n))}\text{c}{}_{\mathrm{n}}$. We characterize the almost sure limit functions of (H_n)_n≥3 in the set of non-negative, non-decreasing, right-continuous, real-valued functions on (0, ∞), if r(n) (log n)^3?Δ = O(1) for all Δ > 0 or if r(n) (log n)^2?Δ = O(1) for all Δ > 0 and r(n) convex and fulfills another regularity condition, where r(n) is the correlation function of the Gaussian sequence.     

On solutions of “equations in symmetric groups”

Let x?S_n, the symmetric group on n symbols. Let θ? Aut(S_n) and let the automorphim order of x with respect to θ be defined by

$\text{γθ(x)=}\text{min}\text{{k:x xθ xθ}{}^2\text{? xθ}{}^{\mathrm{k?1}}\text{=1}}$

where xθ is the image of x under θ. Let α_g? Aut(S_n) denote conjugation by the element g?S_n. Let where s and k are positive integers and $\text{a}\text{b}$ denotes a divides b. Further h(s, k : n) ≡ b(1; s, k : n), where 1 denotes the identity automorphim. If g?S_n let c = f(g, s) denote the number of symbols in g which are in cycles of length not dividing the integer s, and let g_s denote the product of all cycles in g whose lengths do not divide s. Then g_s moves c symbols. The main results proved are: (1) recursion: if n ? c + 1 and t = n ? c ? 1 then $\text{b(g; s, 1:n)=∑}{}_{\mathrm{<mtext>i</mtext><mtext>s</mtext>}}\text{b(g; s, 1:n?1)(}{}^{\mathrm{t}}{}_{\mathrm{i?1}}\text{(i?1)!}$ (2) reduction: b(g; s, 1 : c)h(s, 1 : i) = b(g; s, 1 : i + c); (3) distribution: let D(θ, n) ≡ {(k, b) : k?Z⁺ and b = b(θ; 1, k : n) ≠ 0}; then D(θ, m) = D(φ, m) ∨ m ? N = N(θ, φ) iff θ is conjugate to φ; (4) evaluation: the number of cycles in g_s^s of any given length is smaller than the smallest prime dividing s iff b(g_s; s, 1 : c) = 1. If g = (12 … p^m)^t and $\text{sk}\text{p}{}^{\mathrm{m}}$ then $\text{b(g;s,k:p}{}^{\mathrm{m}}\text{) {}{}^0{}_{\mathrm{\pm 1}}\text{(}\text{mod}\text{p)}$.     

On decomposition of r-partite graphs into edge-disjoint hamilton circuits

Let K(n;r) denote the complete r-partite graph K(n, n,…, n). It is shown here that for all even n(r ? 1) ? 2, K(n;r) is the union of $\text{n(r ? 1)}\text{2}$ of its Hamilton circuits which are mutually edge-disjoint, and for all odd n(r ? 1) ? 1, K(n;r) is the union of $\text{(n(r ? 1) ? 1)}\text{2}$ of its Hamilton circuits and a 1-factor, all of which are mutually edge-disjoint.     

On the solutions to x′(t) = A(t) x (t) over all A(t), where P ⩽ A(t) ⩽ Q

Let P_ij and q_ij be positive numbers for i ≠ j, i, j = 1, …, n, and consider the set of matrix differential equations x′(t) = A(t) x(t) over all A(t), where a_ij(t) is piecewise continuous, a_ij(t) = ?∑_{i ≠ j}a_ij(t), and p_ij ? a_ij(t) ? q_ij all t. A solution x is also to satisfy ∑_{i = 1}ⁿx_i(0) = 1. Let C_t denote the set of all solutions, evaluated at t to equations described above. It is shown that $\text{C}{}_{\mathrm{t}}$, the topological closure of C_t, is a compact convex set for each t. Further, the set valued function $\text{C}{}_{\mathrm{t}}$, of t is continuous and $\text{limit}{}_{\mathrm{t\; \to \; \infty }}\text{C}\text{?}{}_{\mathrm{t}}\text{= ∩}\text{C}\text{?}{}_{\mathrm{t}}$.     

Rectangular arrays

In this paper we studied m×n arrays with row sums $\text{nr}\text{(n,m)}$ and column sums $\text{mr}\text{(n,m)}$ where (n,m) denotes the greatest common divisor of m and n. We were able to show that the function H_m,n(r), which enumerates m×n arrays with row sums and column sums $\text{nr}\text{(m,n)}$ and $\text{mr}\text{(n,m)}$ respectively, is a polynomial in r of degree (m?1)(n?1). We found simple formulas to evaluate these polynomials for negative values, ?r, and we show that certain small negative integers are roots of these polynomials. When we considered the generating function G_m,n(y) = Σ_r?0H_m,n(r)y^r, it was found to be rational of degree less than zero. The denominator of G_m,n(y) is of the form (1?y)^(m?1)(n?1)+3, and the coefficients of the numerator are non-negative integers which enjoy a certain symmetric relation.     

The cochromatic index of a graph

We discuss partitions of the edge set of a graph into subsets which are uniform in their internal relationships; i.e., the edges are independent, they are incident with a common vertex (a star), or three edges meet in a triangle. We define the cochromatic index z′(G) of G to be the minimum number of subsets into which the edge set of G can be partitioned so that the edges in any subset are either mutually adjacent or independent.Several bounds for z′(G) are discussed. For example, it is shown that δ(G) - 1 ? z′(G)? Δ(G) + 1, with the lower bound being attained only for a complete graph. Here δ(G) and Δ(G) denote the minimum and maximum degrees of G, respectively. The cochromatic index is also found for complete n-partite graphs.Given a graph G define a sequence of graphs G₀, G₁,…, G_k, with G₀=G and

, with k being the first value of i for which G_i is regular. Let φ_i(G) = |V(G) – V(G_i| + Δ (G_i) and setφ(G) = min_0?i?kφ_i(G). We show that φ(G) ? 1 ?z′(G)?φ(G) + 1. We then s that a graph G is of class A, B or C, if z′(G) = φ(G) ? 1, φ(G), orφ(G) + 1, respectively. Examples of graphs of each class are presented; in particular, it is shown that any bipartite graph belongs to class B.Finally, we show that if a, b and c are positive integers with a?b?c + 1 and a?c, then unless a = c = b - 1 = 1, there exists a graph G having δ(G) = a, Δ(G) =c, and z′(G) = b.     

A generalization of the Kruskal-Katona theorem

Let k_n ? k_n?1 ? … ? k₁ be positive integers and let ($\text{i}\text{j}$) denote the coefficient of xⁱ in $\text{Π}\text{r=1}\text{j}\text{(1 + x + x}{}^2\text{+ … + x}{}^{\mathrm{kr}}\text{)}$. For given integers l, m, where 1 ? l ? k_n + k_n?1 + … + k₁ and $\text{1 ? m ? (}\text{n}\text{n}\text{)}$, it is shown that there exist unique integers m(l), m(l ? 1),…, m(t), satisfying certain conditions, for which $\text{m = (}\text{m(l)}\text{l}\text{+ (}\text{m(l?1)}\text{l?1}\text{) + … + (}\text{m(t)}\text{t}\text{)}$. Moreover, any m l-subsets of a multiset with k_i elements of type i, i = 1, 2,…, n, will contain at least $\text{(}\text{m(l)}\text{l?1}\text{) + (}\text{m(l?1)}\text{l?2}\text{) + … + (}\text{m(t)}\text{t?1}$ different (l ? 1)-subsets. This result has been anticipated by Greene and Kleitman, but the formulation there is not completely correct. If k₁ = 1, the numbers ($\text{j}\text{i}$) are binomial coefficients and the result is the Kruskal-Katona theorem.     

Some explicit formulae in simultaneous padé approximation

Using old results on the explicit calculation of determinants, formulae are given for the coefficients of P₀(z) and P₀(z)f_i(z) ? P_i(z), where P_i(z) are polynomials of degree σ ? ρ_i (i=0,1,…,n), P₀(z)f_i(z) ? P_i(z) are power series in which the terms with z^k, 0?k?σ, vanish (i=1,2,…,n), (ρ₀,ρ₁,…,ρ_n) is an (n+1)-tuple of nonnegative integers, σ=ρ₀+ρ₁+?+ρ_n, and {f_i}ⁿ_i=1 is the set of hypergeometric functions {₁F₁(1;c_i;z)}ⁿ_i=1$\text{(c}{}_{\mathrm{i}}\text{?}\text{Z}\text{z.drule;}\text{N}\text{, c}{}_{\mathrm{i}}\text{? c}{}_{\mathrm{j}}\text{?}\text{Z}\text{)}$ or {₂F₀(a_i,1;z)}ⁿ_i=1$\text{(a}{}_{\mathrm{i}}\text{?}\text{Z}\text{?}\text{N}\text{, a}{}_{\mathrm{i}}\text{? a}{}_{\mathrm{j}}\text{?}\text{Z}\text{)}$ under the condition ρ₀?ρ_i ? 1 (i=1,2,…,n).     

A bound for the number of tournaments with specified scores

Let $\text{T}$(R) denote the set of all tournaments with score vector R = (r₁, r₂,…, r_n). R. A. Brualdi and Li Qiao (“Proceedings of the Silver Jubilee Conference in Combinatorics at Waterloo,” in press) conjectured that if R is strong with r₁ ≤ r₂ ≤ … ≤ r_n, then |$\text{T}$(R)| ≥ 2^n?2 with equality if and only if R = (1, 1, 2,…, n ? 3, n ? 2, n ? 2). In this paper their conjecture is proved, and this result is used to establish a lower bound on the cardinality of $\text{T}$(R) for every R.     

Decomposability of symmetric multilinear functions

Let V denote a finite dimensional vector space over a field K of characteristic 0, let T_n(V) denote the vector space whose elements are the K-valued n-linear functions on V, and let S_n(V) denote the subspace of T_n(V) whose members are the fully symmetric members of T_n(V). If $\text{L}$_n denotes the symmetric group on {1,2,…,n} then we define the projection $\text{P}{}_{\mathrm{<mtext>L</mtext>}}\text{: T}{}_{\mathrm{n}}\text{(V) → S}{}_{\mathrm{n}}\text{(V)}$ by the formula , where P_σ : T_n(V) → T_n(V) is defined so that P_σ(A)(y₁,y₂,…,y_n = A(y_σ(1),y_σ(2),…,y_σ(n)) for each A?T_n(V) and y_i?V, 1 ? i ? n. If $\text{x}{}_{\mathrm{i}}\text{? V}{}^1\text{, 1 ? i ? n}$, then x₁?x₂? … ?x_n denotes the member of T_n(V) such that $\text{(x}{}_1\text{?x}{}_2\text{· ? ? ?x}{}_{\mathrm{n}}\text{)(y}{}_1\text{,y}{}_2\text{,…,y}{}_{\mathrm{n}}\text{) = П}{}^{\mathrm{n}}{}_{\mathrm{i=1}}\text{x}{}_{\mathrm{i}}\text{(y}{}_{\mathrm{i}}\text{)}$ for each y₁ ,₂,…,y_n in V, and x₁·x₂… x_n denotes $\text{P}{}_{\mathrm{<mtext>L</mtext>}}\text{(x}{}_1\text{?x}{}_2\text{? … ?x}{}_{\mathrm{n}}\text{)}$. If B? S_n(V) and there exists $\text{x}{}_{\mathrm{i}}\text{? V}{}^1\text{, 1 ? i ? n}$, such that B = x₁·x₂…x_n, then B is said to be decomposable. We present two sets of necessary and sufficient conditions for a member B of S_n(V) to be decomposable. One of these sets is valid for an arbitrary field of characteristic zero, while the other requires that K = R or C.     

Some permutation problems

Put Z_n = {1, 2,…, n} and let π denote an arbitrary permutation of Z_n. Problem I. Let π = (π(1), π(2), …, π(n)). π has an up, down, or fixed point at a according as a < π(a), a > π(a), or a = π(a). Let $\text{A}\text{(r, s, t)}$ be the number of π ∈ Z_n with r ups, s downs, and t fixed points. Problem II. Consider the triple π^?1(a), a, π(a). Let R denote an up and F a down of π and let B(n, r, s) denote the number of π ∈ Z_n with r occurrences of π^?1(a)RaRπ(a) and s occurrences of π^?1(a)FaFπ(a). Generating functions are obtained for each enumerant as well as for a refinement of the second. In each case use is made of the cycle structure of permutations.     

Largest and smallest maximal sets of pairwise disjoint partitions

Let $\text{X}$ be a maximal set of pairwise disjoint partitions of n into t distinct parts. Let M_t(n) (resp. m_t(n)) denote the size of the largest (resp. smallest) such maximal set $\text{X}$. Upper and lower bounds for $\text{M}{}_{\mathrm{t}}\text{(n)}\text{n}$ and $\text{m}{}_{\mathrm{t}}\text{(n)}\text{n}$ are established.     

Extremal non-bipartite regular graphs of girth 4

Let f(r) denote the smallest number of points in a non-bipartite r-regular graph of girth 4. It is known that $\text{f(r) ≥}\text{5r}\text{2}$ and that $\text{f(r) =}\text{5r}\text{2}$ if r is even. It is proved that $\text{f(r) ～}\text{5r}\text{2}$ and exact values for f(r) are provided for odd integers of the form r = 4n ? 1. Tight bounds for f(r) for odd integers of the form r= 4n + 1 are given.     

Universal caterpillars

For a class $\text{C}$ of graphs, denote by u($\text{C}$) the least value of m so that for some graph U on m vertices, every G ? $\text{C}$ occurs as a subgraph of U. In this note we obtain rather sharp bounds on u($\text{C}$) when $\text{C}$ is the class of caterpillars on n vertices, i.e., tree with property that the vertices of degree exceeding one induce a path.