Ample simplicial complexes

DOI10.1007/S40879-021-00521-5zbMATH Open1485.05186arXiv2012.01483OpenAlexW4205823744MaRDI QIDQ2115328FDOQ2115328

Michael Farber, Chaim Even-Zohar, Lewis Mead

Publication date: 15 March 2022

Published in: European Journal of Mathematics (Search for Journal in Brave)

Abstract: Motivated by potential applications in network theory, engineering and computer science, we study $r$-ample simplicial complexes. These complexes can be viewed as finite approximations to the Rado complex which has a remarkable property of {it indestructibility,} in the sense that removing any finite number of its simplexes leaves a complex isomorphic to itself. We prove that an $r$-ample simplicial complex is simply connected and $2$-connected for $r$ large. The number $n$ of vertexes of an $r$-ample simplicial complex satisfies $exp(Omega(frac{2}^{r}sqrtr))$. We use the probabilistic method to establish the existence of $r$-ample simplicial complexes with $n$ vertexes for any $n>r{2}^r{2}^{2^r}$. Finally, we introduce the iterated Paley simplicial complexes, which are explicitly constructed $r$-ample simplicial complexes with nearly optimal number of vertexes.

Full work available at URL: https://arxiv.org/abs/2012.01483

Recommendations

• The Rado simplicial complex
• Connectivity of Ample, Conic, and Random Simplicial Complexes
• Large random simplicial complexes. III: The critical dimension.
• Large random simplicial complexes. I
• Large random simplicial complexes. II: The fundamental group

zbMATH Keywords

random simplicial complexample simplicial complexiterated Payley complexRado simplicial complex

Mathematics Subject Classification ID

Combinatorial aspects of simplicial complexes (05E45) Network design and communication in computer systems (68M10)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Probabilities on finite models
• Title not available (Why is that?)
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Title not available (Why is that?)
• Reconstructing graphs as subsumed graphs of hypergraphs, and some self- complementary triple systems
• On Dedekind's Problem: The Number of Isotone Boolean Functions. II
• The poset of hypergraph quasirandomness
• Title not available (Why is that?)
• Universal graphs and universal functions
• The random graph
• Asymmetric graphs
• Equations over finite fields. An elementary approach
• A Constructive Solution to a Tournament Problem
• A class of self-complementary graphs and lower bounds of some ramsey numbers
• Quasi-Random Set Systems
• Homogeneous factorisations of complete graphs with edge-transitive factors
• On Character Sums and Primitive Roots^†
• New lower bounds of some diagonal Ramsey numbers
• All self-complementary symmetric graphs
• Random Simplicial Complexes
• Graphs which contain all small graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Properties of almost all graphs and complexes
• Networks beyond pairwise interactions: structure and dynamics
• Paley graphs satisfy all first-order adjacency axioms
• Cubic and quadruple Paley graphs with the \(n\)-e.c. property
• Vertex-transitive self-complementary uniform hypergraphs
• Vertex-transitive self-complementary uniform hypergraphs of prime order
• Lower bounds of Ramsey numbers based on cubic residues
• Pseudo-random hypergraphs
• On the Brun–Titchmarsh theorem
• The Rado simplicial complex
• Random simplicial complexes in the medial regime
• Quantitative aspects of acyclicity
• Pseudo-random properties of self-complementary symmetric graphs
• Random simplicial complexes, duality and the critical dimension
• Zero-one laws with variable probability

Cited In (3)

• Connectivity of Ample, Conic, and Random Simplicial Complexes
• Large simplicial complexes: universality, randomness, and ampleness
• Occupants in simplicial complexes

This page was built for publication: Ample simplicial complexes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2115328)