Title: On the maximum density of a submatrix and a plausible transcendental Tur\'an-type density
Abstract:
We study the asymptotic maximum density of a constant matrix over an arbitrary symbol set, in a large matrix.
We solve all 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 attaining this value. The validity of this conjecture implies an explicit transcendental Tur\'an-type density. We prove the conjecture subject to plausible assumptions related to monotonicity, and also prove an upper bound of 2/e^2+10^{-3} using flag algebra.
While (h!/h^h)^2 is a 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 minimizer, i.e., a 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 0/1 matrices are minimizers.