Originators: (presented by Douglas West - REGS 2011, based on presentation by Miguel Raggi at CanaDAM)
Definitions: A (0,1)-matrix may be viewed as a grid with some locations marked. A (p,q)-separation of such a matrix is a placement of p-1 horizontal lines (between rows of locations) and q-1 vertical lines (between columns of locations). It is a (p,q)-split if each of the resulting pq regions (cells) contains a marked location.
Question: Given positive integers n,p,q, what is the maximum number fp,q(n) of marks in an n-by-n grid having no (p,q)-split? (Equivalently, how many marks are needed to guarantee existence of a (p,q)-split?)
Background: Extremal problems for the number of marks in a grid when various configurations are forbidden have been motivated by problems in computational geometry; see [BG]. In that paper, the problem of forbidding "trapezoids" is studied; trapezoids are certain configurations that yield a (2,2)-split. A much different problem (with a beautiful solution in [MT]) forbids a (p,p)-separation in which the cells containing marks form a specified p-by-p permutation matrix.
Results: The construction in which the topmost p-1 rows and leftmost q-1 columns are filled with marks has no (p,q)-split, so fp,q(n)\ge (p-1)n+(q-1)n-(p-1)(q-1). Equality is know to hold when min{p,q}=3. The proof of optimality in this case is not very difficult: at most this many marks are removed in a specified way, and if any mark now remains, then the original configuration had a (p,q)-split.
Equality does not hold for large p and q. In particular, there is a construction with 7n-13 marks having no (4,4)-split. This is believed but not known to be optimal. According to Raggi, Marcus-Tardos-Glazer proved an upper bound that is linear in n for fixed p and q, but the leading coefficient is very large.
References:
[BG] Bienstock, Dan; Györi, Ervin.
An extremal problem on sparse 0-1 matrices.
SIAM J. Discrete Math. 4 (1991), 17-27.
[MT] Marcus, Adam; Tardos, Gábor.
Excluded permutation matrices and the Stanley-Wilf conjecture.
J. Combin. Theory Ser. A 107 (2004), 153-160.
[MTG] Marcus, Adam; Tardos, Gábor, Glazer ???