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.     

A Fisher type inequality

In this paper we study subsets of a finite set that intersect each other in at most one element. Each subset intersects most of the other subsets in exactly one element. The following theorem is one of our main conclusions. Let S₁,… S_m be m subsets of an n-set S with |S₁| ? 2 (l = 1, …,m) and |S_i ∩ S_j| ? 1 (i ≠ j; i, j = 1, …, m). Suppose further that for some fixed positive integer c each S_i has non-empty intersection with at least m ? c of the remaining subsets. Then there is a least positive integer M(c) depending only on c such that either m ? n or m ? M(c).     

On the adjacent vertex-distinguishing equitable edge coloring of graphs

Let G(V, E) be a graph. A k-adjacent vertex-distinguishing equatable edge coloring of G, k-AVEEC for short, is a proper edge coloring f if (1) C(u)≠C(v) for uv ∈ E(G), where C(u) = {f(uv)|uv ∈ E}, and (2) for any i, j = 1, 2,… k, we have ||Ei| |Ej|| ≤ 1, where Ei = {e|e ∈ E(G) and f(e) = i}. χáve (G) = min{k| there exists a k-AVEEC of G} is called the adjacent vertex-distinguishing equitable edge chromatic number of G. In this paper, we obtain the χáve (G) of some special graphs and present a conjecture.     

A subdeterminant inequality for normal matrices

Let A be an n × n normal matrix over $\text{C}$, and Q_m, _n be the set of strictly increasing integer sequences of length m chosen from 1,…,n. For α, β ? Q_m, _n denote by A[α|β] the submatrix obtained from A by using rows numbered α and columns numbered β. For k ? {0, 1,…, m} we write |α∩β| = k if there exists a rearrangement of 1,…, m, say i₁,…, i_k, i_k+1,…, i_m, such that α(i_j) = β(i_j), i = 1,…, k, and {α(i_k+1),…, α(i_m) } ∩ {β(i_k+1),…, β(i_m) } = ?. A new bound for |detA[α|β ]| is obtained in terms of the eigenvalues of A when 2m = n and |α∩β| = 0.Let $\text{U}$_n be the group of n × n unitary matrices. Define the nonnegative number

where | α ∩ β| = k. It is proved that

Let A be semidefinite hermitian. We conjecture that ρ₀(A) ? ρ₁(A) ? ··· ? ρ_m(A). These inequalities have been tested by machine calculations.     

[r,s,t]-Coloring of K n,n

Let G=(V(G),E(G)) be a simple graph. Given non-negative integers r,s, and t, an [r,s,t]-coloring of G is a mapping c from V(G)∪E(G) to the color set {0,1,…,k?1} such that |c(v _i )?c(v _j )|≥r for every two adjacent vertices v _i ,v _j , |c(e _i )?c(e _j )|≥s for every two adjacent edges e _i ,e _j , and |c(v _i )?c(e _j )|≥t for all pairs of incident vertices and edges, respectively. The [r,s,t]-chromatic number χ _r,s,t (G) of G is defined to be the minimum k such that G admits an [r,s,t]-coloring. We determine χ _r,s,t (K _n,n ) in all cases.     

On systems of finite sets with constraints on their unions and intersections

Let F be a family of subsets of an n-element set. F is said to be of type (n, r, s) if A ∈ F, B ∈ F implies that |A ∪ B| ? n ? r, and |A ∩ B| ? s. Let f(n, r, s) = max {|F| : F is of type (n, r, s)}. We prove that f(n, r, s) ? f(n ? 1, r ? 1, s) + f(n ? 1, r + 1, s) if r > 0, n > s. And this result is used to give simple and unified proofs of Katona's and Frankl's results on f(n, r, s) when s = 0 and s = 1.     

Covering the vertices of a graph by cycles of prescribed length

The main theorem of that paper is the following: let G be a graph of order n, of size at least (n² - 3n + 6)/2. For any integers k, n₁, n₂,…,n_k such that n = n₁ + n₂ +. + n_k and n_i ? 3, there exists a covering of the vertices of G by disjoint cycles (C_i) =l…k with |C_i| = ni, except when n = 6, n₁ = 3, n₂ = 3, and G is isomorphic to G₁, the complement of G₁ consisting of a C₃ and a stable set of three vertices, or when n = 9, n₁ = n₂ = n₃ = 3, and G is isomorphic to G₂, the complement of G₂ consisting of a complete graph on four vertices and a stable set of five vertices. We prove an analogous theorem for bipartite graphs: let G be a bipartite balanced graph of order 2n, of size at least n² - n + 2. For any integers s, n₁, n₂,…,n_s with n_i ? 2 and n = n₁ + n₂ + ? + n_s, there exists a covering of the vertices of G by s disjoint cycles C_i, with |C_i| = 2n_i.     

Mutually orthogonal graph squares

