Large Combinatorial Objects: Extremal Structure and Quasirandomness

点击翻译按钮获取中文摘要

Large discrete structures pervade nearly every facet of the modern world. Disordered particle systems, social networks and the human brain can all be viewed as massive networks composed of individual nodes with links between them. The challenge of analyzing enormous data sets gives rise to a wealth of exciting mathematical problems. For example, how do we model a large data set in an intelligible way while preserving its crucial information? Answers to this question for many structures can be found in the recently developed "limit" theory for combinatorial objects. A key idea is to view a large data set, e.g. a network, not as a discrete structure, but as a discrete approximation of a richer continuous object. For an analogy, physical objects that we encounter in our everyday lives are essentially networks of particles, but it is rarely useful to think of them in that way. We select a gem based on continuous characteristics like colour and clarity, not on the way it is arranged at a molecular level. Similarly, a large network can be modeled by a continuous analytic object in a way that preserves many of its most vital features. At the heart of combinatorial limit theory is the concept of quasirandomness. A central tenet of quasirandomness is that many seemingly different properties which hold with high probability in a random combinatorial object turn out to be equivalent to one another. An object is said to be "quasirandom" if it has any of these properties. One problem in the proposal is to identify local patterns which characterize quasirandomness in a large permutation. Results of this type have direct applications to the area of independence testing (i.e. testing the null hypothesis) in nonparametric statistics initiated by Kendall and Hoeffding in the 30s and 40s. This viewpoint suggests several intriguing high-dimensional extensions, e.g., what sorts of local statistics characterize mutual independence of a triple of random variables? Another focus is on the influence of local pattern frequencies on global quasirandomness in graphs. A classical result in the area is the Goodman Bound which asserts that the number of monochromatic triangles in a colouring of the edges of a complete graph with two colours is approximately minimized by a random colouring. Statements of this type are motivated by applications in Ramsey Theory, where substantial breakthroughs have come from exploiting effective quasirandomness estimates (including the Goodman Bound itself). This area is linked to the famous Sidorenko Conjecture on frequencies of bipartite subgraphs. My approach involves blending combinatorial arguments with methods from other areas such as analysis, probability and optimization. This versatile toolkit will be applied to a multitude of extremal problems in graphs, permutations, tournaments, directed graphs and hypergraphs. This aim of this work is to develop powerful and widely applicable tools for extracting structure from large data sets.