Infoscience

Journal article

A size-sensitive inequality for cross-intersecting families

Two families A and B, of k-subsets of an n-set are called cross intersecting if A boolean AND B not equal phi for all A,B epsilon b. Strengthening the classical ErclOs-Ko-Rado theorem, Pyber proved that vertical bar A vertical bar vertical bar B vertical bar <= (n-1 k-1)(2)holds for n > 2k. In the present paper we sharpen this inequality. We prove that assuming vertical bar B vertical bar >= ((n - 1 k - 1) - (n -1 k -1)) for some 3 <= i <= k + 1 the stronger inequality vertical bar A vertical bar vertical bar B vertical bar <= ((n - 1 k - 1) + (n-i k -i+1)) x ((n - 1 k - 1) - (n -1 k -1)) holds. These inequalities are best possible. We also present a new short proof of Pyber's inequality and a short computation-free proof of an inequality due to Frankl and Tokushige (1992). (C) 2017 Elsevier Ltd. All rights reserved.

Fulltext

Related material