共查询到20条相似文献,搜索用时 62 毫秒
1.
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. 相似文献
2.
M. Zippin 《Israel Journal of Mathematics》1981,39(4):349-358
It is proved that there exists a positive function Φ(∈) defined for sufficiently small ∈ 〉 0 and satisfying limt→0 Φ(∈) =0 such that for any integersn 〉>0, ifQ is a projection ofl
1
n
onto ak-dimensional subspaceE with ‖|Q‖|≦1+∈ then there is an integerh〉=k(1−Φ(∈)) and anh-dimensional subspaceF ofE withd(F,l
1
h
) 〈= 1+Φ (∈) whered(X, Y) denotes the Banach-Mazur distance between the Banach spacesX andY. Moreover, there is a projectionP ofl
1
n
ontoF with ‖|P‖| ≦1+Φ(∈).
Author was partially supported by the N.S.F. Grant MCS 79-03042. 相似文献
3.
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). 相似文献
4.
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. 相似文献
5.
Z. Füredi 《Graphs and Combinatorics》1985,1(1):51-56
Letn≥k≥1 be integers and letf(n, k) be the smallest integer for which the following holds: If ℱ is a family of subsets of ann-setX with |ℱ|<f(n,k) then for everyk-coloring ofX there existA
B ∈ ℱ,A∈B, A⊂B such thatB-A is monochromatic. Here it is proven that for a fixedk there exist constantsc
k
andd
k
such that
and
ask→∞. The proofs of both the lower and the upper bounds use probabilistic methods. 相似文献
6.
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. 相似文献
7.
Dr. Matthias Kriesell 《Combinatorica》2006,26(3):277-314
A non-complete graph G is called an (n,k)-graph if it is n-connected but G—X is not (n−|X|+1)-connected for any X ⊂V (G) with |X|≤k. Mader conjectured that for k≥3 the graph K2k+2−(1−factor) is the unique (2k,k)-graph(up to isomorphism).
Here we prove this conjecture. 相似文献
8.
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. 相似文献
9.
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 相似文献
10.
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.). 相似文献
11.
Zoltán Füredi 《Combinatorica》1981,1(2):155-162
Let ℋ be a family ofr-subsets of a finite setX. SetD(ℋ)=
|{E:x∈E∈ℋ}|, (maximum degree). We say that ℋ is intersecting if for anyH,H′ ∈ ℋ we haveH ∩H′ ≠ 0. In this case, obviously,D(ℋ)≧|ℋ|/r. According to a well-known conjectureD(ℋ)≧|ℋ|/(r−1+1/r). We prove a slightly stronger result. Let ℋ be anr-uniform, intersecting hypergraph. Then either it is a projective plane of orderr−1, consequentlyD(ℋ)=|ℋ|/(r−1+1/r), orD(ℋ)≧|ℋ|/(r−1). This is a corollary to a more general theorem on not necessarily intersecting hypergraphs. 相似文献
12.
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. 相似文献
13.
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. 相似文献
14.
Joel Spencer 《Combinatorica》1981,1(2):203-208
Asuresum is a pair (A, n),A ⊂ {1, ...,n−1}, so that wheneverA is 2-colored some monochromatic set sums ton. A “finite basis” for the suresum (A, n) with |A| ≦c is proven to exist. Forc fixed, it is shown that no suresum (A, n) exist ifn is a sufficiently large prime. Generalizations tor-colorations,r>2, are discussed. 相似文献
15.
A. V. Kostochka 《Combinatorica》1982,2(2):187-192
Letf(n) denote the minimal number of edges of a 3-uniform hypergraphG=(V, E) onn vertices such that for every quadrupleY ⊂V there existsY ⊃e ∈E. Turán conjectured thatf(3k)=k(k−1)(2k−1). We prove that if Turán’s conjecture is correct then there exist at least 2
k−2 non-isomorphic extremal hypergraphs on 3k vertices. 相似文献
16.
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 相似文献
17.
Francesco Mordasini 《manuscripta mathematica》1999,99(4):443-464
Let X be a quasi-projective scheme and ℱ a coherent sheaf of modules over X such that its non-Cohen–Macaulay locus is at most one dimensional. We use and extend the techniques of Brodmann to construct
proper birational morphisms of quasi-projective schemes f:Y→X and Cohen–Macaulay coherent sheaves of modules over Y that are isomorphic to the pull-back of ℱ away from the exceptional locus of f. Certain blow-ups of X at locally complete intersections subschemes which contain non-reduced scheme structures on the non-Cohen–Macaulay locus
of ℱ are the main part of the construction.
Received: 19 February 1998 / Revised version: 28 December 1998 相似文献
18.
Let G be a finite group and H a subgroup of G. We say that: (1) H is τ-quasinormal in G if H permutes with all Sylow subgroups Q of G such that (|Q|, |H|) = 1 and (|H|, |Q
G
|) ≠ 1; (2) H is weakly τ-quasinormal in G if G has a subnormal subgroup T such that HT = G and T ∩ H ≦ H
τG
, where H
τG
is the subgroup generated by all those subgroups of H which are τ-quasinormal in G. Our main result here is the following. Let ℱ be a saturated formation containing all supersoluble groups and let X ≦ E be normal subgroups of a group G such that G/E ∈ ℱ. Suppose that every non-cyclic Sylow subgroup P of X has a subgroup D such that 1 < |D| < |P| and every subgroup H of P with order |H| = |D| and every cyclic subgroup of P with order 4 (if |D| = 2 and P is non-Abelian) not having a supersoluble supplement in G is weakly τ-quasinormal in G. If X is either E or F* (E), then G ∈ ℱ. 相似文献
19.
Michel Talagrand 《Probability Theory and Related Fields》1998,112(4):545-563
Consider 0<α<1 and the Gaussian process Y(t) on ℝ
N
with covariance E(Y(s)Y(t))=|t|2α+|s|2α−|t−s|2α, where |t| is the Euclidean norm of t. Consider independent copies X
1,…,X
d
of Y and␣the process X(t)=(X
1(t),…,X
d
(t)) valued in ℝ
d
. When kN≤␣(k−1)αd, we show that the trajectories of X do not have k-multiple points. If N<αd and kN>(k−1)αd, the set of k-multiple points of the trajectories X is a countable union of sets of finite Hausdorff measure associated with the function ϕ(ɛ)=ɛ
k
N
/α−(
k
−1)
d
(loglog(1/ɛ))
k
. If N=αd, we show that the set of k-multiple points of the trajectories of X is a countable union of sets of finite Hausdorff measure associated with the function ϕ(ɛ)=ɛ
d
(log(1/ɛ) logloglog 1/ɛ)
k
. (This includes the case k=1.)
Received: 20 May 1997 / Revised version: 15 May 1998 相似文献
20.
L. Babai 《Combinatorica》1988,8(1):133-135
LetL be a set ofs nonnegative integers and a family of subsets of ann-element setX. Suppose that for any two distinct membersA,B we have¦A B¦ L. Assuming in addition that, is uniform, i.e. each member of has the same cardinality, a celebrated theorem of D. K. Ray-Chaudhuri and R. M. Wilson asserts that ¦¦ P. Frankl and R. M. Wilson proved that without the uniformity assumption, we have.We give a short proof of this latter result. 相似文献