We prove that Boolean matrices with bounded $\gamma_{2}$-norm or bounded normalized trace norm must contain a linear-sized all-ones or all-zeros submatrix, verifying a conjecture of Hambardzumyan, Hatami, and Hatami. We also present further structural results about Boolean matrices of bounded $\gamma_{2}$-norm and discuss applications in communication complexity, operator theory, spectral graph theory, and extremal combinatorics. As a key application, we establish an inverse theorem for MaxCut. A celebrated result of Edwards states that every graph G with m edges has a cut of size at least $\frac{m}{2}+\frac{\sqrt{8 m+1}-1}{8}$, with equality achieved by complete graphs with an odd number of vertices. To contrast this, we prove that if the MaxCut of G is at most $\frac{m}{2}+O(\sqrt{m})$, then G must contain a clique of size $\Omega(\sqrt{m})$.

Abstract Given positive integers $$k\le d$$ k ≤ d and a finite field $$\mathbb {F}$$ F , a set $$S\subset \mathbb {F}^{d}$$ S ⊂ F d is (k, c)-subspace evasive if every k-dimensional affine subspace contains at most c elements of S. By a simple averaging argument, the maximum size of a (k, c)-subspace evasive set is at most $$c |\mathbb {F}|^{d-k}$$ c | F | d - k . When k and d are fixed, and c is sufficiently large, the matching lower bound $$\Omega (|\mathbb {F}|^{d-k})$$ Ω ( | F | d - k ) is proved by Dvir and Lovett. We provide an alternative proof of this result using the random algebraic method. We also prove sharp upper bounds on the size of (k, c)-evasive sets in case d is large, extending results of Ben-Aroya and Shinkar. The existence of optimal evasive sets has several interesting consequences in combinatorial geometry. We show that the minimum number of k-dimensional linear hyperplanes needed to cover the grid $$[n]^{d}\subset \mathbb {R}^{d}$$ [ n ] d ⊂ R d is $$\Omega _{d}\big (n^{\frac{d(d-k)}{d-1}}\big )$$ Ω d ( n d ( d - k ) d - 1 ) , which matches the upper bound proved by Balko et al., and settles a problem proposed by Brass et al. Furthermore, we improve the best known lower bound on the maximum number of incidences between points and hyperplanes in $$\mathbb {R}^{d}$$ R d assuming their incidence graph avoids the complete bipartite graph $$K_{c,c}$$ K c , c for some large constant $$c=c(d)$$ c = c ( d ) .

In this paper we study the fundamental problem of finding small dense subgraphs in a given graph. For a real number s > 2, we prove that every graph on n vertices with average degree at least d contains a subgraph of average degree at least s on at most vertices. This is optimal up to the polylogarithmic factor, and resolves a conjecture of Feige and Wagner. * The full version of the paper can be accessed at https://arxiv.org/abs/2207.02170

Abstract A string graph is the intersection graph of curves in the plane. We prove that for every $$\epsilon >0$$ ϵ > 0 , if G is a string graph with n vertices such that the edge density of G is below $${1}/{4}-\epsilon $$ 1 / 4 - ϵ , then V(G) contains two linear sized subsets A and B with no edges between them. The constant 1/4 is a sharp threshold for this phenomenon as there are string graphs with edge density less than $${1}/{4}+\epsilon $$ 1 / 4 + ϵ such that there is an edge connecting any two logarithmic sized subsets of the vertices. The existence of linear sized sets A and B with no edges between them in sufficiently sparse string graphs is a direct consequence of a recent result of Lee about separators. Our main theorem finds the largest possible density for which this still holds. In the special case when the curves are x-monotone, the same result was proved by Pach and the author of this paper, who also proposed the conjecture for the general case.

A matrix is homogeneous if all of its entries are equal. Let $P$ be a $2\times 2$ zero-one matrix that is not homogeneous. We prove that if an $n\times n$ zero-one matrix $A$ does not contain $P$ as a submatrix, then $A$ has a $cn\times cn$ homogeneous submatrix for a suitable constant $c>0$. We further provide an almost complete characterization of the matrices $P$ (missing only finitely many cases) such that forbidding $P$ in $A$ guarantees an $n^{1-o(1)}\times n^{1-o(1)}$ homogeneous submatrix. We apply our results to chordal bipartite graphs, totally balanced matrices, halfplane arrangements, and string graphs.