In Chapter 1, we are concerned with the number of lines a set S <;;;; [n]d of a given size can contain. Here, a line in [n]d means a 'geometric line ', i.e. a set { x(ll, ... , x(n)} of n elements of [n]d such that for each 1 :::; i :::; d, the sequence x?), ... , x~n) is either strictly increasing from 1 to n, or strictly decreasing from n to 1, or constant. One of our aims in this chapter is to provide for every n ~ 3, a counterexample to the Ratio Conjecture of Patashnik, which states that the greatest average degree is attained when S = [n]d. Our other main aim is to prove the result (which would have been strongly suggested by the Ratio Conjecture) that the number of lines contained in S is at most [S[ 2 -c: for some c > 0. Our main aim in Chapter 2 is to provide a new proof of the Alon-Roichman Theorem. There are groups, for example Z2', such that their smallest generating set has size at least log [ G [. The Alon-Roichman Theorem theorem states that for any group G, if we pick clog [G[ elements of G uniformly at random, then not only do these elements form a generating set for the group, but in fact the Cayley graph of G with respect to these elements is highly connected, in the sense that it is an expander graph. Our proof of the Alon-Roichman Theorem gives an improvement to the known bounds. In Chapter 3, we study properties of random graphs arising from Latin squares. These include, as special cases, results on random Cayley graphs which were previously unknown. In Chapter 4, we provide asymptotically best possible bounds for a randomized version of the majority problem, extending a result of De 1/Iarco and Pelc. In this problem, we are given n balls coloured black and white. We are allowed to query whether two balls have the same colour or not and our task is to find a ball of majority colour in the minimal number of queries. Finally, in Chapter 5, we prove that the pair length of the cartesian product of two graphs is the sum of their pair lengths, answering a question of Chen.