共查询到20条相似文献,搜索用时 31 毫秒
1.
Michael Koren 《Israel Journal of Mathematics》1973,15(4):396-403
It is shown that the realizability of the sequences ϕ=(a
1,…,
a
), ψ=(b
1,…,b
n
) and ϕ+ψ is a sufficient condition for the realizability of ϕ+ψ by a graph with a ϕ-factor ifb
i
≦1 fori=1,…,n. The condition is not sufficient in general. A necessary and sufficient condition for the realizability of ϕ+ψ by a graph
with a ϕ-factor is given for the case that ϕ is realizable by a star and isolated vertices. 相似文献
2.
J. B. Shearer 《Combinatorica》1985,5(3):241-245
LetX
1, ...,X
n
be events in a probability space. Let ϱi be the probabilityX
i
occurs. Let ϱ be the probability that none of theX
i
occur. LetG be a graph on [n] so that for 1 ≦i≦n X
i
is independent of ≈X
j
‖(i, j)∉G≈. Letf(d) be the sup of thosex such that if ϱ1, ..., ϱ
n
≦x andG has maximum degree ≦d then ϱ>0. We showf(1)=1/2,f(d)=(d−1)
d−1
d
−d ford≧2. Hence
df(d)=1/e. This answers a question posed by Spencer in [2]. We also find a sharp bound for ϱ in terms of the ϱ
i
andG. 相似文献
3.
A matrixA=(a
ij
) has theEdmonds—Johnson property if, for each choice of integral vectorsd
1,d
2,b
1,b
2, the convex hull of the integral solutions ofd
1≦x≦d
2,b
1≦Ax≦b
2 is obtained by adding the inequalitiescx≦|δ|, wherec is an integral vector andcx≦δ holds for each solution ofd
1≦x≦d
2,b
1≦Ax≦b
2. We characterize the Edmonds—Johnson property for integral matricesA which satisfy
for each (row index)i. A corollary is that ifG is an undirected graph which does not contain any homeomorph ofK
4 in which all triangles ofK
4 have become odd circuits, thenG ist-perfect. This extends results of Boulala, Fonlupt, Sbihi and Uhry.
First author’s research supported by the Netherlands Organization for the Advancement of Pure Research (Z.W.O.). 相似文献
4.
A theorem of Deza asserts that ifH
1, ...,H
m
ares-sets any pair of which intersects in exactlyd elements and ifm ≧s
2 −s+2, then theH
i
form aΔ-system, i.e.
. In other words, every large equidistant (0, 1)-code of constant weight is trivial. We give a (0, +1, −1) analogue of this
theorem. 相似文献
5.
P. D. Seymour 《Combinatorica》1982,2(1):91-97
De Bruijn and Erdős proved that ifA
1, ...,A
k
are distinct subsets of a set of cardinalityn, and |A
i
∩A
j
|≦1 for 1≦i<j ≦k, andk>n, then some two ofA
1, ...,A
k
have empty intersection. We prove a strengthening, that at leastk /n ofA
1, ...,A
k
are pairwise disjoint. This is motivated by a well-known conjecture of Erdőds, Faber and Lovász of which it is a corollary.
Partially supported by N. S. F. grant No. MCS—8103440 相似文献
6.
Theprofile of a hypergraph onn vertices is (f
0, f1, ...,f
n) wheref
i denotes the number ofi-element edges. The extreme points of the set of profiles is determined for certain hypergraph classes. The results contain
many old theorems of extremal set theory as particular cases (Sperner. Erdős—Ko—Rado, Daykin—Frankl—Green—Hilton). 相似文献
7.
Intersection theorems with geometric consequences 总被引:3,自引:0,他引:3
In this paper we prove that ifℱ is a family ofk-subsets of ann-set, μ0, μ1, ..., μs are distinct residues modp (p is a prime) such thatk ≡ μ0 (modp) and forF ≠ F′ ≠ℱ we have |F ∩F′| ≡ μi (modp) for somei, 1 ≦i≦s, then |ℱ|≦(
s
n
).
As a consequence we show that ifR
n
is covered bym sets withm<(1+o(1)) (1.2)
n
then there is one set within which all the distances are realised.
It is left open whether the same conclusion holds for compositep. 相似文献
8.
Arc-disjoint in-trees in directed graphs 总被引:2,自引:0,他引:2
Given a directed graph D = (V,A) with a set of d specified vertices S = {s
1,…, s
d
} ⊆ V and a function f: S → ℕ where ℕ denotes the set of natural numbers, we present a necessary and sufficient condition such that there exist Σ
i=1
d
f(s
i
) arc-disjoint in-trees denoted by T
i,1,T
i,2,…, for every i = 1,…,d such that T
i,1,…, are rooted at s
i
and each T
i,j
spans the vertices from which s
i
is reachable. This generalizes the result of Edmonds [2], i.e., the necessary and sufficient condition that for a directed
graph D=(V,A) with a specified vertex s∈V, there are k arc-disjoint in-trees rooted at s each of which spans V. Furthermore, we extend another characterization of packing in-trees of Edmonds [1] to the one in our case.
Supported by JSPS Research Fellowships for Young Scientists.
Supported by the project New Horizons in Computing, Grand-in-Aid for Scientific Research on Priority Areas, MEXT Japan. 相似文献
9.
David M. Bressoud 《Proceedings Mathematical Sciences》1987,97(1-3):61-66
Given a basic hypergeometric series with numerator parametersa
1,a
2, ...,a
r and denominator parametersb
2, ...,b
r, we say it isalmost poised ifb
i, =a
1
q
δ,i
a
i,δi = 0, 1 or 2, for 2 ≤i ≤r. Identities are given for almost poised series withr = 3 andr = 5 when a1, =q
−2n.
Partially supported by N.S.F. Grant No. DMS-8521580. 相似文献
10.
A system of setsE
1,E
2, ...,E
k ⊂X is said to be disjointly representable if there existx
1,x
2, ...,x
k
teX such thatx
i
teE
j
⇔i=j. Letf(r, k) denote the maximal size of anr-uniform set-system containing nok disjointly representable members. In the first section the exact value off(r, 3) is determined and (asymptotically sharp) bounds onf(r, k),k>3 are established. The last two sections contain some generalizations, in particular we prove an analogue of Sauer’ theorem
[16] for uniform set-systems.
Dedicated to Paul Erdős on his seventieth birthday 相似文献
11.
David Mejzler 《Israel Journal of Mathematics》1987,57(1):1-27
LetX
1, ...,X
n be independent random variables, letF
i be the distribution function ofX
i (1≦i≦n) and letX
1n
≦... ≦X
nn be the corresponding order statistics. We consider the statisticsX
kn, wherek=k(n),k/n → 1 andn−k → ∞. Under some additional restrictions concerning the behaviour of the sequences {a
n>0,b
n,k(n),F
n} we characterize the class of all distribution functionsH such that Prob{(X
kn
−b
n
)/a
n
<x)}→H.
Dedicated to the Memory of N. V. Smirnov (1900–1966) 相似文献
12.
Claude Berge 《Combinatorica》1982,2(3):213-222
Gallai and Milgram have shown that the vertices of a directed graph, with stability number α(G), can be covered by exactly α(G) disjoint paths. However, the various proofs of this result do not imply the existence of a maximum stable setS and of a partition of the vertex-set into paths μ1, μ2, ..., μk such tht |μi ∩S|=1 for alli.
Later, Gallai proved that in a directed graph, the maximum number of vertices in a path is at least equal to the chromatic
number; here again, we do not know if there exists an optimal coloring (S
1,S
2, ...,S
k) and a path μ such that |μ ∩S
i|=1 for alli.
In this paper we show that many directed graphs, like the perfect graphs, have stronger properties: for every maximal stable
setS there exists a partition of the vertex set into paths which meet the stable set in only one point. Also: for every optimal
coloring there exists a path which meets each color class in only one point. This suggests several conjecties similar to the
perfect graph conjecture.
Dedicated to Tibor Gallai on his seventieth birthday 相似文献
13.
Alan J. Hoffman 《Advances in Computational Mathematics》2006,25(1-3):1-6
Assume F={f1,. . .,fn} is a family of nonnegative functions of n−1 nonnegative variables such that, for every matrix A of order n, |aii|>fi (moduli of off-diagonal entries in row i of A) for all i implies A nonsingular. We show that there is a positive vector x, depending only on F, such that for all A=(aij), and all i, fi≥∑j|aij|{xj}/xi. This improves a theorem of Ky Fan, and yields a generalization of a nonsingularity criterion of Gudkov.
Dedicated to Charles A. Micchelli, in celebration of his 60th birthday and our 30 years of friendship 相似文献
14.
Summary LetX
1,X
2, ...,X
r
ber independentn-dimensional random vectors each with a non-singular normal distribution with zero means and positive partial correlations. Suppose thatX
i
=(X
i1
, ...,X
in
) and the random vectorY=(Y
1, ...,Y
n
), their maximum, is defined byY
j
=max{X
ij
:1ir}. LetW be another randomn-vector which is the maximum of another such family of independentn-vectorsZ
1,Z
2, ...,Z
s
. It is then shown in this paper that the distributions of theZ
i
's are simply a rearrangement of those of theZ
j
's (and of course,r=s), whenever their maximaY andW have the same distribution. This problem was initially studied by Anderson and Ghurye [2] in the univariate and bivariate cases and motivated by a supply-demand problem in econometrics. 相似文献
15.
Melvin Hausner 《Combinatorica》1985,5(3):215-225
Ifμ is a positive measure, andA
2, ...,A
n
are measurable sets, the sequencesS
0, ...,S
n
andP
[0], ...,P
[n] are related by the inclusion-exclusion equalities. Inequalities among theS
i
are based on the obviousP
[k]≧0. Letting
=the average average measure of the intersection ofk of the setsA
i
, it is shown that (−1)
k
Δ
k
M
i
≧0 fori+k≦n. The casek=1 yields Fréchet’s inequalities, andk=2 yields Gumbel’s and K. L. Chung’s inequalities. Generalizations are given involvingk-th order divided differences. Using convexity arguments, it is shown that forS
0=1,
whenS
1≧N−1, and
for 1≦k<N≦n andv=0, 1, .... Asymptotic results asn → ∞ are obtained. In particular it is shown that for fixedN,
for all sequencesM
0, ...,M
n
of sufficiently large length if and only if
for 0<t<1. 相似文献
16.
A relative regular sequencea
1, ...,a
r
, with respect to the idealI=(a
1, ...,a
r
) has the property thatI annihilates the Koszul homology associated to each initial subsequence. This note analyzes the concepts of relative regular and proper sequences, two notions situated in a strategic position for studying the arithmetical properties of Blow-up Algebras in the largest context of generalized Cohen-Macaulay rings. 相似文献
17.
Ervin Győri 《Combinatorica》1981,1(3):263-273
It was proved ([5], [6]) that ifG is ann-vertex-connected graph then for any vertex sequencev
1, ...,v
n
≠V(G) and for any sequence of positive integersk
1, ...,k
n
such thatk
1+...+k
n
=|V(G)|, there exists ann-partition ofV(G) such that this partition separates the verticesv
1, ...,v(n), and the class of the partition containingv
i
induces a connected subgraph consisting ofk
i
vertices, fori=1, 2, ...,n. Now fix the integersk
1, ...,k
n
. In this paper we study what can we say about the vertex-connectivity ofG if there exists such a partition ofV(G) for any sequence of verticesv
1, ...,v
n
≠V(G). We find some interesting cases when the existence of such partitions implies then-vertex-connectivity ofG, in the other cases we give sharp lower bounds for the vertex-connectivity ofG. 相似文献
18.
A. J. W. Hilton 《Combinatorica》1982,2(1):37-51
A variety of results on edge-colourings are proved, the main one being the following: ifG is a graph without loops or multiple edges and with maximum degree Δ=Δ(G), and if ν is a given integer 1≦ν≦Δ(G), thenG can be given a proper edge-colouring with the coloursc
1, ...,c
Δ+1 with the additional property that any edge colouredc
μ with μ≧ν is on a vertex which has on it edges coloured with at least ν − 1 ofc
1, ...,c
v
. 相似文献
19.
《Quaestiones Mathematicae》2013,36(2):233-236
AbstractA connected graph G of order p =|V| and sise q =| E | is said to be (ai, bi)-destructible (with respect to Ei and Vi say) if ai,bi are integral factors of p and an ai-set of edges Ei exists whose removal from G results in exactly bi components isomorphic to Ki i.e. whose removal from G isolates the vertices in a bi-set Vi. The operation of removing Ei and Vi from G results in either Ø or a subgraph H of G and is called an (ai , bi)-destruction of G. In this paper we show that the only graphs whose every (ai,bi)- destruction results in a complete subgraph are K (1,2) and K4—e, where e ε K4. 相似文献
20.
Let ℱ be a family of subsets of a finite set ofn elements. The vector (f
0, ...,f
n
) is called the profile of ℱ wheref
i
denotes the number ofi-element subsets in ℱ. Take the set of profiles of all families ℱ satisfyingF
1⊄F
2 andF
1∩F
2≠0 for allF
1,F
2teℱ. It is proved that the extreme points of this set inR
n+1 have at most two non-zero components.
Dedicated to Paul Erdős on his seventieth birthday 相似文献