共查询到20条相似文献,搜索用时 78 毫秒
1.
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 相似文献
2.
Roy Meshulam 《Graphs and Combinatorics》1992,8(3):287-289
Let ℱ be a family ofn−k-dimensional faces of the discrete cube {0,1}
n
such that for allF ε ℱ, F ⊄ ∪ { F′: F ≠ F′ ∈ ℱ}. It is shown that ifn≥n
0
(k) then |ℱ| ≤
. This was conjectured by Aharoni and Holzman and is the casem=2 of a more general result on faces of {0,...,m−1}n. 相似文献
3.
LetΓ be a class of countable graphs, and let ℱ(Γ) denote the class of all countable graphs that do not contain any subgraph isomorphic to a member ofΓ. Furthermore, letTΓ andHΓ denote the class of all subdivisions of graphs inΓ and the class of all graphs contracting to a member ofΓ, respectively. As the main result of this paper it is decided which of the classes ℱ(TK
n
) and ℱ(HK
n
),n≦ℵ0, contain a universal element. In fact, for ℱ(TK
4)=ℱ(HK
4) a strongly universal graph is constructed, whereas for 5≦n≦ℵ0 the classes ℱ(TK
n
) and ℱ(HK
n
) have no universal elements.
Dedicated to Klaus Wagner on his 75th birthday 相似文献
4.
It is shown that ifX is ans-distance subset inR
d
, then |X|≦(
s
d+s
).
Supported in part by NSF grant MCS7903128 A01.
Supported in part by NSF grant MCS. 相似文献
5.
H. -D. O. F. Gronau 《Combinatorica》1982,2(1):25-36
LetR be anr-element set and ℱ be a Sperner family of its subsets, that is,X ⊈Y for all differentX, Y ∈ ℱ. The maximum cardinality of ℱ is determined under the conditions 1)c≦|X|≦d for allX ∈ ℱ, (c andd are fixed integers) and 2) nok sets (k≧4, fixed integer) in ℱ have an empty intersection. The result is mainly based on a theorem which is proved by induction,
simultaneously with a theorem of Frankl. 相似文献
6.
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 相似文献
7.
LetF be a collection ofk-element sets with the property that the intersection of no two should be included in a third. We show that such a collection
of maximum size satisfies .2715k+o(k)≦≦log2 |F|≦.7549k+o(k) settling a question raised by Erdős. The lower bound is probabilistic, the upper bound is deduced via an entropy argument.
Some open questions are posed.
This research has been supported in part by the Office of Naval Research under Contract N00014-76-C-0366.
Supported in part by a NSF postdoctoral Fellowship. 相似文献
8.
A family ℱ of sets has propertyB if there exists a setS such thatS∩F≠0 andS⊄F for everyF∈ℱ. ℱ has propertyB(s) if there exists a setS such that 0<|F∩S|<s for everyF∈ℱ. Denote bym(n) (respectivelym(n, s)) the size of a smallest family ofn-element sets not having propertyB (respectivelyB(s)). P. Erdős has asked whetherm(n, s)≧m (s) for alln≧s. We show that, in general, this inequality does not hold. 相似文献
9.
Richard Mansfield 《Israel Journal of Mathematics》1981,39(3):265-272
The compactness theorem for the predicate calculus is used to prove that ifp is a prime ands is a positive integer withs≦11 or 2
s−1≦p and X is a set of distinct residues modp, there are at least 2s−3 distinct residuesx+y withx≠y andx, y∈X. 相似文献
10.
If a setX ⊂E
n has non-emptyk-dimensional interior, or if some point isk-dimensional surrounded, then the classic theorem of E. Steinitz may be extended. For example ifX ⊂E
n has int
k
X ≠ 0, (0 ≦k≦n) and ifp ɛ int conX, thenp ɛ int conY for someY ⊂X with cardY≦2n−k+1. 相似文献
11.
Peter Frankl 《Combinatorica》1983,3(2):193-199
Letn, k, t be integers,n>k>t≧0, and letm(n, k, t) denote the maximum number of sets, in a family ofk-subsets of ann-set, no two of which intersect in exactlyt elements. The problem of determiningm(n, k, t) was raised by Erdős in 1975. In the present paper we prove that ifk≦2t+1 andk−t is a prime, thenm(n, k, t)≦(
t
n
)(
k
2k-t-1
)/(
t
2k-t-1
). Moreover, equality holds if and only if an (n, 2k−t−1,t)-Steiner system exists. The proof uses a linear algebraic approach. 相似文献
12.
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. 相似文献
13.
DuBeiliang 《高校应用数学学报(英文版)》2001,16(2):107-110
Abstract. In this paper, it is shown that a sufficient condition for the existence of a 相似文献
14.
The grid graph is the graph on [k]
n
={0,...,k–1}
n
in whichx=(x
i
)
1
n
is joined toy=(y
i
)
1
n
if for somei we have |x
i
–y
i
|=1 andx
j
=y
j
for allji. In this paper we give a lower bound for the number of edges between a subset of [k]
n
of given cardinality and its complement. The bound we obtain is essentially best possible. In particular, we show that ifA[k]
n
satisfiesk
n
/4|A|3k
n
/4 then there are at leastk
n–1
edges betweenA and its complement.Our result is apparently the first example of an isoperimetric inequality for which the extremal sets do not form a nested family.We also give a best possible upper bound for the number of edges spanned by a subset of [k]
n
of given cardinality. In particular, forr=1,...,k we show that ifA[k]
n
satisfies |A|r
n
then the subgraph of [k]
n
induced byA has average degree at most 2n(1–1/r).Research partially supported by NSF Grant DMS-8806097 相似文献
15.
Let α be a rational-valued set-function on then-element sexX i.e. α(B) εQ for everyB ⫅X. We say that α defines a 0-configuration with respect toA⫅2
x
if for everyA εA we have
α(B)=0. The 0-configurations form a vector space of dimension 2
n
− |A| (Theorem 1). Let 0 ≦t<k ≦n and letA={A ⫅X: |A| ≦t}. We show that in this case the 0-configurations satisfying α(B)=0 for |B|>k form a vector space of dimension
, we exhibit a basis for this space (Theorem 4). Also a result of Frankl, Wilson [3] is strengthened (Theorem 6). 相似文献
16.
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 相似文献
17.
Z. Füredi 《Combinatorica》1985,5(1):27-31
LetX be a finite set ofn elements and ℱ a family of 4a+5-element subsets,a≧6. Suppose that all the pairwise intersections of members of ℱ have cardinality 0,a or 2a+1. We show thatc
1
n
4/3<max |F|<c
2
n
4/3 for some positivec
i’s. This answers a question of P. Frankl. 相似文献
18.
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.). 相似文献
19.
A. Arias 《Israel Journal of Mathematics》1988,63(2):139-148
We show that for 1 ≦p < ∞,p ≠ 2, ifɛ > 0 is small enough andX ≦L
p is the span ofn independent Rademacher functions orn independent Gaussian random variables, then any superspaceY ofX satisfyingd(Y,L
p
m
) ≦ 1 +ɛ has dimension larger thanr
n, wherer =r(ɛ, p) > 1.
This forms part of the author’s doctoral dissertation prepared at Texas A&M University under the direction of Professor W.
B. Johnson.
Supported in part by NSF DMS-85 00764. 相似文献
20.
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. 相似文献