Minors, Embeddability, and Extremal Problems for Hypergraphs

Uli Wagner ()
Additional contact information
Uli Wagner: ETH Zürich, Institut für Theoretische Informatik

A chapter in Thirty Essays on Geometric Graph Theory, 2013, pp 569-607 from Springer

Abstract: Abstract This is an expository chapter based on two talks given during the Special Semester on Discrete and Computational Geometry, organized by János Pach and Emo Welzl, at the École Polytechnique Fédérale in Lausanne, Switzerland, in the fall of 2010. Our first purpose is to describe a circle of ideas regarding topological extremal problems for simplicial complexes (hypergraphs), and the corresponding phase-transition questions for random complexes (as introduced by Linial and Meshulam). In particular, we discuss some notions of minors pertaining to such questions. Our focus is on k-dimensional complexes that are sparse, i.e., such that the number of k-dimensional simplices is linear in the number of (k − 1)-dimensional simplices. Second, we discuss a notion of higher-dimensional expansion for simplicial complexes, due to Gromov, which is very useful in this context (the same notion of expansion has also arisen independently in the work of Linial, Meshulam, and Wallach on random complexes, and in the work of Newman and Rabinovich on higher-dimensional analogues of finite metrics).

Keywords: Simplicial Complex; Piecewise Linear; Embeddability Problem; Random Complex; Finite Simplicial Complex (search for similar items in EconPapers)
Date: 2013
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4614-0110-0_31

Ordering information: This item can be ordered from
http://www.springer.com/9781461401100

DOI: 10.1007/978-1-4614-0110-0_31

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().