2026-09-23T13:16:01Zhttps://api.repository.cam.ac.uk/server/oai/request

oai:www.repository.cam.ac.uk:1810/3263622023-12-22T13:50:14Zcom_1810_213747com_1810_256064col_1810_213748

Extremal problems in the cube and the grid and other combinatorial results 10.17863/CAM.73820 Räty, Eero-Pekka Leader, Imre This dissertation contains results from various areas of combinatorics. In Chapters 2, 3 and 4 we consider questions in the area of isoperimetric inequalities. In Chapter 2, we find the exact classification of all subsets A⊆{0,1}^n for which both A and A^c minimise the size of the neighbourhood, which answers a question of Aubrun and Szarek. Harper's inequality implies that the initial segments of the simplicial order satisfy these conditions, but we prove that in general there are non-trivial examples of such sets as well. In Chapter 3, we consider the zero-deletion shadow, which is closely related to the general coordinate deletion shadow introduced by Danh and Daykin. We prove that there is a certain order on [k]^n={0,...,k-1}^n, the n-dimensional grid of side-length k, whose initial segments minimise the size of the zero-deletion shadow. In Chapter 4, we consider the following generalisation of the Kruskal-Katona theorem on [k]^n. For a set A⊆[k]^n, define the d-shadow of A to be the set of all points x obtained from any y∈A by replacing one non-zero coordinate of y by 0. We find an order on [k]^n whose initial segments minimise the size of the d-shadow. In Chapter 5, we consider a certain combinatorial game called Toucher-Isolator game that is played on the edges of a given graph G. The value of the game on G measures how many vertices of G one of the players can achieve by using the edges claimed by her. We find the exact value of the game when G is a path or a cycle of a given length, and we prove that among the trees on n vertices, the path on n vertices has the least value of the game. These results improve previous bounds obtained by Dowden, Kang, Mikalački and Stojaković. In Chapter 6, we consider a problem in Ramsey Theory related to the Hales-Jewett theorem. We prove that for any 2-colouring of [3]^n there exists a monochromatic combinatorial line whose active coordinate set is an interval, provided that n is large. This disproves a conjecture of Conlon and Kamćev. In Chapter 7, we give a construction of a graph G that is P6-induced-saturated, where P6 is the path on 6 vertices. This answers a question of Axenovich and Csikós. University of Cambridge 2021-04-01 Thesis Doctoral Doctor of Philosophy (PhD) eng https://www.repository.cam.ac.uk/handle/1810/326362 https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/440ea35d-2a36-4629-a718-f679e277e212/download 2d2962915eeb011108eaea0d28c590e5 https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/dd36204d-f18b-44cc-9f28-2b9d91642ecb/download 353adac0d1ebdfd65ab16480263c3c87 https://www.rioxx.net/licenses/all-rights-reserved/ Combinatorics Extremal combinatorics Discrete isoperimetric inequalities