Talk information

Date: Sunday, January 28, 2024
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Raphy Yuster (Haifa)
Title: On the maximum density of a submatrix and a possible transcendental Turán-type density

Abstract:

We study the asymptotic maximum density at which a given constant (say, square) matrix over an arbitrary set of symbols can appear in a large (say, square) matrix over an arbitrary set of symbols.

We solve the $2 \times 2$ cases except for one isomorphism type for which the asymptotic maximum density is conjectured to be $2/e^2$, and construct a limit object having the conjectured value. The validity of this conjecture would imply an explicit example of a transcendental Turán-type density. While $(h!/h^h)^2$ is a simple lower bound for the asymptotic maximum density of an $h \times h$ matrix, we explicitly construct, for all $h \ge 1$, an $h \times h$  matrix for which this bound is attained. We also sketch how known results on the inducibility of graphs can be modified to show that, as $h$ grows, almost all $h \times h$ binary matrices have asymptotic maximum density $(h!/h^h)^2$.