Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userBorel Combinatorics of Locally Finite Graphs
208
0
0.0
(
0
)
Authors
Oleg Pikhurko
Ask ChatGPT about the research
No Arabic abstract
We provide a gentle introduction, aimed at non-experts, to Borel combinatorics that studies definable graphs on topological spaces. This is an emerging field on the borderline between combinatorics and descriptive set theory with deep connections to many other areas. After giving some background material, we present in careful detail some basic tools and results on the existence of Borel satisfying assignments: Bore
rate research
Read More
The well-known Galvin-Prikry Theorem states that Borel subsets of the Baire space are Ramsey: Given any Borel subset $mathcal{X}subseteq [omega]^{omega}$, where $[omega]^{omega}$ is endowed with the metric topology, each infinite subset $Xsubseteq omega$ contains an infinite subset $Ysubseteq X$ such that $[Y]^{omega}$ is either contained in $mathcal{X}$ or disjoint from $mathcal{X}$. Kechris, Pestov, and Todorcevic point out in their seminal 2005 paper the dearth of similar results for homogeneous structures. Such results are a necessary step to the larger goal of finding a correspondence between structures with infinite dimensional Ramsey properties and topological dynamics, extending their correspondence between the Ramsey property and extreme amenability. In this article, we prove an analogue of the Galvin-Prikry theorem for the Rado graph. Any such infinite dimensional Ramsey theorem is subject to constraints following from the 2006 work of Laflamme, Sauer, and Vuksanovic. The proof uses techniques developed for the authors work on the Ramsey theory of the Henson graphs as well as some new methods for fusion sequences, used to bypass the lack of a certain amalgamation property enjoyed by the Baire space.
We show that a locally finite Borel graph is nonsmooth if and only if it admits marker sequences which are far from every point. Our proof uses the Galvin-Prikry theorem and the Glimm-Effros dichotomy.
Operads are algebraic devices offering a formalization of the concept of operations with several inputs and one output. Such operations can be naturally composed to form bigger and more complex ones. Coming historically from algebraic topology, operads intervene now as important objects in computer science and in combinatorics. The theory of operads, together with the algebraic setting and the tools accompanying it, promises advances in these two areas. On the one hand, operads provide a useful abstraction of formal expressions, and also, provide connections with the theory of rewrite systems. On the other hand, a lot of operads involving combinatorial objects highlight some of their properties and allow to discover new ones. This book presents the theory of nonsymmetric operads under a combinatorial point of view. It portrays the main elements of this theory and the links it maintains with several areas of computer science and combinatorics. A lot of examples of operads appearing in combinatorics are studied and some constructions relating operads with known algebraic structures are presented. The modern treatment of operads consisting in considering the space of formal power series associated with an operad is developed. Enrichments of nonsymmetric operads as colored, cyclic, and symmetric operads are reviewed. This text is addressed to any computer scientist or combinatorist who looks a complete and a modern description of the theory of nonsymmetric operads. Evenly, this book is intended to an audience of algebraists who are looking for an original point of view fitting in the context of combinatorics.
We settle a question posed by G. Eric Moorhouse on the model theory and existence of locally finite generalized quadrangles. In this paper, we completely handle the case in which the generalized quadrangles have a countable number of elements.
A graph $G$ is said to be ubiquitous, if every graph $Gamma$ that contains arbitrarily many disjoint $G$-minors automatically contains infinitely many disjoint $G$-minors. The well-known Ubiquity conjecture of Andreae says that every locally finite graph is ubiquitous. In this paper we show that locally finite graphs admitting a certain type of tree-decomposition, which we call an extensive tree-decomposition, are ubiquitous. In particular this includes all locally finite graphs of finite tree-width, and also all locally finite graphs with finitely many ends, all of which have finite degree. It remains an open question whether every locally finite graph admits an extensive tree-decomposition.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
