Unavoidable Traces Of Set Systems

Sauer, Shelah, Vapnik and Chervonenkis proved that if a set system on n vertices contains many sets, then the set system has full trace on a large set. Although the restriction on the size of the groundset cannot be lifted, Frankl and Pach found a trace structure that is guaranteed to occur in uniform set systems even if we do not bound the size of the groundset. In this note we shall give three sequences of structures such that every set system consisting of sufficiently many sets contains at least one of these structures with many sets.     

Intersecting sperner families and their convex hulls

Let ℱ be a family of subsets of a finite set ofn elements. The vector (f ₀, ...,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 ₁⊄F ₂ andF ₁∩F ₂≠0 for allF ₁,F ₂teℱ. It is proved that the extreme points of this set inR ⁿ⁺¹ have at most two non-zero components. Dedicated to Paul Erdős on his seventieth birthday     

Weighted Non-Trivial Multiply Intersecting Families

Let n and r be positive integers. Suppose that a family satisfies F₁∩···∩F_r ≠∅ for all F₁, . . .,F_r ∈ and . We prove that there exists ε=ε(r) >0 such that holds for 1/2≤w≤1/2+ε if r≥13.     

Families of finite sets with three intersections

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 ²), and show that in some casesm(n, k, L)=O(n ^3/2), which is quite surprising.     

On The Structure Of Triangle-Free Graphs Of Large Minimum Degree

It is shown that for every ε>0 there exists a constant L such that every triangle-free graph on n vertices with minimum degree at least (1/3+ε)n is homomorphic to a triangle-free graph on at most L vertices. * Research partially supported by KBN grant 2 P03A 016 23.     

Bonds Intersecting Cycles In A Graph

Let G be a k-connected graph G having circumference c ≥ 2k. It is shown that for k ≥ 2, then there is a bond B which intersects every cycle of length c-k + 2 or greater.     

On sperner families in which nok sets have an empty intersection III

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.     

On disjointly representable sets

A system of setsE ₁,E ₂, ...,E _k ⊂X is said to be disjointly representable if there existx ₁,x ₂, ...,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     

Erd?s-Ko-Rado for three sets

Fix integers k?3 and n?3k/2. Let F be a family of k-sets of an n-element set so that whenever A,B,C∈F satisfy |A∪B∪C|?2k, we have A∩B∩C≠∅. We prove that with equality only when ?_F∈FF≠∅. This settles a conjecture of Frankl and Füredi [2], who proved the result for n?k²+3k.     

Proof Of A Conjecture Of Erdős On Triangles In Set-Systems

A triangle is a family of three sets A,B,C such that A∩B, B∩C, C∩A are each nonempty, and . Let be a family of r-element subsets of an n-element set, containing no triangle. Our main result implies that for r ≥ 3 and n ≥ 3r/2, we have This settles a longstanding conjecture of Erdős [7], by improving on earlier results of Bermond, Chvátal, Frankl, and Füredi. We also show that equality holds if and only if consists of all r-element subsets containing a fixed element. Analogous results are obtained for nonuniform families.     

Small Forbidden Configurations IV: The 3 Rowed Case

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), Θ(m²) or Θ(m³) (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.     

Supersaturation For Ramsey-Turán Problems

For an l-graph , the Turán number is the maximum number of edges in an n-vertex l-graph containing no copy of . The limit is known to exist [8]. The Ramsey–Turán density is defined similarly to except that we restrict to only those with independence number o(n). A result of Erdős and Sós [3] states that as long as for every edge E of there is another edge E′of for which |E∩E′|≥2. Therefore a natural question is whether there exists for which . Another variant proposed in [3] requires the stronger condition that every set of vertices of of size at least εn (0<ε<1) has density bounded below by some threshold. By definition, for every . However, even is not known for very many l-graphs when l>2. We prove the existence of a phenomenon similar to supersaturation for Turán problems for hypergraphs. As a consequence, we construct, for each l≥3, infinitely many l-graphs for which . We also prove that the 3-graph with triples 12a, 12b, 12c, 13a, 13b, 13c, 23a, 23b, 23c, abc, satisfies . The existence of a hypergraph satisfying was conjectured by Erdős and Sós [3], proved by Frankl and R?dl [6], and later by Sidorenko [14]. Our short proof is based on different ideas and is simpler than these earlier proofs. * Research supported in part by the National Science Foundation under grants DMS-9970325 and DMS-0400812, and an Alfred P. Sloan Research Fellowship. † Research supported in part by the National Science Foundation under grants DMS-0071261 and DMS-0300529.     

An intersection theorem for four sets

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,D∈F with |A∪B∪C∪D|?2r, we have A∩B∩C∩D≠∅. We prove that for n sufficiently large, , with equality only if _?F∈FF≠∅. 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 _?F∈FF≠∅. The stability theorem is analogous to, and motivated by the fundamental result of Erd?s and Simonovits for graphs.     

Katona’s Intersection Theorem: Four Proofs

It is known from a previous paper [3] that Katonas Intersection Theorem follows from the Complete Intersection Theorem by Ahlswede and Khachatrian via a Comparison Lemma. It also has been proved directly in [3] by the pushing–pulling method of that paper. Here we add a third proof via a new (k,k+1)-shifting technique, whose impact will be exploared elsewhere. The fourth and last of our proofs is a gift from heaven for Gyulas birthday.Presented on the Conference on Hypergraphs held in Budapest June 7–9, 2001 in Honour of Gyula Katona on the occasion of his 60th Birthday.     

On A Hypergraph Turán Problem Of Frankl

Let be the 2k-uniform hypergraph obtained by letting P₁, . . .,P_r be pairwise disjoint sets of size k and taking as edges all sets P_i∪P_j with i ≠ j. This can be thought of as the ‘k-expansion’ of the complete graph K_r: 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 ∪V₂ and taking as edges all sets of size 2k that intersect each of V₁ and V₂ 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 2^p+1. In this paper we also show that when r=2^p+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.     

On point covers of multiple intervals and axis-parallel rectangles

In certain families of hypergraphs the transversal number is bounded by some function of the packing number. In this paper we study hypergraphs related to multiple intervals and axisparallel rectangles, respectively. Essential improvements of former established upper bounds are presented here. We explore the close connection between the two problems at issue.Supported by the Alexander von Humboldt Foundation and the NSF grant No. STC-91-19999Supported by the NSF grant No. CCR-92-00788, the (Hungarian) National Scientific Research Fund (OTKA) grant No. F014919. The author was visiting the Computation and Automation Institute, Budapest while part of this research was done.     

Families of finite sets with minimum shadows

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.     

On the vector space of 0-configurations

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 ⁿ − |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).     

A class of constructions for turán’s (3, 4)-problem

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.     

Numerical solution of the Poisson equation over hypercubes using reduced Chebyshev polynomial bases

We describe how to use new reduced size polynomial approximations for the numerical solution of the Poisson equation over hypercubes. Our method is based on a non-standard Galerkin method which allows test functions which do not verify the boundary conditions. Numerical examples are given in dimensions up to 8 on solutions with different smoothness using the same approximation basis for both situations. A special attention is paid on conditioning problems.