Some Results in Combinatorics and Combinatorial Geometry

This dissertation contains various results in combinatorics and combnatorial geometry. In Chapter 2, we discuss union-closed families. For a given number of k-sets, how should we choose them so as to minimise the union-closed family that they generate? In this chapter we show that, if $\mathcal{A}$ is a family of k-sets of size $\binom{t}{k}$, and t is sufficiently large, then the union-closed family generated by $\mathcal{A}$ has size at least that generated by the family of all k-sets from a t-set. This proves (for this size of family) a conjecture of Roberts. We also give some other results, including a new proof of the result of Leck, Roberts and Simpson that exactly determines this minimum (for all sizes of the family) when k=2. In Chapter 3, we discuss inequalities on projected volumes in $\mathbb{R}ⁿ$. Given 2ⁿ-1 real numbers x_A indexed by the non-empty subsets A ⊂ {1,...,n}$, is it possible to construct a body $T ⊂ \mathbb{R}^n$ such that $x_A=log |T_A|$ where $|T_A|$ is the |A|-dimensional volume of the projection of T onto the subspace spanned by the axes in A? We denote by $ψ_n$ the set of all vectors x for which there is a body T such that $x_A=log |T_A|$ for all A. Bollobás and Thomason showed that $ψ_n$ is contained in the polyhedral cone defined by the class of ‘uniform cover inequalities'. We prove that the closed convex hull $\overline{conv}(ψ_n) is equal to the cone given by the uniform cover inequalities. We also show that conv(ψ_n) is not closed for n ≥ 4. Our result answers a conjecture of Tan and Zeng. In Chapter 4, we discuss a problem on intersecting families of graphs. We show that a family of oriented graphs on n vertices such that any two have strongly-connected intersection has size at most 1/3ⁿ of all oriented graphs. We also show that a family of graphs such that any two have Hamiltonian intersection has size at most 1/2ⁿ of all graphs, verifying a conjecture of Berger, Berkowitz, Devlin, Doppelt, Durham, Murthy and Vemuri. In Chapter 5, we discuss a problem on extremal trees. Among all trees on n vertices with a given degree sequence, how do we maximise or minimise the sum of f(deg x, deg y) over all adjacent pairs of vertices x and y, where f is a fixed symmetric function satisfying a `monotonicity' condition? Wang showed that the so-called `greedy' tree maximises this quantity, while an `alternating greedy' tree minimises it. We solve the inverse problem and characterize precisely which trees are extremal for these two problems. In Chapter 6, we discuss a game on a square grid. Two players take it turn to claim empty cells from an n × n grid. The first player (if any) to occupy a transversal (a set of n cells having no two cells in the same row or column) is the winner. In this chapter we show that for n ≥ 4, the first player has a winning strategy. This answers a question of Erickson. In Chapter 7, we discuss a problem on distances in metric spaces. Given functions f,g: [n] → [n], do there exist n points A₁,A₂,\ldots,A_n$ in some metric space such that $A_{f(i)},A_{g(i)}$ are the points closest and farthest from point $A_i$? In this chapter we characterize precisely which pairs of functions have this property. Define m(k) to be the maximal number such that any pair of functions f,g:[m(k)] → [m(k)] realizable in some metric space is also realizable in $\mathbb{R}^k$. We show that m(k) grows exponentially in k. This answers a question of Croft. We also discuss what happens when looking at minimal and maximal distances separately.

Name dc:type.qualificationname

Doctor of Philosophy (PhD)

Level dc:type.qualificationlevel

Doctoral

Grantor dc:publisher.institution

University of Cambridge

Year dc:date.issued

2024

Author dc:creator

• Randelovic, Zarko

Advisor dc:contributor.advisor

• Leader, Imre

• Combinatorics
• Combinatorial Geometry

Licence

• https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/fc039acb-72a4-473a-ab34-1398c60ba70f/download
• https://creativecommons.org/licenses/by/4.0/

Language dc:language

eng

DOI dc:identifier.doi

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

OAI identifier oai:identifier

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