共查询到20条相似文献,搜索用时 31 毫秒
1.
V. I. Mysovskikh 《Journal of Mathematical Sciences》1999,95(2):2111-2115
We consider a lattice of subgroups normalized by the symmetric group Sn in a complete monomial group G = H|Sn, where H is an arbitrary (finite or infinite) group. It is shown that for n3, the subgroup is strongly paranormal in this wreath product for any H. A similar result is obtained for the alternating group An, n4. The property of strong paranormality for D in G means that for any element x G, the commutator identity [[x,D],D]=[x, D] holds. This guarantees a standard arrangement of subgroups of G normalized by D. Bibliography: 17 titles.Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 236, 1997, pp. 111–118. 相似文献
2.
Given a graphG = (V, E), leta
S, S L, be the edge set incidence vectors of its nontrivial connected subgraphs.The extreme points of = {x R
E: asx |V(S)| - |S|, S L} are shown to be integer 0/± 1 and characterized. They are the alternating vectorsb
k, k K, ofG.
WhenG is a tree, the extreme points ofB 0,b
kx 1,k K} are shown to be the connected vectors ofG together with the origin. For the four LP's associated with andA, good algorithms are given and total dual integrality of andA proven.On leave from Swiss Federal Institute of Technology, Zurich. 相似文献
3.
In this paper we study tight lower bounds on the size of a maximum matching in a regular graph. For k ≥3, let G be a connected k-regular graph of order n and let α′(G) be the size of a maximum matching in G. We show that if k is even, then
, while if k is odd, then
. We show that both bounds are tight.
Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal. 相似文献
4.
Hikoe Enomoto 《Graphs and Combinatorics》1986,2(1):37-42
In a paper with the same title [3], we proved Chvátal's conjecture thatk-tough graphs havek-factors if they satisfy trivial necessary conditions. In this paper, we prove the following stronger result: Suppose|V(G)| k + 1,k |V(G)| even, and|S| k w(G – S) – 7/8k ifw(G – S) 2, wherew(G – S) is the number of connected components ofG – S. ThenG has ak-factor. 相似文献
5.
Gerhard Grams 《Geometriae Dedicata》1994,50(1):87-105
In 1972 M. O'Nan proved thatL
n (q),h 3; can be characterized as a doubly-transitive groupG on a finite set , whereG
a has an Abelian normal subgroup acting not semi-regularly on -a. In the Main Theorem we show that a similar statement holds if is infinite. Our result implies O'Nan's theorem.This paper is part of the author's Ph.D. thesis written under supervision of Prof. F. G. Timmesfeld. 相似文献
6.
Denote bymi(G) the number of maximal independent sets ofG. This paper studies the setS(k) of all graphsG withmi(G) = k and without isolated vertices (exceptG K
1) or duplicated vertices. We determineS(1), S(2), andS(3) and prove that |V(G)| 2
k–1
+k – 2 for anyG inS(k) andk 2; consequently,S(k) is finite for anyk.
Supported in part by the National Science Council under grant NSC 83-0208-M009-050 相似文献
7.
Two finite real sequences (a
1,...,a
k
) and (b
1,...,b
k
) are cross-monotone if each is nondecreasing anda
i+1–a
i
b
i+1–b
i
for alli. A sequence (1,...,
n
) of nondecreasing reals is in class CM(k) if it has disjointk-term subsequences that are cross-monotone. The paper shows thatf(k), the smallestn such that every nondecreasing (1,...,
n
) is in CM(k), is bounded between aboutk
2/4 andk
2/2. It also shows thatg(k), the smallestn for which all (1,...,
n
) are in CM(k)and eithera
k
b
1 orb
k
a
1, equalsk(k–1)+2, and thath(k), the smallestn for which all (1,...,
n
) are in CM(k)and eithera
1b
1...a
k
b
k
orb
1a
1...b
k
a
k
, equals 2(k–1)2+2.The results forf andg rely on new theorems for regular patterns in (0, 1)-matrices that are of interest in their own right. An example is: Every upper-triangulark
2×k
2 (0, 1)-matrix has eitherk 1's in consecutive columns, each below its predecessor, ork 0's in consecutive rows, each to the right of its predecessor, and the same conclusion is false whenk
2 is replaced byk
2–1. 相似文献
8.
Ekkehard Krätzel 《Monatshefte für Mathematik》1995,120(2):105-119
There are many results on the distribution of square-full and cube-full numbers. In this article the distribution of these numbers are studied in more detail. Suchk-full numbers (k=2,3) are considered which are at the same time 1-free (1k+2). At first an asymptotic result is given for the numberN
k,1(x) ofk-full and 1-free numbers not exceedingx. Then the distribution of these numbers in short intervals is investigated. We obtain different estimations of the differenceN
k,1(x+h)–Nk,1(x) in the casesk=2, 1=4,5,6,7,18 andk=3, 1=5,6,7, 18. 相似文献
9.
A. D. Korshunov 《Mathematical Notes》1971,9(3):155-160
LetG(n) be the set of all nonoriented graphs with n enumerated points without loops or multiple lines, and let vk(G) be the number of mutually nonisomorphic k-point subgraphs of G G(n). It is proved that at least |G(n)| (1–1/n) graphs G G(n) possess the following properties: a) for any k [6log2n], where c=–c log2c–(1–c)×log2(1–c) and c>1/2, we havev
k(G) > C
n
k
(1–1/n2); b) for any k [cn + 5 log2n] we havev
k(G) = C
n
k
. Hence almost all graphs G G(n) containv(G) 2n pairwise nonisomorphic subgraphs.Translated from Matematicheskie Zametki, Vol. 9, No. 3, pp. 263–273, March, 1971. 相似文献
10.
John S. Caughman IV 《Journal of Algebraic Combinatorics》2002,15(3):223-229
Let denote a bipartite distance-regular graph with diameter D 3 and valency k 3. Suppose 0, 1, ...,
D
is a Q-polynomial ordering of the eigenvalues of . This sequence is known to satisfy the recurrence
i – 1 –
i
+
i + 1 = 0 (0 > i > D), for some real scalar . Let q denote a complex scalar such that q + q
–1 = . Bannai and Ito have conjectured that q is real if the diameter D is sufficiently large.We settle this conjecture in the bipartite case by showing that q is real if the diameter D 4. Moreover, if D = 3, then q is not real if and only if 1 is the second largest eigenvalue and the pair (, k) is one of the following: (1, 3), (1, 4), (1, 5), (1, 6), (2, 4), or (2, 5). We observe that each of these pairs has a unique realization by a known bipartite distance-regular graph of diameter 3. 相似文献
11.
12.
Guangfu Zhao 《应用数学学报(英文版)》1987,3(2):111-121
A graphG is said to be embeddable into a graphH, if there is an isomorphism ofG into a subgraph ofH. It is shown in this paper that every unicycle or tree which is neither a path norK
1,3 embeds in itsn-th iterated line graph forn1 or 2, 3, and that every other connected graph that embeds in itsn-th iterated line graph may be constructed from such an embedded unicycle or tree in a natural way. A special kind of embedding of graph into itsn-th iterated line graph, called incidence embedding, is studied. Moreover, it is shown that for every positive integerk, there exists a graphG such that (G) = , where (G) is the leastn1 for whichG embeds inL
n(G). 相似文献
13.
For an ordered k-decomposition
of a connected graph G and an edge e of G, the
-code of e is the k-tuple
where d(e, G
i) is the distance from e to G
i. A decomposition
is resolving if every two distinct edges of G have distinct
-codes. The minimum k for which G has a resolving k-decomposition is its decomposition dimension dim
d
(G). A resolving decomposition
of G is connected if each G
i is connected for 1 i k. The minimum k for which G has a connected resolving k-decomposition is its connected decomposition number cd(G). Thus 2 dim
d
(G) cd(G) m for every connected graph G of size m 2. All nontrivial connected graphs of size m with connected decomposition number 2 or m have been characterized. We present characterizations for connected graphs of size m with connected decomposition number m – 1 or m – 2. It is shown that each pair s, t of rational numbers with 0 < s t 1, there is a connected graph G of size m such that dim
d
(G)/m = s and cd(G)/m = t. 相似文献
14.
I. Kh. Sabitov 《Journal of Mathematical Sciences》1994,72(4):3237-3241
It is established that if a surface has only one nontrivial independent field of first order infinitesimal bendings, then rigidity of order n 3 implies rigidity of any order m n, in particular, nondeformability that is analytic in parameter. All the considerations are carried out in class C
1.In passing, a new approach to the determination of infinitesimal bendings of higher order is given.
Translated from Ukrainskii Geometricheskii Sbornik, No. 35, pp. 118–124, 1992. 相似文献
15.
Hiroaki Taniguchi 《Geometriae Dedicata》1999,78(2):215-228
Let k and K be commutative fields with dimkK=2n, n1 and char(k)2, 3. If k satisfies one of the following conditions: (1) k is a finite field and k contains a 3-th root of unity, or (2) K is a cyclic extension of k where k is not 3-closed, and k contains a 2a3b-th root of unity, where 6n=2a3bc and c is coprime to 2, 3, then there exists an embedding of the tn-dimensional affine space AG(tn,k) into the t-dimensional affine space AG(t,K), for all t2. 相似文献
16.
Suppose that is a collection of 3-subsets of{1, 2,..., n} which does not contain ak-star (i.e.,k 3-sets any two of which intersect in the same singleton). Fork 3 andn n
0
(k), the collections having largest possible sizes are determined. 相似文献
17.
Let G be an abelian
group of order n. The
critical number c(G) of G is the smallest
s such that the subset sums
set (S) covers all G for eachs ubset
SG\{0} of cardinality |S|s. It has been recently proved that, if
p is the smallest prime
dividing n and
n/p is composite, then
c(G)=|G|/p+p–2, thus establishing a conjecture of
Diderrich.We characterize the critical sets with |S|=|G|/p+p–3 and (S)=G, where p3 is the smallest prime dividing
n, n/p is composite and
n7p2+3p.We also extend a result of Diderrichan d Mann by proving
that, for n67, |S|n/3+2 and S=G
imply (S)=G. Sets of cardinality
for which
(S) =G are also characterized when
n183, the smallest prime
p dividing
n is odd and
n/p is composite. Finally we
obtain a necessary and sufficient condition for the equality
(G)=G
to hold when |S|n/(p+2)+p, where p5, n/p is composite and
n15p2.* Work partially supported by the Spanish Research
Council under grant TIC2000-1017 Work partially supported by the Catalan Research
Council under grant 2000SGR00079 相似文献
18.
Jean-Pierre Roudneff 《Geometriae Dedicata》1987,23(2):221-227
Let p
k denote the number of k-sided faces in an arrangement of n5 lines in the real projective plane. B. Grünbaum has shown that p
41/2n(n–3) and has conjectured that equality can occur only for simple arrangements. We prove this conjecture here. We also show that 4p
4+5p
53n holds for every simple arrangement of n4 lines. This latter result is a strengthening of a theorem of T. O. Strommer. 相似文献
19.
Jean-Marie De Koninck 《Monatshefte für Mathematik》1993,116(1):13-37
Let
and, for each integern such that (n)k, denote byP
k
(n) itsk
th largest prime factor. Further, given a set of primesQ of positive density <1 satisfying a certain regularity condition, defineP(n, Q), as the largest prime divisor ofn belonging toQ, assuming thatP(n,Q)=+ if no such prime factor exists. We provide estimates of
, fork2, and of
. We also study the median value of the functionP(n,Q) and that of the functionP
k
(n) for eachk1. 相似文献
20.
Let X,X
n
;n1 be a sequence of real-valued i.i.d. random variables with E(X)=0. Assume B(u) is positive, strictly increasing and regularly-varying at infinity with index 1/2<1. Set b
n
=B(n),n1. If
and
for some [0,), then it is shown that
and
for every real triangular array (a
n,k
;1kn,n1) and every array of bounded real-valued i.i.d. random variables W,W
n,k
;1kn,n1`` independent of {X,X
n
;n1}, where (W)=(E(W–E(W))2)1/2. An analogous law of the iterated logarithm for the unweighted sums
n
k=1
X
k
;n1} is also given, along with some illustrative examples. 相似文献