Discrete Math Seminar: Q-ary generalizations of set intersection and extremal graph theoretic problems

Characteristic vectors of subsets of an $n$-element ground set give a natural 1-to-1 correspondence between set systems and 0-1 vector systems. As the size of the intersection of two sets equals the scalar product of their characteristic vectors, this correspondence is often used in proofs of intersection theorems of finite sets. There exist several definitions of intersection for vectors of length $n$ with entries from $\{0,1,...,q\}$. In this talk, we will propose a new one: the size of the $s$-sum intersection of two such vectors $u,v$ is the number of coordinates where the entries have sum at least $s$, i.e. ∣{i:ui+vi≥s}∣|\{i: u_i+v_i\ge s\}|∣{i:ui​+vi​≥s}∣. We address analogs of the following classical results in this setting: the Erdős–Ko–Rado theorem and the theorem of Bollobás on intersecting set pairs. We will also define an $s$-sum analog of graph Turán problems and survey results concerning them.

Joint work with Zsolt Tuza and Máté Vizer.