Let R = (r1,…, rm) and S = (s1,…, sn) be nonnegative integral vectors, and let (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 (R, S) is a position whose entry is the same for all matrices in (R, S). The interchange graph G(R, S) is the graph where the vertices are the matrices in (R, S) and where two matrices are joined by an edge provided they differ by an interchange. We prove that when 1 ≤ ri ≤ n ? 1 (i = 1,…, m) and 1 ≤ sj ≤ m ? 1 (j = 1,…, n), G(R, S) is prime if and only if (R, S) has no invariant positions. 相似文献
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 S1,… Sm be m subsets of an n-set S with |S1| ? 2 (l = 1, …,m) and |Si ∩ Sj| ? 1 (i ≠ j; i, j = 1, …, m). Suppose further that for some fixed positive integer c each Si 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). 相似文献
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. 相似文献
Let A be an n × n normal matrix over , and Qm, n be the set of strictly increasing integer sequences of length m chosen from 1,…,n. For α, β ? Qm, 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 i1,…, ik, ik+1,…, im, such that α(ij) = β(ij), i = 1,…, k, and {α(ik+1),…, α(im) } ∩ {β(ik+1),…, β(im) } = ?. A new bound for |detA[α|β ]| is obtained in terms of the eigenvalues of A when 2m = n and |α∩β| = 0.Let 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 ρ0(A) ? ρ1(A) ? ··· ? ρm(A). These inequalities have been tested by machine calculations. 相似文献
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(vi)?c(vj)|≥r for every two adjacent vertices vi,vj, |c(ei)?c(ej)|≥s for every two adjacent edges ei,ej, and |c(vi)?c(ej)|≥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(Kn,n) in all cases. 相似文献
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. 相似文献
The main theorem of that paper is the following: let G be a graph of order n, of size at least (n2 - 3n + 6)/2. For any integers k, n1, n2,…,nk such that n = n1 + n2 +. + nk and ni ? 3, there exists a covering of the vertices of G by disjoint cycles (Ci) =l…k with |Ci| = ni, except when n = 6, n1 = 3, n2 = 3, and G is isomorphic to G1, the complement of G1 consisting of a C3 and a stable set of three vertices, or when n = 9, n1 = n2 = n3 = 3, and G is isomorphic to G2, the complement of G2 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 n2 - n + 2. For any integers s, n1, n2,…,ns with ni ? 2 and n = n1 + n2 + ? + ns, there exists a covering of the vertices of G by s disjoint cycles Ci, with |Ci| = 2ni. 相似文献
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 [ai, bi], i = 1, …, n, on [a, b] such that |f(ai) ? f(bi)| > ? for any i = 1, …, n (sup Ø = 0). The following theorem is proved: if {fj} is a pointwise bounded sequence of real functions on the interval [a, b] such that n(?) ≡ lim supj→∞N(?, fj, [a, b]) < ∞ for any ? > 0, then the sequence {fj} 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 {fj} 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. 相似文献
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. 相似文献
Let m and n be positive integers, and let R=(r1,…,rm) and S=(s1,…,sn) be nonnegative integral vectors. We survey the combinational properties of the set of all m × n matrices of 0's and 1's having ri1's in row i andsi 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. 相似文献
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 S1, …, Sn and identifying the vertices in Si to form a single vertex αi for i = 1, …, n. Thus E(F) = E(G) and an edge which joins an element of Si to an element of Sj 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 E1, …, Er. 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(Ei) 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(E1), …, F(Er) are almost regular and F(E1), …, F(Eq) are 2-edge-connected and each vertex ξ of G arises by identification from a prescribed number g(ξ) of vertices of F. 相似文献
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 S1,…, Sn be n subsets of an n-set S. Suppose that |Si| ? 3 (i = 1,…,n) and that |Si ∩ Sj| ? 1 (i ≠ j;i,j = 1,…,n). Suppose further that each Si has nonempty intersection with at least n ? 2 of the other subsets. Then the subsets S1,…,Sn 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). 相似文献
Let {λi}i = 1s (s ≥ 2) be a finite sequence of non-zero real numbers, not all of the same sign and in which not all the ratios are rational. A given sequence of positive integers {ni}i = 1s is said to have property (P) (() respectively) if for any {λi}i = 1s and any real number η, there exists a positive constant σ, depending on {λi}i = 1s and {ni}i = 1s only, so that the inequality |η + Σi = 1sλixini| < (max xi)?σ has infinitely many solutions in positive integers (primes respectively) x1, x2,…, xs. In this paper, we prove the following result: Given a sequence of positive integers {ni}i = 1∞, a necessary and sufficient condition that, for any positive integer j, there exists an integer s, depending on {ni}i = j∞ only, such that {ni}i = jj + s ? 1 has property (P) (or ()), is that Σi = 1∞ni?1 = ∞. These are parallel to some striking results of G. A. Fre?man, E. J. Scourfield and K. Thanigasalam. 相似文献
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. 相似文献
We consider an h-partite version of Dilworth’s theorem with multiple partial orders. Let P be a finite set, and let <1,...,<r be partial orders on P. Let G(P, <1,...,<r) be the graph whose vertices are the elements of P, and x, y ∈ P are joined by an edge if x<iy or y<ix holds for some 1 ≤ i ≤ r. We show that if the edge density of G(P, <1, ... , <r) is strictly larger than 1 ? 1/(2h ? 2)r, then P contains h disjoint sets A1, ... , Ah such that A1 <j... <jAh holds for some 1 ≤ j ≤ r, and |A1| = ... = |Ah| = Ω(|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 A1, ... , Ah such that the elements of Ai are incomparable with the elements of Aj for 1 ≤ i < j ≤ h, and |A1| = ... = |Ah| = |P|1?o(1). Finally, we prove that if the edge density of the complement of G(P, <1, <2) is α, then there are disjoint sets A, B ? P such that any element of A is incomparable with any element of B in both <1 and <2, and |A| = |B| > n1?γ(α), where γ(α) → 0 as α → 1. We provide a few applications of these results in combinatorial geometry, as well. 相似文献
Let Rij 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 =[Fij], i,j=1,…, n, such that Fij=Rij 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 Rij 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. 相似文献
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 + ∞. 相似文献
Denote by CA 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 Rn(f) (Rn(f)A) the best uniform approximation of a function f ∈ CA on the circle |z| = 1 (in the disk |z| ≤ 1) by the set ?n. The following equality is proved for any n ≥ 1: sup{Rn(f)A/Rn(f): f ∈ CA ? ?n} = 2. We also consider a similar problem of comparing the best approximations of functions in CA by polynomials and trigonometric polynomials. 相似文献
One presentation of the alternating groupAn hasn?2 generatorss1,…,sn?2 and relationss13=si2=(s1?1si)3=(sjsk)2=1, wherei>1 and |j?k|>1. Against this backdrop, a presentation of the alternating semigroupAnc )An is introduced: It hasn?1 generatorss1,…,Sn?2,e, theAn-relations (above), and relationse2=e, (es1)4, (esj)2=(esj)4,esi=sis1-1es1, wherej>1 andi≥1. 相似文献