Cross-intersecting families of permutations

For positive integers r and n with r?n, let Pr,n be the family of all sets {(1,y₁),(2,y₂),…,(r,yr)} such that y₁,y₂,…,yr are distinct elements of [n]={1,2,…,n}. Pn,n describes permutations of [n]. For r<n, Pr,n describes permutations of r-element subsets of [n]. Families A₁,A₂,…,Ak of sets are said to be cross-intersecting if, for any distinct i and j in [k], any set in Ai intersects any set in Aj. For any r, n and k?2, we determine the cases in which the sum of sizes of cross-intersecting sub-families A₁,A₂,…,Ak of Pr,n is a maximum, hence solving a recent conjecture (suggested by the author).     

Multiple cross-intersecting families of signed sets

A k-signed r-set on[n]={1,…,n} is an ordered pair (A,f), where A is an r-subset of [n] and f is a function from A to [k]. Families A₁,…,Ap are said to be cross-intersecting if any set in any family Ai intersects any set in any other family Aj. Hilton proved a sharp bound for the sum of sizes of cross-intersecting families of r-subsets of [n]. Our aim is to generalise Hilton's bound to one for families of k-signed r-sets on [n]. The main tool developed is an extension of Katona's cyclic permutation argument.     

Clique number of Xor products of Kneser graphs

In this article we investigate a problem in graph theory, which has an equivalent reformulation in extremal set theory similar to the problems researched in “A general 2-part Erd?s-Ko-Rado theorem” by Gyula O.H. Katona, who proposed our problem as well. In the graph theoretic form we examine the clique number of the Xor product of two isomorphic $KG(N,k)$ Kneser graphs. Denote this number with $f(k,N)$. We give lower and upper bounds on $f(k,N)$, and we solve the problem up to a constant deviation depending only on k, and find the exact value for $f(2,N)$ if N is large enough. Also we compute that $f(k,k^2)$ is asymptotically equivalent to $k^2$.     

Weighted cross-intersecting families

In this paper we investigate weighted cross-intersecting families: if α,β>0 are given constants, we want to find the maximum of α|A|+β|B| for A,B uniform cross-intersecting families. We determine the maximum sum, even if we have restrictions of the size of A.As corollaries, we will obtain some new bounds on the shadows and the shades of uniform families. We give direct proofs for these bounds, as well, and show that the theorems for cross-intersecting families also follow from these results.Finally, we will generalize the LYM inequality not only for cross-intersecting families, but also for arbitrary Sperner families.     

Setwise intersecting families of permutations

A family of permutations A⊂Sn is said to be t-set-intersecting if for any two permutations σ,π∈A, there exists a t-set x whose image is the same under both permutations, i.e. σ(x)=π(x). We prove that if n is sufficiently large depending on t, the maximum-sized t-set-intersecting families of permutations in Sn are cosets of stabilizers of t-sets. The t=2 case of this was conjectured by János Körner. It can be seen as a variant of the Deza-Frankl conjecture, proved in Ellis, Friedgut and Pilpel (2011) [3]. Our proof uses similar techniques to those of Ellis, Friedgut and Pilpel (2011) [3], namely, eigenvalue methods, together with the representation theory of the symmetric group, but the combinatorial part of the proof is harder.     

Stable sets, corner polyhedra and the Chvátal closure

We consider the edge formulation of the stable set problem. We characterize its corner polyhedron, i.e. the convex hull of the points satisfying all the constraints except the non-negativity of the basic variables. We show that the non-trivial inequalities necessary to describe this polyhedron can be derived from one row of the simplex tableau as fractional Gomory cuts. It follows that the split closure is not stronger than the Chvátal closure for the edge relaxation of the stable set problem.     

The Unbalance of Set Systems

The unbalance of an intersecting family is defined as , where is the maximum degree of i.e. the maximum of over all vertices x. We show that the unbalance of a k-uniform intersecting family is at most when n ≥ 6k ³ and we determine all families achieving this bound.     

A short proof of a cross-intersection theorem of Hilton

