We consider some aspects of the global geometry of cellular complexes. Motivated by techniques in graph theory, we develop combinatorial versions of isoperimetric and Poincare inequalities, and use them to derive various geometric and topological estimates. This has a progression of three major topics: 1. We define isoperimetric inequalities for normed chain complexes. In the graph case, these quantities boil down to various notions of graph expansion. We also develop some randomized algorithms which provide (in expectation) solutions to these isoperimetric problems. 2. We use these isoperimetric inequalities to derive topological and geometric estimates for certain models of random simplicial complexes. These models are generalizations of the well-known models of random graphs. 3. Using these random complexes as examples, we show that there are simplicial complexes which cannot be embedded into Euclidean space while faithfully preserving the areas of minimal surfaces.

Extremal combinatorics studies how large a collection of objects can be if it satisfies a given set of restrictions. Inspired by a classical theorem due to Erdos, Ko and Rado, Simonovits and Sos posed the following problem: determine how large a collection of graphs on the vertex set {1,...,n} can be, if the intersection of any two of them contains a triangle. They conjectured that the largest possible collection, containing 1/8 of all graphs, consists of all graphs containing a fixed triangle (a triangle-star). The first major contribution of this thesis is a confirmation of this conjecture. We prove the Simonovits–Sos conjecture in the following strong form: the only triangle-intersecting families of measure at least 1/8 are triangle-stars (uniqueness), and every triangle-intersecting family of measure 1/8−e is O(e)-close to a triangle-star (stability). In order to prove the stability part of our theorem, we utilize a structure theorem for Boolean functions on {0,1}^m whose Fourier expansion is concentrated on the first t+1 levels, due to Kindler and Safra. The second major contribution of this thesis consists of two analogs of this theorem for Boolean functions on S_m whose Fourier expansion is concentrated on the first two levels. In the same way that the Kindler–Safra theorem is useful for studying triangle-intersecting families, our structure theorems are useful for studying intersecting families of permutations, which are families in which any two permutations agree on the image of at least one point. Using one of our theorems, we give a simple proof of the following result of Ellis, Friedgut and Pilpel: an intersecting family of permutations on S_m of size (1−e)(m−1)! is O(e)-close to a double coset, a family which consists of all permutations sending some point i to some point j.

We consider some aspects of the global geometry of cellular complexes. Motivated by techniques in graph theory, we develop combinatorial versions of isoperimetric and Poincare inequalities, and use them to derive various geometric and topological estimates. This has a progression of three major topics: 1. We define isoperimetric inequalities for normed chain complexes. In the graph case, these quantities boil down to various notions of graph expansion. We also develop some randomized algorithms which provide (in expectation) solutions to these isoperimetric problems. 2. We use these isoperimetric inequalities to derive topological and geometric estimates for certain models of random simplicial complexes. These models are generalizations of the well-known models of random graphs. 3. Using these random complexes as examples, we show that there are simplicial complexes which cannot be embedded into Euclidean space while faithfully preserving the areas of minimal surfaces.

Extremal combinatorics studies how large a collection of objects can be if it satisfies a given set of restrictions. Inspired by a classical theorem due to Erdos, Ko and Rado, Simonovits and Sos posed the following problem: determine how large a collection of graphs on the vertex set {1,...,n} can be, if the intersection of any two of them contains a triangle. They conjectured that the largest possible collection, containing 1/8 of all graphs, consists of all graphs containing a fixed triangle (a triangle-star). The first major contribution of this thesis is a confirmation of this conjecture. We prove the Simonovits–Sos conjecture in the following strong form: the only triangle-intersecting families of measure at least 1/8 are triangle-stars (uniqueness), and every triangle-intersecting family of measure 1/8−e is O(e)-close to a triangle-star (stability). In order to prove the stability part of our theorem, we utilize a structure theorem for Boolean functions on {0,1}^m whose Fourier expansion is concentrated on the first t+1 levels, due to Kindler and Safra. The second major contribution of this thesis consists of two analogs of this theorem for Boolean functions on S_m whose Fourier expansion is concentrated on the first two levels. In the same way that the Kindler–Safra theorem is useful for studying triangle-intersecting families, our structure theorems are useful for studying intersecting families of permutations, which are families in which any two permutations agree on the image of at least one point. Using one of our theorems, we give a simple proof of the following result of Ellis, Friedgut and Pilpel: an intersecting family of permutations on S_m of size (1−e)(m−1)! is O(e)-close to a double coset, a family which consists of all permutations sending some point i to some point j.