A decomposition ??={G₁, G₂,…,G_s} of a graph G is a partition of the edge set of G into edge‐disjoint subgraphs G₁, G₂,…,G_s. If G_i?H for all i∈{1, 2, …, s}, then ?? is a decomposition of G by H. Two decompositions ??={G₁, G₂, …, G_n} and ?={F₁, F₂,…,F_n} of the complete bipartite graph K_n,n are orthogonal if |E(G_i)∩E(F_j)|=1 for all i,j∈{1, 2, …, n}. A set of decompositions {??₁, ??₂, …, ??_k} of K_{n, n} is a set of k mutually orthogonal graph squares (MOGS) if ??_i and ??_j are orthogonal for all i, j∈{1, 2, …, k} and i≠j. For any bipartite graph G with n edges, N(n, G) denotes the maximum number k in a largest possible set {??₁, ??₂, …, ??_k} of MOGS of K_{n, n} by G. El‐Shanawany conjectured that if p is a prime number, then N(p, P_{p+ 1})=p, where P_{p+ 1} is the path on p+ 1 vertices. In this article, we prove this conjecture. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 369–373, 2009     

Selection principle for pointwise bounded sequences of functions

For a number ? > 0 and a real function f on an interval [a, b], denote by N(?, f, [a, b]) the least upper bound of the set of indices n for which there is a family of disjoint intervals [a _i , b _i ], i = 1, …, n, on [a, b] such that |f(a _i ) ? f(b _i )| > ? for any i = 1, …, n (sup Ø = 0). The following theorem is proved: if {f _j } is a pointwise bounded sequence of real functions on the interval [a, b] such that n(?) ≡ lim sup _j→∞ N(?, f _j , [a, b]) < ∞ for any ? > 0, then the sequence {f _j } contains a subsequence which converges, everywhere on [a, b], to some function f such that N(?, f, [a, b]) ≤ n(?) for any ? > 0. It is proved that the main condition in this theorem related to the upper limit is necessary for any uniformly convergent sequence {f _j } and is “almost” necessary for any everywhere convergent sequence of measurable functions, and many pointwise selection principles generalizing Helly’s classical theorem are consequences of our theorem. Examples are presented which illustrate the sharpness of the theorem.     

Multiplicative infinite loop space theory

Let G be a finitely presented group given by its pre-abelian presentation <X1,…,Xm; Xe11ζ1,…,Xemmζ,ζm+1,…>, where ei≥0 for i = 1,…, m and ζj?G′ for j≥1. Let N be the subgroup of G generated by the normal subgroups [xeii, G] for i = 1,…, m. Then Dn+2(G)≡γn+2(G) (modNG′) for all n≥0, where G” is the second commutator subgroup of G,γn+2(G) is the (n+2)th term of the lower central series of G and Dn+2(G) = G∩(1+△n+2(G)) is the (n+2)th dimension subgroup of G.     

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.     

Amalgamations of almost regular edge-colourings of simple graphs

A finite graph F is a detachment of a finite graph G if G can be obtained from F by partitioning V(F) into disjoint sets S₁, …, S_n and identifying the vertices in S_i to form a single vertex α_i for i = 1, …, n. Thus E(F) = E(G) and an edge which joins an element of S_i to an element of S_j in F will join α_i to α_j in G. If L is a subset of E(G) then G(L) denotes the subgraph of G such that V(G(L)) = V(G), E(G(L)) = L. We call a graph almost regular if there is an integer d such that every vertex has valency d or d + 1. Suppose that E(G) is partitioned into disjoint sets E₁, …, E_r. Hilton [3] found necessary and sufficient conditions for the existence of a detachment F of G such that F is a complete graph with 2r + 1 vertices and F(E_i) is a Hamilton circuit of F for i = 1, …, r. We give a new proof of Hilton's theorem, which also yields a generalisation. Specifically, for any q ∈ {0, 1, …, r}, we find necessary and sufficient conditions for G to have a detachment F without loops or multiple edges such that F(E₁), …, F(E_r) are almost regular and F(E₁), …, F(E_q) are 2-edge-connected and each vertex ξ of G arises by identification from a prescribed number g(ξ) of vertices of F.     

Subsets of a finite set that intersect each other in at most one element

In this paper we study de Bruijn-Erdös type theorems that deal with the foundations of finite geometries. The following theorem is one of our main conclusions. Let S₁,…, S_n be n subsets of an n-set S. Suppose that |S_i| ? 3 (i = 1,…,n) and that |S_i ∩ S_j| ? 1 (i ≠ j;i,j = 1,…,n). Suppose further that each S_i has nonempty intersection with at least n ? 2 of the other subsets. Then the subsets S₁,…,S_n of S are one of the following configurations. (1) They are a finite projective plane. (2) They are a symmetric group divisible design and each subset has nonempty intersection with exactly n ? 2 of the other subsets. (3) We have n = 9 or n = 10 and in each case there exists a unique configuration that does not satisfy (1) or (2).     

Diophantine inequalities with mixed powers

