The Library
Limit structures and property testing
Tools
Klimošová, Tereza (2015) Limit structures and property testing. PhD thesis, University of Warwick.
|
PDF
WRAP_THESIS_Klimosova_2015.pdf - Submitted Version - Requires a PDF viewer. Download (1409Kb) | Preview |
Official URL: http://webcat.warwick.ac.uk/record=b2872054~S1
Abstract
In the thesis, we study properties of large combinatorial objects. We analyze these objects from two different points of view.
The first aspect is analytic - we study properties of limit objects of combinatorial structures. We investigate when graphons (limits of graphs) and permutons (limits of permutations) are finitely forcible, i.e., when they are uniquely determined by finitely many densities of their substructures. We give examples of families of permutons that are finitely forcible but the associated graphons are not and we disprove a conjecture of Lovasz and Szegedy on the dimension of the space of typical vertices of a finitely forcible graphon. In particular, we show that there exists a finitely forcible graphon W such that the topological spaces T(W) and T(W) have infinite Lebesgue covering dimension.
We also study the dependence between densities of substructures. We prove a permutation analogue of the classical theorem of Erdos, Lovasz and Spencer on the densities of connected subgraphs in large graphs.
The second aspect of large combinatorial objects we concentrate on is algorithmic|we study property testing and parameter testing. We show that there exists a bounded testable permutation parameter that is not finitely forcible and that every hereditary permutation property is testable (in constant time) with respect to the Kendall's tau distance, resolving a conjecture of Kohayakawa.
Item Type: | Thesis (PhD) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Library of Congress Subject Headings (LCSH): | Combinatorial analysis | ||||
Official Date: | September 2015 | ||||
Dates: |
|
||||
Institution: | University of Warwick | ||||
Theses Department: | Mathematics Institute | ||||
Thesis Type: | PhD | ||||
Publication Status: | Unpublished | ||||
Supervisor(s)/Advisor: | Králʼ, Daniel | ||||
Extent: | vii, 96 leaves | ||||
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