## Lines in Hales-Jewett cubes and other combinatorial results

##### View / Open Files

##### Authors

Christofides, Demetres

##### Date

2008-02-12##### Awarding Institution

University of Cambridge

##### Author Affiliation

Department of Pure Mathematics and Mathematical Statistics

##### Qualification

Doctor of Philosophy (PhD)

##### Type

Thesis

##### Metadata

Show full item record##### Citation

Christofides, D. (2008). Lines in Hales-Jewett cubes and other combinatorial results (Doctoral thesis). https://doi.org/10.17863/CAM.11711

##### Description

This thesis is not available on this repository until the author agrees to make it public. If you are the author of this thesis and would like to make your work openly available, please contact us: thesis@repository.cam.ac.uk.

The Library can supply a digital copy for private research purposes; interested parties should submit the request form here: http://www.lib.cam.ac.uk/collections/departments/digital-content-unit/ordering-images

Please note that print copies of theses may be available for consultation in the Cambridge University Library's Manuscript reading room. Admission details are at http://www.lib.cam.ac.uk/collections/departments/manuscripts-university-archives

##### Abstract

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.