Consider the plane as a checkerboard, with each unit square colored black or white in an arbitrary manner. We show that for any such coloring there are straight line segments, of arbitrarily large length, such that the difference of their white length minus their black length, in absolute value, is at least the square root of their length, up to a multiplicative constant. For the corresponding “finite” problem ($N\times N$ checkerboard) we also prove that we can color it in such a way that the above quantity is at most $C\sqrt{N}\log N$, for any placement of the line segment.

Let $h_R$ denote an $L^{\mathrm{\infty }}$-normalized Haar function adapted to a dyadic rectangle $R\subset [0,1{]}^d$. We show that for all choices of coefficients $\alpha (R)\in \{\pm 1\}$, we have the following lower bound on the $L^{\mathrm{\infty }}$-norms of the sums of such functions, where the sum is over rectangles of a fixed volume:
$$n^{\eta (d)}\lesssim \parallel \sum _{|R|=2^{-n}}\alpha (R)h_R(x){\parallel }_{L^{\mathrm{\infty }}([0,1{]}^d)},\text{for all }\eta (d)<\frac{d-1}{2}+\frac{1}{8d},$$
where the implied constant is independent of $n\ge 1$. The inequality above (without restriction on the coefficients) arises in connection to several areas, such as Probabilities, Approximation, and Discrepancy. With $\eta (d)=(d-1)/2$, the inequality above follows from orthogonality, while it is conjectured that the inequality holds with $\eta (d)=d/2$. This is known and proved in $(Talagrand,1994)$ in the case of $d=2$, and recent papers of the authors $(Bilyk\text{ and }Lacey,2006)$, $(Bilyk\text{ et al., 2007})$ prove that in higher dimensions one can take $\eta (d)>(d-1)/2$, without specifying a particular value of $\eta$. The restriction ${\alpha }_R\in \{\pm 1\}$ allows us to significantly simplify our prior arguments and to find an explicit value of $\eta (d)$.

We study the generating functions for pattern-restricted $k$-ary words of length $n$ corresponding to the longest alternating subsequence statistic in which the pattern is any one of the six permutations of length three.

We extend an argument of Felix Behrend to show that fairly dense subsets of the integers exist which contain no solution to certain systems of linear equations.

Using combinatorial methods, we derive several formulas for the volume of convex bodies obtained by intersecting a unit hypercube with a halfspace, or with a hyperplane of codimension 1, or with a flat defined by two parallel hyperplanes. We also describe some of the history of these problems, dating to Polya’s Ph.D. thesis, and we discuss several applications of these formulas.