Let {λ_i}_{i = 1}^s (s ≥ 2) be a finite sequence of non-zero real numbers, not all of the same sign and in which not all the ratios $\text{λ}{}_{\mathrm{i}}\text{λ}{}_{\mathrm{j}}$ are rational. A given sequence of positive integers {n_i}_{i = 1}^s is said to have property (P) (($\text{P}{}^1$) respectively) if for any {λ_i}_{i = 1}^s and any real number η, there exists a positive constant σ, depending on {λ_i}_{i = 1}^s and {n_i}_{i = 1}^s only, so that the inequality |η + Σ_{i = 1}^sλ_ix_iⁿⁱ| < (max x_i)^?σ has infinitely many solutions in positive integers (primes respectively) x₁, x₂,…, x_s. In this paper, we prove the following result: Given a sequence of positive integers {n_i}_{i = 1}^∞, a necessary and sufficient condition that, for any positive integer j, there exists an integer s, depending on {n_i}_{i = j}^∞ only, such that {n_i}_{i = j}^{j + s ? 1} has property (P) (or ($\text{P}{}^1$)), is that Σ_{i = 1}^∞n_i^?1 = ∞. These are parallel to some striking results of G. A. Fre?man, E. J. Scourfield and K. Thanigasalam.     

A class of antimagic join graphs

A labeling f of a graph G is a bijection from its edge set E(G) to the set {1, 2, . . . , |E(G)|}, which is antimagic if for any distinct vertices x and y, the sum of the labels on edges incident to x is different from the sum of the labels on edges incident to y. A graph G is antimagic if G has an f which is antimagic. Hartsfield and Ringel conjectured in 1990 that every connected graph other than K 2 is antimagic. In this paper, we show that if G 1 is an n-vertex graph with minimum degree at least r, and G 2 is an m-vertex graph with maximum degree at most 2r-1 (m ≥ n), then G1 ∨ G2 is antimagic.     

Turán-Type Results for Complete <Emphasis Type="Italic">h</Emphasis>-Partite Graphs in Comparability and Incomparability Graphs

We consider an h-partite version of Dilworth’s theorem with multiple partial orders. Let P be a finite set, and let <₁,...,< _r be partial orders on P. Let G(P, <₁,...,< _r ) be the graph whose vertices are the elements of P, and x, y ∈ P are joined by an edge if x< _i y or y< _i x holds for some 1 ≤ i ≤ r. We show that if the edge density of G(P, <₁, ... , < _r ) is strictly larger than 1 ? 1/(2h ? 2) ^r , then P contains h disjoint sets A ₁, ... , A _h such that A ₁ < _j ... < _j A _h holds for some 1 ≤ j ≤ r, and |A ₁| = ... = |A _h | = Ω(|P|). Also, we show that if the complement of G(P, <) has edge density strictly larger than 1 ? 1/(3h ? 3), then P contains h disjoint sets A ₁, ... , A _h such that the elements of A _i are incomparable with the elements of A _j for 1 ≤ i < j ≤ h, and |A ₁| = ... = |A _h | = |P|^1?o(1). Finally, we prove that if the edge density of the complement of G(P, <₁, <₂) is α, then there are disjoint sets A, B ? P such that any element of A is incomparable with any element of B in both <₁ and <₂, and |A| = |B| > n ^1?γ(α), where γ(α) → 0 as α → 1. We provide a few applications of these results in combinatorial geometry, as well.     

Extensions of band matrices with band inverses

Let R_ij be a given set of μ_i× μ_j matrices for i, j=1,…, n and |i?j| ?m, where 0?m?n?1. Necessary and sufficient conditions are established for the existence and uniqueness of an invertible block matrix =[F_ij], i,j=1,…, n, such that F_ij=R_ij for |i?j|?m, F admits either a left or right block triangular factorization, and (F^?1)_ij=0 for |i?j|>m. The well-known conditions for an invertible block matrix to admit a block triangular factorization emerge for the particular choice m=n?1. The special case in which the given R_ij are positive definite (in an appropriate sense) is explored in detail, and an inequality which corresponds to Burg's maximal entropy inequality in the theory of covariance extension is deduced. The block Toeplitz case is also studied.     

On the Super Edge-Magic Deficiency of Graphs

A (p, q) graph G is edge-magic if there exists a bijective function f: V(G) ∪ E(G) → {1,2,…,p + q} such that f(u) + f(v) + f(uv) = k is a constant, called the valence of f, for any edge uv of G. Moreover, G is said to be super edge-magic if f(V(G)) = {1,2,…,p}. The question studied in this paper is for which graphs is it possible to add a finite number of isolated vertices so that the resulting graph is super edge-magic? If it is possible for a given graph G, then we say that the minimum such number of isolated vertices is the super edge-magic deficiency, μ_s(G) of G; otherwise we define it to be + ∞.     

Comparison of the best uniform approximations of analytic functions in the disk and on its boundary

Denote by C _A the set of functions that are analytic in the disk |z| < 1 and continuous on its closure |z| ≤ 1; let ? _n , n = 0, 1, 2, ..., be the set of rational functions of degree at most n. Denote by R _n (f) (R _n (f) _A ) the best uniform approximation of a function f ∈ C _A on the circle |z| = 1 (in the disk |z| ≤ 1) by the set ? _n . The following equality is proved for any n ≥ 1: sup{R _n (f) _A /R _n (f): f ∈ C _A ? ? _n } = 2. We also consider a similar problem of comparing the best approximations of functions in C _A by polynomials and trigonometric polynomials.     

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.