Classical partitioning problems, like the Max-Cut problem, ask for partitions that optimize one quantity, which are important to such fields as VLSI design, combinatorial optimization, and computer science. Judicious partitioning problems on graphs or hypergraphs ask for partitions that optimize several quantities simultaneously. In this dissertation, we work on judicious partitions of graphs and hypergraphs, and solve or asymptotically solve several open problems of Bollobas and Scott on judicious partitions, using the probabilistic method and extremal techniques.

Consider an m x zero-one matrix A. An s x t submatrix of A is said to be even if the sum of its entries is even. In this paper, we focus on the case m = n and s = t = 2. The maximum number M(n) of even 2 x 2 submatrices of A is clearly ( 2n) 2, and corresponds to the matrix A having, e.g., all ones (or zeros). A more interesting question, motivated by Turán numbers and Hadamard matrices, is that of the minimum number m(n) of such matrices. It has recently been shown that m(n) ≥ 1/2 ( 2n) 2 - Bn 3 for some constant B. In this paper we show that if the matrix A = A n is considered to be induced by an infinite zero one matrix obtained at random, then P(E n ≤1/2( 2n) 2 - Cn 2 log n infinitely often) = 0, where E n denotes the number of even 2 x 2 submatrices of A n. Results such as these provide us with specific information about the tightness of the concentration of E n around its expected value of 1/2 ( 2n) 2.