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 kpartite hypergraph to another kpartite 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(r1) 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ántype problems. Given a family of khypergraphs F, ex(n;F) is the maximum number of edges an Ffree nvertex khypergraph can have. We prove that for a rational r, there exists some finite family F of khypergraphs for which ex(n;F) = Ɵ(nkr) 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 semialgebraic 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(n1E) 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