Publication

A size-sensitive inequality for cross-intersecting families

Andrei Kupavskii
2017
Journal Articles

Abstract

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

Official source

https://infoscience.epfl.ch/entities/publication/f1fe3fc7-8eb0-4fee-a994-be80fdffae6a

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Andrei Kupavskii
2017
Journal Articles

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/f1fe3fc7-8eb0-4fee-a994-be80fdffae6a

About this result

Related concepts (17)

Finite set

In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example, is a finite set with five elements. The number of elements of a finite set is a natural number (possibly zero) and is called the cardinality (or the cardinal number) of the set. A set that is not a finite set is called an infinite set.

Subset

In mathematics, set A is a subset of a set B if all elements of A are also elements of B; B is then a superset of A. It is possible for A and B to be equal; if they are unequal, then A is a proper subset of B. The relationship of one set being a subset of another is called inclusion (or sometimes containment). A is a subset of B may also be expressed as B includes (or contains) A or A is included (or contained) in B. A k-subset is a subset with k elements. The subset relation defines a partial order on sets.

Mathematical proof

A mathematical proof is a deductive argument for a mathematical statement, showing that the stated assumptions logically guarantee the conclusion. The argument may use other previously established statements, such as theorems; but every proof can, in principle, be constructed using only certain basic or original assumptions known as axioms, along with the accepted rules of inference. Proofs are examples of exhaustive deductive reasoning which establish logical certainty, to be distinguished from empirical arguments or non-exhaustive inductive reasoning which establish "reasonable expectation".

Related publications (21)

A size-sensitive inequality for cross-intersecting families

Chat with Graph Search

SC-TPTP: An Extension of the TPTP Derivation Format for Sequent-Based Calculus

LISA – A Modern Proof System

A Gapless Post-quantum Hash Proof System in the Hamming Metric