Problems of optimal choice on posets and generalizations of acyclic colourings

NOTE : The mathematical symbols in the abstract do not always display correctly in this text field. Please see the abstract in the thesis for the definitive abstract. ABSTRACT: This dissertation is in two parts, each of three chapters. In Part 1, I shall prove some results concerning variants of the `secretary problem'. In Part 2, I shall bound several generalizations of the acyclic chromatic number of a graph as functions of its maximum degree. I shall begin Chapter 1 by describing the classical secretary problem, in which the aim is to select the best candidate for the post of a secretary, and its solution. I shall then summarize some of its many generalizations that have been studied up to now, provide some basic theory, and briefly outline the results that I shall prove. In Chapter 2, I shall suppose that the candidates come as ‘m’ pairs of equally qualified identical twins. I shall describe an optimal strategy, a formula for its probability of success and the asymptotic behaviour of this strategy and its probability of success as m → ∞. I shall also find an optimal strategy and its probability of success for the analagous version with ‘c’-tuplets. I shall move away from known posets in Chapter 3, assuming instead that the candidates come from a poset about which the only information known is its size and number of maximal elements. I shall show that, given this information, there is an algorithm that is successful with probability at least ¹/e . For posets with ‘k ≥ 2’ maximal elements, I shall prove that if their width is also ‘k’ then this can be improved to ‘k-1√1/k’ and show that no better bound of this type is possible. In Chapter 4, I shall describe the history of acyclic colourings, in which a graph must be properly coloured with no two-coloured cycle, and state some results known about them and their variants. In particular, I shall highlight a result of Alon, McDiarmid and Reed, which bounds the acyclic chromatic number of a graph by a function of its maximum degree. My results in the next two chapters are of this form. I shall consider two natural generalizations in Chapter 5. In the first, only cycles of length at least ’l’ must receive at least three colours. In the second, every cycle must receive at least ‘c’ colours, except those of length less than ‘c’, which must be multicoloured. My results in Chapter 6 generalize the concept of a cycle; it is now subgraphs with minimum degree ‘r’ that must receive at least three colours, rather than subgraphs with minimum degree two (which contain cycles). I shall also consider a natural version of this problem for hypergraphs.

Name dc:type.qualificationname

Doctor of Philosophy (PhD)

Level dc:type.qualificationlevel

Doctoral

Grantor dc:publisher.institution

University of Cambridge

Year dc:date.issued

2011

Author dc:creator

• Garrod, Bryn James

• Partially ordered sets
• Graph theory
• Graph coloring
• Secretary problem (Probability theory)

Licence

• https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/0b32dc13-2ba0-438c-9ed6-c0b8be1070d2/download
• https://www.rioxx.net/licenses/all-rights-reserved/

Language dc:language

eng

DOI dc:identifier.doi

https://doi.org/10.17863/CAM.16222

OAI identifier oai:identifier

oai:www.repository.cam.ac.uk:1810/243496