The Library
Applications of entropy to extremal problems
Tools
Fitch, Matthew (2018) Applications of entropy to extremal problems. PhD thesis, University of Warwick.
|
PDF
WRAP_Theses_Fitch_2019.pdf - Submitted Version - Requires a PDF viewer. Download (776Kb) | Preview |
Official URL: http://webcat.warwick.ac.uk/record=b3438537~S15
Abstract
The Sidorenko conjecture gives a lower bound on the number of homomorphisms from a bipartite graph to another graph. Szegedy [28] used entropy methods to prove the conjecture in some cases. We will refine these methods to also give lower bounds for the number of injective homomorphisms from a bipartite graph to another bipartite graph, and a lower bound for the number of homomorphisms from a k-partite hypergraph to another k-partite hypergraph, as well as a few other similar problems.
Next is a generalisation of the Kruskal Katona Theorem [19, 17]. We are given integers k < r and families of sets A C N(r) and B N(r-1) such that for every A E A, at least k distinct subset of A of size r - 1 are in B. We then ask the question of what is the minimum size of A as a function of the size of B? In the case where 0 < k < 3, we will be able to find an exact solution. Then for k > 4 we will make a lot of progress towards finding a solution.
The next chapter is to do with Turán-type problems. Given a family of k-hypergraphs F, ex(n;F) is the maximum number of edges an F-free n-vertex k-hypergraph can have. We prove that for a rational r, there exists some finite family F of k-hypergraphs for which ex(n;F) = Ɵ(nk-r) if and only if 0 < r < k - 1 or r = k.
The final chapter will deal with the implicit representation conjecture, in the special case of semi-algebraic graphs. Given a graph in such a family, we want to assign a name to each vertex in such a way that we can recover each edge based only on the names of the two incident vertices. We will first prove that one `obvious' way of storing the information doesn't work. Then we will come up with a way of storing the information that requires O(n1-E) bits per vertex, where E is some small constant depending only on the family.
Item Type: | Thesis (PhD) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Library of Congress Subject Headings (LCSH): | Entropy, Homomorphisms (Mathematics), Extremal problems (Mathematics) | ||||
Official Date: | September 2018 | ||||
Dates: |
|
||||
Institution: | University of Warwick | ||||
Theses Department: | Mathematics Institute | ||||
Thesis Type: | PhD | ||||
Publication Status: | Unpublished | ||||
Supervisor(s)/Advisor: | Pikhurko, Oleg | ||||
Sponsors: | European Research Council | ||||
Format of File: | |||||
Extent: | v, 99 leaves : illustrations | ||||
Language: | eng |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year