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

April 12, 2022, 3:10-4:00pm | Carver Hall 401 & Zoom

Speaker: Balázs Patkós (Alfréd Rényi Institute of Mathematics)

Abstract:

-ary generalizations of set intersection and extremal graph theoretic problems

Characteristic vectors of subsets of an nn-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 nn with entries from {0,1,…,q}\{0,1,…,q\}. In this talk, we will propose a new one: the size of the ss-sum intersection of two such vectors u,vu,v is the number of coordinates where the entries have sum at least ss, i.e. ∣{i:ui+vi≥s}∣|\{i: u_i+v_i\ge 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 ss-sum analog of graph Turán problems and survey results concerning them.

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