Show simple item record

dc.contributor.authorChristofides, Demetres
dc.date.accessioned2017-07-17T12:50:03Z
dc.date.available2017-07-17T12:50:03Z
dc.date.issued2008-02-12
dc.identifier.otherPhD.30928
dc.identifier.urihttps://www.repository.cam.ac.uk/handle/1810/265533
dc.descriptionThis 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.
dc.descriptionThe 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
dc.descriptionPlease 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
dc.description.abstractIn 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.
dc.rightsAll Rights Reserveden
dc.rights.urihttps://www.rioxx.net/licenses/all-rights-reserved/en
dc.titleLines in Hales-Jewett cubes and other combinatorial results
dc.typeThesis
dc.type.qualificationlevelDoctoral
dc.type.qualificationnameDoctor of Philosophy (PhD)
dc.publisher.institutionUniversity of Cambridge
dc.publisher.departmentDepartment of Pure Mathematics and Mathematical Statistics
dc.identifier.doi10.17863/CAM.11711


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record