Poset saturation and other combinatorial results
type: CreativeWork
description: In this dissertation we discuss a number of combinatorial results. These results fall into four broad areas: poset saturation, Ramsey theory, pursuit and evasion, and union-closed families. Chapter 2 is dedicated to the area of poset saturation. Given a finite poset P, we call a family F of subsets of [n] P-saturated if F does not contain an induced copy of P, but adding any other set to F creates an induced copy of P. The size of the smallest P-saturated family with ground set [n] is called the induced saturated number of P, which is denoted by sat∗(n,P). In this chapter we look at four posets: the butterfly, the diamond, the antichain and the poset N . We establish a linear lower bound for the butterfly, a lower bound of(2√2 − o(1))√n for the diamond, a lower bound of √n for the poset N , and the exact saturation number for the 5-antichain and the 6-antichain. Chapter 3 is dedicated to two different Ramsey theory questions. In Section 3.1 we establish a Ramsey characterisation of eventually periodic words. More precisely, for a finite colouring of X∗ (the set of finite words on alphabet X) we say that a factorisation x = u1u2 · · · of an infinite word x is ‘super-monochromatic’ if each word uk1 uk2 · · · ukn, where k1 < · · · < kn, is the same colour. We show that a word x is eventually periodic if and only if for every finite colouring of X∗ there is a suffix of x having a super-monochromatic factorisation. This has been a conjecture for quite some time. In Section 3.2 we investigate the question of whether or not, given a finite colouring of the rationals or the reals, we can find an infinite subset with the property that the set of all its finite sums and products is monochromatic. The main result of this section is the existence of a finite colouring of the rationals with the property that no infinite set whose denominators contain only finitely many primes has the set of all of its finite sums and products monochromatic. In Chapter 4 we explore the game of co…
abstract: In this dissertation we discuss a number of combinatorial results. These results fall into four broad areas: poset saturation, Ramsey theory, pursuit and evasion, and union-closed families. Chapter 2 is dedicated to the area of poset saturation. Given a finite poset P, we call a family F of subsets of [n] P-saturated if F does not contain an induced copy of P, but adding any other set to F creates an induced copy of P. The size of the smallest P-saturated family with ground set [n] is called the induced saturated number of P, which is denoted by sat∗(n,P). In this chapter we look at four posets: the butterfly, the diamond, the antichain and the poset N . We establish a linear lower bound for the butterfly, a lower bound of(2√2 − o(1))√n for the diamond, a lower bound of √n for the poset N , and the exact saturation number for the 5-antichain and the 6-antichain. Chapter 3 is dedicated to two different Ramsey theory questions. In Section 3.1 we establish a Ramsey characterisation of eventually periodic words. More precisely, for a finite colouring of X∗ (the set of finite words on alphabet X) we say that a factorisation x = u1u2 · · · of an infinite word x is ‘super-monochromatic’ if each word uk1 uk2 · · · ukn, where k1 < · · · < kn, is the same colour. We show that a word x is eventually periodic if and only if for every finite colouring of X∗ there is a suffix of x having a super-monochromatic factorisation. This has been a conjecture for quite some time. In Section 3.2 we investigate the question of whether or not, given a finite colouring of the rationals or the reals, we can find an infinite subset with the property that the set of all its finite sums and products is monochromatic. The main result of this section is the existence of a finite colouring of the rationals with the property that no infinite set whose denominators contain only finitely many primes has the set of all of its finite sums and products monochromatic. In Chapter 4 we explore the game of co…
author: Ivan, Maria
language: eng
keywords: Extremal combinatorics, Poset saturation, Ramsey theory
license: https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/4eca863b-1685-4b35-907e-8c4c41bc2186/download
license: https://www.rioxx.net/licenses/all-rights-reserved/
date published: 2023-05-09
date modified: 2026-07-22T22:24:23Z
provider: Cambridge University
publisher: Networked Digital Library of Theses and Dissertations
type: WebPage
source organization: University of Cambridge

PropertyValue
property ID: DOI
value: 10.17863/CAM.99063