{"id":{"repo_id":"cambridge","oai_identifier":"oai:www.repository.cam.ac.uk:1810/382510"},"canonical_url":"https://search.dev.ndltd.org/etd/cambridge/oai:www.repository.cam.ac.uk:1810/382510","repository":{"repo_id":"cambridge","name":"Cambridge University","base_url":"https://api.repository.cam.ac.uk/server/oai/request"},"display":{"title":"Some Results in Combinatorics and Combinatorial Geometry","abstract":"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.","abstract_html":"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 <span class=\"etd-inline-math\">x<sub>A</sub></span> 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&#x27;. We prove that the closed convex hull $\\overline{conv}(ψ_n)<span class=\"etd-inline-math\"> is equal to the cone given by the uniform cover inequalities. We also show that conv(ψ<sub>n</sub>) 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&#x27; condition? Wang showed that the so-called `greedy&#x27; tree maximises this quantity, while an `alternating greedy&#x27; 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 </span>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.","abstract_has_math":true,"creators":["Randelovic, Zarko"],"institution":"University of Cambridge","degree_name":"Doctor of Philosophy (PhD)","degree_level":"Doctoral","degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":["Leader, Imre"],"committee_chairs":[],"committee_members":[],"year":2024,"date_issued":"2024-10-23","date_published":"2024-10-23","updated_at":"2026-07-22T22:24:18Z","subjects":["Combinatorics","Combinatorial Geometry"],"languages":["eng"],"rights":[],"rights_urls":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/fc039acb-72a4-473a-ab34-1398c60ba70f/download","https://creativecommons.org/licenses/by/4.0/"],"identifier_entries":[]},"links":{"outbound_url":"https://doi.org/10.17863/CAM.117286","outbound_label":"DOI","outbound_source":"dc:identifier.doi"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Leader, Imre"]},{"key":"dc:contributor.sponsor","label":"Sponsor","values":["My PhD was funded by the Department of Pure Mathematics and Mathematical Statistics and the Cmabridge Trust. I am very grateful to them."]},{"key":"dc:creator","label":"Author","values":["Randelovic, Zarko"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.issued","label":"Date","values":["2024-10-23"]},{"key":"dc:publisher.institution","label":"Dc Publisher Institution","values":["University of Cambridge"]},{"key":"dc:relation.isreferencedby.uri","label":"Dc Relation Isreferencedby URI","values":["https://www.repository.cam.ac.uk/handle/1810/382510"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"dc:type.qualificationlevel","label":"Dc Type Qualificationlevel","values":["Doctoral"]},{"key":"dc:type.qualificationname","label":"Dc Type Qualificationname","values":["Doctor of Philosophy (PhD)"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Combinatorics","Combinatorial Geometry"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/fc039acb-72a4-473a-ab34-1398c60ba70f/download","https://creativecommons.org/licenses/by/4.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.doi","label":"DOI","values":["https://doi.org/10.17863/CAM.117286"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/834c439d-aab8-405d-a636-4db2d49e600b/download"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:format.checksum.md5","label":"Dc Format Checksum Md5","values":["87eda9de84448d1f82354d60eee3eb5f","cb7e0c6707421fd45c93a335079a9494"]},{"key":"dc:title","label":"Title","values":["Some Results in Combinatorics and Combinatorial Geometry"]}]}],"canonical_facts":{"dc:contributor.advisor":["Leader, Imre"],"dc:contributor.sponsor":["My PhD was funded by the Department of Pure Mathematics and Mathematical Statistics and the Cmabridge Trust. I am very grateful to them."],"dc:creator":["Randelovic, Zarko"],"dc:date.issued":["2024-10-23"],"dc:description.abstract":["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."],"dc:format.checksum.md5":["87eda9de84448d1f82354d60eee3eb5f","cb7e0c6707421fd45c93a335079a9494"],"dc:identifier.doi":["https://doi.org/10.17863/CAM.117286"],"dc:identifier.uri":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/834c439d-aab8-405d-a636-4db2d49e600b/download"],"dc:language":["eng"],"dc:publisher.institution":["University of Cambridge"],"dc:relation.isreferencedby.uri":["https://www.repository.cam.ac.uk/handle/1810/382510"],"dc:rights":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/fc039acb-72a4-473a-ab34-1398c60ba70f/download","https://creativecommons.org/licenses/by/4.0/"],"dc:subject":["Combinatorics","Combinatorial Geometry"],"dc:title":["Some Results in Combinatorics and Combinatorial Geometry"],"dc:type":["Thesis"],"dc:type.qualificationlevel":["Doctoral"],"dc:type.qualificationname":["Doctor of Philosophy (PhD)"]},"updated_at":"2026-07-22T22:24:18Z"}