Families A₁,…,A_k of sets are said to be cross-intersecting if for any A_i∈A_i and A_j∈A_j, i≠j. A nice result of Hilton that generalises the Erd?s-Ko-Rado (EKR) Theorem says that if r≤n/2 and A₁,…,A_k are cross-intersecting sub-families of , then

     

More complete intersection theorems

The seminal complete intersection theorem of Ahlswede and Khachatrian gives the maximum cardinality of a $k$-uniform $t$-intersecting family on $n$ points, and describes all optimal families. In recent work, we extended this theorem to the weighted setting, giving the maximum ${\mu }_p$ measure of a $t$-intersecting family on $n$ points. In this work, we prove two new complete intersection theorems. The first gives the supremum ${\mu }_p$ measure of a $t$-intersecting family on infinitely many points, and the second gives the maximum cardinality of a subset of ${\mathbb{Z}}_m^n$ in which any two elements $x,y$ have $t$ positions $i_1,\dots ,i_t$ such that $x_{i_j}?y_{i_j}\in \{?(s?1),\dots ,s?1\}$. In both cases, we determine the extremal families, whenever possible.     

On non-strong jumping numbers and density structures of hypergraphs

Estimating Turán densities of hypergraphs is believed to be one of the most challenging problems in extremal set theory. The concept of ‘jump’ concerns the distribution of Turán densities. A number α∈[0,1) is a jump for r-uniform graphs if there exists a constant c>0 such that for any family F of r-uniform graphs, if the Turán density of F is greater than α, then the Turán density of F is at least α+c. A fundamental result in extremal graph theory due to Erd?s and Stone implies that every number in [0,1) is a jump for graphs. Erd?s also showed that every number in [0,r!/r^r) is a jump for r-uniform hypergraphs. Furthermore, Frankl and Rödl showed the existence of non-jumps for hypergraphs. Recently, more non-jumps were found in [r!/r^r,1) for r-uniform hypergraphs. But there are still a lot of unknowns regarding jumps for hypergraphs. In this paper, we propose a new but related concept-strong-jump and describe several sequences of non-strong-jumps. It might help us to understand the distribution of Turán densities for hypergraphs better by finding more non-strong-jumps.     

Paths partition with prescribed beginnings in digraphs: A Chvátal-Erd?s condition approach

A digraph D verifies the Chvátal-Erd?s conditions if α(D)?κ(D), where α(D) is the stability number of D and κ(D) is its vertex-connectivity. Related to the Gallai-Milgram Theorem (see Gallai and Milgram [Verallgemeinerung eines Graphentheorischen Satzes von Redei, Acta Sci. Math. 21 (1960) 181-186]), we raise in this context the following conjecture. For every set of α=α(D) vertices {x₁,…,x_α}, there exists a vertex-partition of D into directed paths {P₁,…,P_α} such that P_i begins at x_i for all i. The case α(D)=2 of the conjecture is proved.     

Erdős matching conjecture for almost perfect matchings

In 1965 Erd?s asked, what is the largest size of a family of k-element subsets of an n-element set that does not contain a matching of size $s+1$? In this note, we improve upon a recent result of Frankl and resolve this problem for $s>101k^3$ and $(s+1)k?n<(s+1)(k+\frac{1}{100k})$.     

On Cross-intersecting Families of Sets

A family of -element subsets and a family of k-element subsets of an n-element set are cross-intersecting if every set from has a nonempty intersection with every set from . We compare two previously established inequalities each related to the maximization of the product , and give a new and short proof for one of them. We also determine the maximum of for arbitrary positive weights ,_k.     

Largest Families Without an <Emphasis Type="Italic">r</Emphasis>-Fork

Let [n] = { 1,2,...,n} be a finite set, a family of its subsets, 2 ≤ r a fixed integer. Suppose that contains no r + 1 distinct members F, G ₁,..., G _r such that F ⊂ G ₁,...,F ⊂ G _r all hold. The maximum size is asymptotically determined up to the second term, improving the result of Tran. The work of the second author was supported by the Hungarian National Foundation for Scientific Research grant numbers NK0621321, AT048826, the Bulgarian National Science Fund under Grant IO-03/2005 and the projects of the European Community: INTAS 04-77-7171, COMBSTRU–HPRN-CT-2002-000278, FIST–MTKD-CT-2004-003006.