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.     

Small maximally disjoint union-free families

A family F of k-subsets of an n-set X is disjoint union-free (DUF) if all disjoint pairs of elements of F have distinct unions; that is, if for every A,B,C,D∈F, A∩B=C∩D=∅ and A∪B=C∪D implies {A,B}={C,D}. DUF families of maximum size have been studied by Erdös and Füredi. Let F be DUF with the property that F∪{E} is not DUF for any k-subset E of X not already in F. Then F is maximally DUF. We introduce the problem of finding the minimum size of maximally DUF families and provide bounds on this quantity for k=3.     

Hypergraphs do not jump

The number α, 0≦α≦1, is a jump forr if for any positive ε and any integerm,m≧r, anyr-uniform hypergraph withn>n _o (ε,m) vertices and at least (α+ε) \(\left( {\begin{array}{*{20}c} n \\ r \\ \end{array} } \right)\) edges contains a subgraph withm vertices and at least (α+c) \(\left( {\begin{array}{*{20}c} m \\ r \\ \end{array} } \right)\) edges, wherec=c(α) does not depend on ε andm. It follows from a theorem of Erdös, Stone and Simonovits that forr=2 every α is a jump. Erdös asked whether the same is true forr≧3. He offered $ 1000 for answering this question. In this paper we give a negative answer by showing that \(1 - \frac{1}{{l^{r - 1} }}\) is not a jump ifr≧3,l>2r.     

Hypergraphs with no special cycles

A special cycle in a hypergraph is a cyclex ₁ E ₁ x ₂ E ₂ x ₃ ...x _n E _n x ₁ ofn distinct verticesx _i andn distinct edgesE _j (n≧3) whereE _i ∩{x ₁,x ₂, ...,x _n }={x _i ,x _i+1} (x _n+1=x ₁). In the equivalent (0, 1)-matrix formulation, a special cycle corresponds to a square submatrix which is the incidence matrix of a cycle of size at least 3. Hypergraphs with no special cycles have been called totally balanced by Lovász. Simple hypergraphs with no special cycles onm vertices can be shown to have at most ( ₂ ^m )+m+1 edges where the empty edge is allowed. Such hypergraphs with the maximum number of edges have a fascinating structure and are called solutions. The main result of this paper is an algorithm that shows that a simple hypergraph on at mostm vertices with no special cycles can be completed (by adding edges) to a solution. Support provided by NSERC.     

Heavy Transversals and Indecomposable Hypergraphs

A weighted hypergraph is a hypergraph H = (V, E) with a weighting function , where R is the set of reals. A multiset S V generates a partial hypergraph H ^S with edges , where both the cardinality and the total weight w(S) are counted with multiplicities of vertices in S. The transversal number of H is represented by (H). We prove the following: there exists a function f(n) such that, for any weighted n-Helly hypergraph H, (H ^B ) 1, for all multisets B V if and only if (H ^A ) 1, for all multisets A V with . We provide lower and upper bounds for f(n) using a link between indecomposable hypergraphs and critical weighted n-Helly hypergraphs.* On leave from Computing and Automation Research Institute, Hungarian Academy of Sciences.     

Density Conditions for Panchromatic Colourings of Hypergraphs

Let be a hypergraph. A panchromatic t-colouring of is a t-colouring of its vertices such that each edge has at least one vertex of each colour; and is panchromatically t-choosable if, whenever each vertex is given a list of t colours, the vertices can be coloured from their lists in such a way that each edge receives at least t different colours. The Hall ratio of is . Among other results, it is proved here that if every edge has at least t vertices and whenever , then is panchromatically t-choosable, and this condition is sharp; the minimum such that every t-uniform hypergraph with is panchromatically t-choosable satisfies ; and except possibly when t = 3 or 5, a t-uniform hypergraph is panchromatically t-colourable if whenever , and this condition is sharp. This last result dualizes to a sharp sufficient condition for the chromatic index of a hypergraph to equal its maximum degree. Received November 10, 1998 RID="*" ID="*" This work was carried out while the first author was visiting Nottingham, funded by Visiting Fellowship Research Grant GR/L54585 from the Engineering and Physical Sciences Research Council. The work of this author was also partly supported by grants 96-01-01614 and 97-01-01075 of the Russian Foundation for Fundamental Research.     

On the number of edge disjoint cliques in graphs of given size

