LENGTH-RESTRICTED STAIRCASES IN A RECTANGLE, AND A QUESTION OF KATONA

In 1972, Katona proved that if you have a set V of points in a rectangle and you do not allow h+1 points to be situated on a shape called a two-segment staircase, then the size of V cannot be more than the sum of the h largest diagonals. Later, he considered what happens if you also limit the length of the forbidden staircase. In this case, the nice upper bound no longer always applies: for example, on the 5 × 5 grid with h=2 and length bound k=6, there are ten points with no short staircase, whereas unions of whole diagonals give only nine. Katona wondered if there is a good intermediate condition between the one that works and the one that fails. In this paper, we focus on quantifying how and when this bound fails. We define ex_k as the largest family that avoids h-staircases of length less than k, and md_k as the best possible size you can get by picking h diagonals in a specific way (using residue classes modulo k). The difference E_k = ex_k − md_k is called the excess. With m = min(a, b) and d = |a−b|, we show E_k ≤ ⌊(h−d)₊²/4⌋ whenever a, b ≤ k−1 and h ≤ m+1, so E_k=0 whenever d ≥ h−1 or k = max(a, b)+1. For k > max(a, b), any failure can only happen inside a bounded window, and the excess does not always reach its peak at the left end. Katona’s example turns out to be just the first of an infinite sequence: for every n ≥ 5, we construct a set of 2n points on the n × n grid with k = n+1, while md_k = 2n−1, and our argument also explains why the construction fails for n=4. Finally, we show extremal families are not unique.