Poset saturation and other combinatorial results

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 cops and robbers on infinite graphs. The main question is: for which graphs can one guarantee that the cop has a winning strategy? In the finite case these graphs are precisely the ‘constructible’ graphs, but the infinite case is not well understood. For example, we exhibit a graph that is cop-win but not constructible. This is the first known such example. On the other hand, every constructible graph is a weak cop win (meaning that the cop can eventually force the robber out of any finite set). We also investigate how this notion relates to the notion of ‘locally constructible’ (every finite graph is contained in a finite constructible subgraph). The main result of this chapter is the construction of a locally constructible graph that is not a weak cop win. Surprisingly, this graph may even be chosen to be locally finite. Finally, in Chapter 5 we discuss the union-closed conjecture which asserts that for any union-closed family of sets, there exists an element of the ground set contained in at least half of the sets of the family. Our attention is on the small sets of union-closed families. More precisely, we construct a class of union-closed families of sets such that the frequency of the elements of the minimal sets is o(1) – so that these elements are not generally in half of the sets of union-closed families.

Name dc:type.qualificationname

Doctor of Philosophy (PhD)

Level dc:type.qualificationlevel

Doctoral

Grantor dc:publisher.institution

University of Cambridge

Year dc:date.issued

2023

Author dc:creator

• Ivan, Maria

Advisor dc:contributor.advisor

• Leader, Imre

• Extremal combinatorics
• Poset saturation
• Ramsey theory

Licence

• https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/4eca863b-1685-4b35-907e-8c4c41bc2186/download
• https://www.rioxx.net/licenses/all-rights-reserved/

Language dc:language

eng

Author Identifier

0000-0003-0817-3777

OAI identifier oai:identifier

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