Events - Department of Mathematics

View Full Calendar

Graph Theory and Combinatorics Seminar: Q-ary generalizations of set intersection and extremal graph theoretic problems

Event Type
347 AH
Apr 7, 2022   11:00 am  
Balazs Patkos (Renyi Institute)
Sean English
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: u_i+v_i\ge s}|. We address analogs of the following classical results in this setting: the Erdos-Ko-Rado theorem and the theorem of Bollob\'as on intersecting set pairs. We will also define an s-sum analog of graph Turan problems and survey results concerning them.Joint work with Zsolt Tuza and Mate Vizer.
link for robots only