Overlap properties of geometric expanders
The overlap number of a finite (d + 1)-uniform hypergraph H is the largest constant c(H) ∈ (0, 1] such that no matter how we map the vertices of H into ℝ[superscript d], there is a point covered by at least a c(H)-fraction of the simplices induced by the images of its hyperedges. Motivated by the se...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Walter de Gruyter
2013
|
| Online Access: | http://hdl.handle.net/1721.1/80829 |
| _version_ | 1811077253644156928 |
|---|---|
| author | Fox, Jacob Gromov, Mikhail Lafforgue, Vincent Naor, Assaf Pach, Janos |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Fox, Jacob Gromov, Mikhail Lafforgue, Vincent Naor, Assaf Pach, Janos |
| author_sort | Fox, Jacob |
| collection | MIT |
| description | The overlap number of a finite (d + 1)-uniform hypergraph H is the largest constant c(H) ∈ (0, 1] such that no matter how we map the vertices of H into ℝ[superscript d], there is a point covered by at least a c(H)-fraction of the simplices induced by the images of its hyperedges. Motivated by the search for an analogue of the notion of graph expansion for higher dimensional simplicial complexes, we address the question whether or not there exists a sequence of arbitrarily large (d + 1)-uniform hypergraphs with bounded degree for which . Using both random methods and explicit constructions, we answer this question positively by constructing infinite families of (d + 1)-uniform hypergraphs with bounded degree such that their overlap numbers are bounded from below by a positive constant c = c(d). We also show that, for every d, the best value of the constant c = c(d) that can be achieved by such a construction is asymptotically equal to the limit of the overlap numbers of the complete (d + 1)-uniform hypergraphs with n vertices, as n → ∞. For the proof of the latter statement, we establish the following geometric partitioning result of independent interest. For any h, s and any ɛ > 0, there exists K = K(ɛ, h, s) satisfying the following condition. For any k ≧ K and for any semi-algebraic relation R on h-tuples of points in a Euclidean space ℝ[superscript d] with description complexity at most s, every finite set P ⫅ ℝ[superscript d] has a partition P = P[subscript 1] ∪ ⋯ ∪ P[subscript k] into k parts of sizes as equal as possible such that all but at most an ɛ-fraction of the h-tuples (P[subscript i1], … , P[subscript ih]) have the property that either all h-tuples of points with one element in each Pij are related with respect to R or none of them are. |
| first_indexed | 2024-09-23T10:40:06Z |
| format | Article |
| id | mit-1721.1/80829 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:40:06Z |
| publishDate | 2013 |
| publisher | Walter de Gruyter |
| record_format | dspace |
| spelling | mit-1721.1/808292022-09-27T14:06:38Z Overlap properties of geometric expanders Fox, Jacob Gromov, Mikhail Lafforgue, Vincent Naor, Assaf Pach, Janos Massachusetts Institute of Technology. Department of Mathematics Fox, Jacob The overlap number of a finite (d + 1)-uniform hypergraph H is the largest constant c(H) ∈ (0, 1] such that no matter how we map the vertices of H into ℝ[superscript d], there is a point covered by at least a c(H)-fraction of the simplices induced by the images of its hyperedges. Motivated by the search for an analogue of the notion of graph expansion for higher dimensional simplicial complexes, we address the question whether or not there exists a sequence of arbitrarily large (d + 1)-uniform hypergraphs with bounded degree for which . Using both random methods and explicit constructions, we answer this question positively by constructing infinite families of (d + 1)-uniform hypergraphs with bounded degree such that their overlap numbers are bounded from below by a positive constant c = c(d). We also show that, for every d, the best value of the constant c = c(d) that can be achieved by such a construction is asymptotically equal to the limit of the overlap numbers of the complete (d + 1)-uniform hypergraphs with n vertices, as n → ∞. For the proof of the latter statement, we establish the following geometric partitioning result of independent interest. For any h, s and any ɛ > 0, there exists K = K(ɛ, h, s) satisfying the following condition. For any k ≧ K and for any semi-algebraic relation R on h-tuples of points in a Euclidean space ℝ[superscript d] with description complexity at most s, every finite set P ⫅ ℝ[superscript d] has a partition P = P[subscript 1] ∪ ⋯ ∪ P[subscript k] into k parts of sizes as equal as possible such that all but at most an ɛ-fraction of the h-tuples (P[subscript i1], … , P[subscript ih]) have the property that either all h-tuples of points with one element in each Pij are related with respect to R or none of them are. National Science Foundation (U.S.). Graduate Research Fellowship Program Princeton University (Centennial Fellowship) 2013-09-20T15:13:47Z 2013-09-20T15:13:47Z 2011-11 2011-02 Article http://purl.org/eprint/type/JournalArticle 1435-5345 0075-4102 http://hdl.handle.net/1721.1/80829 Fox, Jacob, Mikhail Gromov, Vincent Lafforgue, Assaf Naor, and Janos Pach. “Overlap properties of geometric expanders.” Journal für die reine und angewandte Mathematik (Crelles Journal) 2012, no. 671 (January 2012). en_US http://dx.doi.org/10.1515/crelle.2011.157 Journal für die reine und angewandte Mathematik (Crelles Journal) Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Walter de Gruyter MIT web domain |
| spellingShingle | Fox, Jacob Gromov, Mikhail Lafforgue, Vincent Naor, Assaf Pach, Janos Overlap properties of geometric expanders |
| title | Overlap properties of geometric expanders |
| title_full | Overlap properties of geometric expanders |
| title_fullStr | Overlap properties of geometric expanders |
| title_full_unstemmed | Overlap properties of geometric expanders |
| title_short | Overlap properties of geometric expanders |
| title_sort | overlap properties of geometric expanders |
| url | http://hdl.handle.net/1721.1/80829 |
| work_keys_str_mv | AT foxjacob overlappropertiesofgeometricexpanders AT gromovmikhail overlappropertiesofgeometricexpanders AT lafforguevincent overlappropertiesofgeometricexpanders AT naorassaf overlappropertiesofgeometricexpanders AT pachjanos overlappropertiesofgeometricexpanders |