Discrete Applied Mathematics Seminar by Michael Tait: Subgraphs of Pseudo-Random Graphs

Speaker: Michael Tait, Villanova University

Title: Subgraphs of Pseudo-Random Graphs
Abstract: Fix a graph $F$. If I have a large pseudo-random graph can I always find $F$ as a subgraph? Can I count the number of copies? What about if I only have a sufficiently large subset of vertices of my pseudo-random graph?
We discuss how to use spectral graph theory to give a general framework for questions like these. Some of the applications are to questions in discrete geometry and VC dimension. One representative question that we are motivated by is the following:

Let $E$ be a set in ${\mathbb{F}}_q^d$ and $\alpha ,\beta \in {\mathbb{F}}_q^{\ast }$. How large does $E$ need to be to guarantee that there are four points $w,x,y,z\in E$ such that they form a rectangle of side lengths $\alpha$ and $\beta$, i.e.
$$(w-x)\cdot (x-y)=0,(x-y)\cdot (y-z)=0,(y-z)\cdot (z-w)=0,(z-w)(w-x)=0,$$
and $$||w-x||=||y-z||=\alpha ,||x-y||=||z-w||=\beta .$$

Our general framework makes progress on this and other similar questions as a corollary. This is joint work with Thang Pham, Steven Senger, and Vu Thi Huong Thu (and if time permits also with Alex Iosevich and Thu Huyen Nguyen).

Discrete Applied Math Seminar

Request Zoom link