In this paper, we prove that any graph ofn vertices andt _r–1(n)+m edges, wheret _r–1(n) is the Turán number, contains (1–o(1)m edge disjointK _r'sifm=o(n ²). Furthermore, we determine the maximumm such that every graph ofn vertices andt _r–1(n)+m edges containsm edge disjointK _r's ifn is sufficiently large.Research partially supported by Hungarian National Foundation for Scientific Research Grant no. 1812.     

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 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     

An efficient control variate method for pricing variance derivatives

This paper studies the pricing of variance swap derivatives with stochastic volatility by the control variate method. A closed form solution is derived for the approximate model with deterministic volatility, which plays the key role in the paper, and an efficient control variate technique is therefore proposed when the volatility obeys the log-normal process. By the analysis of moments for the underlying processes, the optimal volatility function in the approximate model is constructed. The numerical results show the high efficiency of our method; the results coincide with the theoretical results. The idea in the paper is also applicable for the valuation of other types of variance swap, options with stochastic volatility and other financial derivatives with multi-factor models.     

Posets with large dimension and relatively few critical pairs

The dimension of a poset (partially ordered set)P=(X, P) is the minimum number of linear extensions ofP whose intersection isP. It is also the minimum number of extensions ofP needed to reverse all critical pairs. Since any critical pair is reversed by some extension, the dimensiont never exceeds the number of critical pairsm. This paper analyzes the relationship betweent andm, when 3tmt+2, in terms of induced subposet containment. Ifmt+1 then the poset must containS _t , the standard example of at-dimensional poset. The analysis form=t+2 leads to dimension products and David Kelly's concept of a split. Whent=3 andm=5, the poset must contain eitherS ₃, or the 6-point poset called a chevron, or the chevron's dual. Whent4 andm=t+2, the poset must containS _t , or the dimension product of the Kelly split of a chevron andS _t–3, or the dual of this product.     

Custom sandwich pairs

For many equations arising in practice, the solutions are critical points of functionals. In previous papers we have shown that there are pairs of subsets, called sandwich pairs, that can produce critical points even though they do not separate the functional. All that is required is that the functional be bounded from above on one of the sets and bounded from below on the other, with no relationship needed between the bounds. This provides a distinct advantage in applications. The present paper discusses the situation in which one cannot find sandwich pairs for which the functional is bounded below on one set and bounded above on the other. We develop a method which can deal with such situations and apply it to problems in partial differential equations.     

Expanding graphs contain all small trees

The assertion of the title is formulated and proved. The result is then used to construct graphs with a linear number of edges that, even after the deletion of almost all of their edges or almost all of their vertices, continue to contain all small trees.     

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     

Extremal hypergraph problems and convex hulls

Theprofile of a hypergraph onn vertices is (f ₀, f₁, ...,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).     

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

Extending partial isomorphisms on finite structures

We prove the following theorem:Let A be a finite structure in a fixed finite relational language,p ₁,...,p _m partial isomorphisms of A. Then there exists a finite structure B, and automorphismsf _i of B extending thep _i 's. This theorem can be used to prove the small index property for the random structure in this language. A special case of this theorem is, if A and B are hypergraphs. In addition we prove the theorem for the case of triangle free graphs.     

Approximations to m‐Colored Complete Infinite Hypergraphs

Given an edge coloring of a graph with a set of m colors, we say that the graph is exactly m‐colored if each of the colors is used. In 1999, Stacey and Weidl, partially resolving a conjecture of Erickson from 1994, showed that for a fixed natural number and for all sufficiently large k, there is a k‐coloring of the complete graph on such that no complete infinite subgraph is exactly m‐colored. In the light of this result, we consider the question of how close we can come to finding an exactly m‐colored complete infinite subgraph. We show that for a natural number m and any finite coloring of the edges of the complete graph on with m or more colors, there is an exactly ‐colored complete infinite subgraph for some satisfying ; this is best possible up to the additive constant. We also obtain analogous results for this problem in the setting of r‐uniform hypergraphs. Along the way, we also prove a recent conjecture of the second author and investigate generalizations of this conjecture to r‐uniform hypergraphs.     

The Turán problem for projective geometries

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 PG_m(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.     

Set systems with three intersections

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 ₁ n ^4/3<max |F|<c ₂ n ^4/3 for some positivec _i’s. This answers a question of P. Frankl.