Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. A size-sensitive inequality for cross-intersecting families
 
research article

A size-sensitive inequality for cross-intersecting families

Frankl, Peter
•
Kupavskii, Andrey
2017
European Journal Of Combinatorics

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.

  • Details
  • Metrics
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés