首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 15 毫秒
1.
A system of setsE 1,E 2, ...,E kX 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  相似文献   

2.
Fix integers n,r?4 and let F denote a family of r-sets of an n-element set. Suppose that for every four distinct A,B,C,DF with |ABCD|?2r, we have ABCD≠∅. We prove that for n sufficiently large, , with equality only if ?FFF≠∅. This is closely related to a problem of Katona and a result of Frankl and Füredi [P. Frankl, Z. Füredi, A new generalization of the Erd?s-Ko-Rado theorem, Combinatorica 3 (3-4) (1983) 341-349], who proved a similar statement for three sets. It has been conjectured by the author [D. Mubayi, Erd?s-Ko-Rado for three sets, J. Combin. Theory Ser. A, 113 (3) (2006) 547-550] that the same result holds for d sets (instead of just four), where d?r, and for all n?dr/(d−1). This exact result is obtained by first proving a stability result, namely that if |F| is close to then F is close to satisfying ?FFF≠∅. The stability theorem is analogous to, and motivated by the fundamental result of Erd?s and Simonovits for graphs.  相似文献   

3.
LetR be anr-element set and ℱ be a Sperner family of its subsets, that is,XY 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.  相似文献   

4.
Peter Frankl 《Combinatorica》1984,4(2-3):141-148
LetX be a finite set ofn elements and ℓ a family ofk-subsets ofX. Suppose that for a given setL of non-negative integers all the pairwise intersections of members of ℓ have cardinality belonging toL. Letm(n, k, L) denote the maximum possible cardinality of ℓ. This function was investigated by many authors, but to determine its exact value or even its correct order of magnitude appears to be hopeless. In this paper we investigate the case |L|=3. We give necessary and sufficient conditions form(n, k, L)=O(n) andm(n, k, L)≧O(n 2), and show that in some casesm(n, k, L)=O(n 3/2), which is quite surprising.  相似文献   

5.
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<jk, 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.
The following problem was answered by a theorem of Kruskal, Katona, and Lindström about 20 years ago: Given a family ofk-element sets ?, |?|=m, at least how many (k-d)-element subsets are contained in the members of ?? This paper deals with the extremal families, e.g., they are completely described for infinitely many values ofm.  相似文献   

7.
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.  相似文献   

8.
Let L k be the graph formed by the lowest three levels of the Boolean lattice B k , i.e.,V(L k )={0, 1,...,k, 12, 13,..., (k–1)k} and 0is connected toi for all 1ik, andij is connected toi andj (1i<jk).It is proved that if a graph G overn vertices has at leastk 3/2 n 3/2 edges, then it contains a copy of L k .Research supported in part by the Hungarian National Science Foundation under Grant No. 1812  相似文献   

9.
Letf(n) denote the minimal number of edges of a 3-uniform hypergraphG=(V, E) onn vertices such that for every quadrupleYV there existsYeE. 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.  相似文献   

10.
We consider the following Turán problem. How many edges can there be in a (q+1)-uniform hypergraph on n vertices that does not contain a copy of the projective geometry PGm(q)? The case q=m=2 (the Fano plane) was recently solved independently and simultaneously by Keevash and Sudakov (The Turán number of the Fano plane, Combinatorica, to appear) and Füredi and Simonovits (Triple systems not containing a Fano configuration, Combin. Probab. Comput., to appear). Here we obtain estimates for general q and m via the de Caen-Füredi method of links combined with the orbit-stabiliser theorem from elementary group theory. In particular, we improve the known upper and lower bounds in the case q=2, m=3.  相似文献   

11.
We shall consider graphs (hypergraphs) without loops and multiple edges. Let ? be a family of so called prohibited graphs and ex (n, ?) denote the maximum number of edges (hyperedges) a graph (hypergraph) onn vertices can have without containing subgraphs from ?. A graph (hyper-graph) will be called supersaturated if it has more edges than ex (n, ?). IfG hasn vertices and ex (n, ?)+k edges (hyperedges), then it always contains prohibited subgraphs. The basic question investigated here is: At least how many copies ofL ε ? must occur in a graphG n onn vertices with ex (n, ?)+k edges (hyperedges)?  相似文献   

12.
This paper contains a proof of the following result: ifn≧(t+1)(k?t?1), then any family ofk-subsets of ann-set with the property that any two of the subsets meet in at leastt points contains at most \(\left( {\begin{array}{*{20}c} {n - t} \\ {k - t} \\ \end{array} } \right)\) subsets. (By a theorem of P. Frankl, this was known whent≧15.) The bound (t+1)(k-t-1) represents the best possible strengthening of the original 1961 theorem of Erdös, Ko, and Rado which reaches the same conclusion under the hypothesisnt+(k?t) \(\left( {\begin{array}{*{20}c} k \\ t \\ \end{array} } \right)^3 \) . Our proof is linear algebraic in nature; it may be considered as an application of Delsarte’s linear programming bound, but somewhat lengthy calculations are required to reach the stated result. (A. Schrijver has previously noticed the relevance of these methods.) Our exposition is self-contained.  相似文献   

