Problems and results on linear hypergraphs

In this thesis, we tackle several problems involving the study of 3-uniform, linear hypergraphs satisfying some additional structural constraint. We begin with a problem of Hrushovski concerning Latin squares satisfying a partial associativity condition. From an $n\times n$ Latin square $A$ one can define a binary operation $\circ:[n]\times[n]\to [n]$, and $\circ$ is associative if and only if $A$ is a group multiplication table. Hrushovski asked whether, if $\circ$ is only associative a positive proportion of the time, $A$ must still in some sense be close to a group multiplication table. This problem manifests a well-studied combinatorial theme, in which a local structural constraint is relaxed (first to a `99$\%$' version and then to a `1$\%$' version) and the global consequences of the relaxed constraints are analysed. We show that the partial associativity condition is sufficient to deduce powerful global information, allowing us to find within $A$ a large subset with group-like structure. Since Latin squares can be regarded as 3-uniform, linear hypergraphs, and the partial associativity condition can be formulated in terms of the count of a particular subhypergraph, we are able to apply purely combinatorial methods to a problem that touches algebra, model theory and geometric group theory. We then take this problem further. A condition due to Thomsen provides a combinatorial constraint which, if satisfied by the Latin square $A$, proves that $A$ is in fact the multiplication table of an abelian group. It is then natural to ask whether a relaxed version of this result is also attainable, and by extending our methods we are able to prove a result of this flavour. Since the combinatorial obstructions to commutativity of $\circ$ are far more complex than those for associativity, topological complications arise that are not present in the earlier work. We also study a problem of Loh concerning sequences of triples of integers from $[n]$ satisfying a certain `increasing' property. Loh studied the maximum length of such a sequence, improving a trivial upper bound of n² to n²/\exp(\log^*n) using the triangle removal lemma and conjecturing that a natural construction of length n^3/2 is best possible. We provide the first power-type improvement to the upper bound, showing that there exists ε>0 such that the length is bounded by n^2-ε. By viewing the triples as edges in a 3-uniform hypergraph, the increasing property shows that the hypergraph is linear and provides further restrictions in terms of forbidden subhypergraphs. By considering this formulation, we provide links to various important open problems including the Brown--Erd\H os--S\'os conjecture. Finally, we present a collection of shorter results. In work connecting to the earlier chapters, we resolve the Brown--Erd\H os--S\'os conjecture in the context of hypergraphs with a group structure, and show moreover that subsets of group multiplication tables exhibit local density far beyond what can be hoped for in general. In work less closely connected to the main theme of the thesis, we also answer a question of Leader, Mili\'cevi\'c and Tan concerning partitions of boxes, consider a problem on projective cubes in \mathbb{Z}_2ⁿ, and resolve a conjecture concerning a diffusion process on graphs.

Name dc:type.qualificationname

Doctor of Philosophy (PhD)

Level dc:type.qualificationlevel

Doctoral

Grantor dc:publisher.institution

University of Cambridge

Year dc:date.issued

2019

Author dc:creator

• Long, Jason

Advisor dc:contributor.advisor

• Gowers, Timothy

• Hypergraphs
• Combinatorics
• Graph Theory

Licence

• https://www.repository.cam.ac.uk/bitstreams/974d3fc5-23b2-4b3e-b611-f10ed93ba080/download
• http://purl.org/NET/rdflicense/allrightsreserved

Language dc:language

eng

DOI dc:identifier.doi

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

OAI identifier oai:identifier

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