## Abstract

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 ℝ^{d} there is a point covered by at least a c(H)-fraction of the simplices induced by the images of its hyperedges. In [18], motivated by the search for an analogue of the notion of graph expansion for higher dimensional simplicial complexes, it was asked whether or not there exists a sequence {H_{n}}_{n=1} ^{∞} of arbitrarily large (d + 1)-uniform hypergraphs with bounded degree, for which inf_{n≥1} c(H_{n}) > 0. 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 d and any ε > 0, there exists K = K(ε,d) ≥ d + 1 satisfying the following condition. For any k ≥ K, for any point q ∈ ℝ^{d} and for any finite Borei measure μ on ℝ^{d} with respect to which every hyperplane has measure 0, there is a partition ℝ^{d} = A_{1} ∪. .. ∪ A_{k} into k measurable parts of equal measure such that all but at most an ε-fraction of the (d + 1)-tuples A_{i1},..., A _{id+1} have the property that either all simplices with one vertex in each A_{ij} contain q or none of these simplices contain q.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011 |

Pages | 1188-1197 |

Number of pages | 10 |

State | Published - May 12 2011 |

Event | 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011 - San Francisco, CA, United States Duration: Jan 23 2011 → Jan 25 2011 |

### Other

Other | 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011 |
---|---|

Country | United States |

City | San Francisco, CA |

Period | 1/23/11 → 1/25/11 |

## All Science Journal Classification (ASJC) codes

- Software
- Mathematics(all)