13.
A. Blokhuis 《Combinatorica》1990,10(4):393-396
A new, short proof is given of the following theorem of Bollobás: LetA 1,..., Ah andB 1,..., Bh be collections of sets with i ¦A i¦=r,¦Bi¦=s and ¦A iBj¦=Ø if and only ifi=j, thenh( s r+s ). The proof immediately extends to the generalizations of this theorem obtained by Frankl, Alon and others.  相似文献   

14.
For a setA of non-negative numbers, letD(A) (the difference set ofA) be the set of nonnegative differences of elements ofA, and letD k be thek-fold iteration ofD. We show that for everyk, almost every set of non-negative integers containing 0 arises asD k (A) for someA. We also give sufficient conditions for a setA to be the unique setX such that 0X andD k (X)=D k (A). We show that for eachm there is a setA such thatD(X)=D(A) has exactly 2 m solutionsX with 0X.This work was supported by grants DMS 92-02833 and DMS 91-23478 from the National Science Foundation. The first author acknowledges the support of the Hungarian National Science Foundation under grants, OTKA 4269, and OTKA 016389, and the National Security Agency (grant No. MDA904-95-H-1045).Lee A. Rubel died March 25, 1995. He is very much missed by his coauthors.  相似文献   

15.
For a finite nonempty set of integers, each of which is at least two, and an integern 3, the numberf(;n) is defined as the least order of a graph having degree set and girthn. The numberf(;n) is evaluated for several sets and integersn. In particular, it is shown thatf({3, 4}; 5) = 13 andf({3, 4}; 6) = 18.Research of the third author was partially supported by a Faculty Research Fellowship from Western Michigan University.  相似文献   

16.
Let be the 2k-uniform hypergraph obtained by letting P1, . . .,Pr be pairwise disjoint sets of size k and taking as edges all sets PiPj with ij. This can be thought of as the ‘k-expansion’ of the complete graph Kr: each vertex has been replaced with a set of size k. An example of a hypergraph with vertex set V that does not contain can be obtained by partitioning V = V1 ∪V2 and taking as edges all sets of size 2k that intersect each of V1 and V2 in an odd number of elements. Let denote a hypergraph on n vertices obtained by this construction that has as many edges as possible. For n sufficiently large we prove a conjecture of Frankl, which states that any hypergraph on n vertices that contains no has at most as many edges as . Sidorenko has given an upper bound of for the Tur′an density of for any r, and a construction establishing a matching lower bound when r is of the form 2p+1. In this paper we also show that when r=2p+1, any -free hypergraph of density looks approximately like Sidorenko’s construction. On the other hand, when r is not of this form, we show that corresponding constructions do not exist and improve the upper bound on the Turán density of to , where c(r) is a constant depending only on r. The backbone of our arguments is a strategy of first proving approximate structure theorems, and then showing that any imperfections in the structure must lead to a suboptimal configuration. The tools for its realisation draw on extremal graph theory, linear algebra, the Kruskal–Katona theorem and properties of Krawtchouck polynomials. * Research supported in part by NSF grants DMS-0355497, DMS-0106589, and by an Alfred P. Sloan fellowship.  相似文献   

17.
Summary Ak-colouring of a hypergraph is an assignment of no more thank colours to the vertices of the hypergraph in such a way that the coloured hypergraph has no monochromatic edges. In this paper a polymatroid is associated with a hypergraph. It is shown that the number ofk-colourings of the hypergraph is determined by an evaluation of the characteristic polynomial of this polymatroid. Hypergraph colouring is then related to an extension of the critical problem developed by the author. It is shown that, ifq is a prime power, then a hypergraph isq k -colourable if and only if the critical exponent overGF(q) of its associated polymatroid is less than or equal tok.  相似文献   

18.
The first part of this paper deals with families of ordered k-tuples having a common element in different position. A quite general theorem is given and special cases are considered. The second part deals with t families of sets with some intersection properties, and generalizes results by Bollobás, Frankl, Lovász and Füredi to this case.  相似文献   

19.
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 |FF′| ≡ μi (modp) for somei, 1 ≦is, 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.  相似文献   

20.
The present paper continues the work begun by Anstee, Griggs and Sali on small forbidden configurations. We define a matrix to be simple if it is a (0,1)-matrix with no repeated columns. Let F be a k×l (0,1)-matrix (the forbidden configuration). Small refers to the size of k and in this paper k = 3. Assume A is an m×n simple matrix which has no submatrix which is a row and column permutation of F. We define forb(m,F) as the best possible upper bound on n, for such a matrix A, which depends on m and F. We complete the classification for all 3-rowed (0,1)-matrices of forb (m,F) as either Θ(m), Θ(m2) or Θ(m3) (with constants depending on F). * Research is supported in part by NSERC. † Research was done while the second author visited the University of British Columbia supported by NSERC of first author. Research was partially supported by Hungarian National Research Fund (OTKA) numbers T034702 and T037846.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号