An improved threshold for 0–1 matrices whose squares have bounded entries

For positive integers n and t , let Γ ( n , 2 , t ) be the family of n × n 0–1 matrices A for which every entry of A 2 is at most t , and let γ ( n , 2 , t ) be the largest possible number of ones in such a matrix. A previous result established the exact value of γ ( n , 2 , t ) under a cubic lower bound on n . We reduce this sufficient order condition to a quadratic one. More precisely, for t ≥ 2 , the known extremal formula holds when n − t is even and n ≥ 2 t 2 + 6 t , and when n − t is odd and n ≥ 4 t 2 + 9 t + 2 . We also obtain an exchange-rigidity property for extremal matrices. The proof retains the exact deficit associated with the gap between the maximum degree and its extremal value.