We prove various results in additive combinatorics for subsets of random sets. In particular we extend Sarkozy's theorem and a theorem of Green on long arithmetic progressions in sumsets to dense subsets of random sets with asymptotic density 0. Our proofs require a transference argument due to Green and Green-Tao which enables us to apply known results for sets of positive upper density to subsets of random sets which have positive relative density. We also prove a density result which states that if a subset of a random set has positive relative density, then the sumset of the subset must have positive upper density in the integers.

In this thesis, we obtain approximations to the non-3-colourability threshold of sparse random graphs and we investigate the structure of random graphs near the region where the transition from 3-colourability to non-3-colourability seems to occur. It has been observed that, as for many other properties, the property of non-3-colourability of graphs exhibits a sharp threshold behaviour. It is conjectured that there exists a critical average degree such that when the average degree of a random graph is around this value the probability of the random graph being non-3-colourable changes rapidly from near 0 to near 1. The difficulty in calculating the critical value arises because the number of proper 3-colourings of a random graph is not concentrated: there is a `jackpot' effect. In order to reduce this effect, we focus on a sub-family of proper 3-colourings, which are called rigid 3-colourings. We give precise estimates for their expected number and we deduce that when the average degree of a random graph is bigger than 5, then the graph is asymptotically almost surely not 3-colourable. After that, we investigate the non-$k$-colourability of random regular graphs for any $k \geq 3$. Using a first moment argument, for each $k \geq 3$ we provide a bound so that whenever the degree of the random regular graph is bigger than this, then the random regular graph is asymptotically almost surely not $k$-colourable. Moreover, in a (failed!) attempt to show that almost all 5-regular graphs are not 3-colourable, we analyse the expected number of rigid 3-colourings of a random 5-regular graph. Motivated by the fact that the transition from 3-colourability to non-3-colourability occurs inside the subgraph of the random graph that is called the 3-core, we investigate the structure of this subgraph after its appearance. Indeed, we do this for the $k$-core, for any $k \geq 2$; and by extending existing techniques we obtain the asymptotic behaviour of the proportion of vertices of each fixed degree. Finally, we apply these results in order to obtain a more clear view of the structure of the 2-core (or simply the core) of a random graph after the emergence of its giant component. We determine the asymptotic distributions of the numbers of isolated cycles in the core as well as of those cycles that are not isolated there having any fixed length. Then we focus on its giant component, and in particular we give the asymptotic distributions of the numbers of 2-vertex and 2-edge-connected components.

In this thesis, we investigate the cost of finding collisions in a black-box function, a problem that is of fundamental importance in cryptanalysis. Inspired by the excellent performance of the heuristic rho method of collision finding, we define several new models of complexity that take into account the cost of moving information across a large space, and lay the groundwork for studying the performance of classical and quantum algorithms in these models.

The Trust Region Subproblem (TRS) is the problem of minimizing a quadratic (possibly non-convex) function over a sphere. It is the main step of the trust region method for unconstrained optimization problems. Two cases may cause numerical difficulties in solving the TRS, i.e., (i) the so-called hard case and (ii) having a large trust region radius. In this thesis we give the optimality characteristics of the TRS and review the major current algorithms. Then we introduce some techniques to solve the TRS efficiently for the two difficult cases. A shift and deflation technique avoids the hard case; and a scaling can adjust the value of the trust region radius. In addition, we illustrate other improvements for the TRS algorithm, including: rotation, approximate eigenvalue calculations, and inverse polynomial interpolation. We also introduce a warm start approach and include a new treatment for the hard case for the trust region method. Sensitivity analysis is provided to show that the optimal objective value for the TRS is stable with respect to the trust region radius in both the easy and hard cases. Finally, numerical experiments are provided to show the performance of all the improvements.

A classic combinatorics problem is: What is the probability that if n people randomly reach into a dark closet to retrieve their hats, no person will pick his own hat? Now there are n! ways to retrieve n hats if you didn't care which hat you got. But for this problem you need to determine how may different ways no person will pick his own hat. In this paper we expand on the original idea and consider two variations of this problem: If there are n elements and m distinguishable possibilities, in how many ways can you rearrange these elements. For example, if n men check their hats and k women check their hats, in how many ways will the men retrieve a different hat than the one he checked. The second problem is: if n people randomly reach into a dark closet to retrieve their hat but now there are m hats in the closet, how many different ways will no person retrieve his hat? In the second case m >= n.

We prove various results in additive combinatorics for subsets of random sets. In particular we extend Sarkozy's theorem and a theorem of Green on long arithmetic progressions in sumsets to dense subsets of random sets with asymptotic density 0. Our proofs require a transference argument due to Green and Green-Tao which enables us to apply known results for sets of positive upper density to subsets of random sets which have positive relative density. We also prove a density result which states that if a subset of a random set has positive relative density, then the sumset of the subset must have positive upper density in the integers. / Science, Faculty of / Mathematics, Department of / Graduate