NDA
Bejelentkezés
Kapcsolat
Density and regularity theorems for semialgebraic hypergraphs 
Tartalom:  http://dx.doi.org/10.1137/1.9781611973730.100 

Archívum:  MTA Könyvtár 
Gyűjtemény: 
Status = Published
Type = Conference or Workshop Item 
Cím: 
Density and regularity theorems for semialgebraic hypergraphs

Létrehozó: 
Fox, Jacob
Pach, János
Suk, Andrew

Dátum: 
2015

Téma: 
QA72 Algebra / algebra

Tartalmi leírás: 
A kuniform semialgebraic hypergraph H is a pair (P, E), where P is a subset of ?d and E is a collection of fctuples (<inf>p1</inf> ? <inf>Pk</inf>) ? P such that (<inf>p1</inf> ? <inf>Pk</inf>) ? E if and only if the kd coordinates of the pis satisfy a boolean combination of a finite number of polynomial inequalities. The complexity of H can be measured by the number and the degrees of these inequalities and the number of variables (coordinates) kd. Several classical results in extremal hypergraph theory can be substantially improved when restricted to semialgebraic hypergraphs. Substantially improving a theorem of Fox, Gromov, Lafforgue, Naor, and Pach, we establish the following "polynomial regularity lemma": For any 0 < ? < 1/2, the vertex set of every kuniform semialgebraic hypergraph H = (P, E) can be partitioned into at most (l/?)c parts P<inf>1</inf>, P2? as equal as possible, such that all but at most an efraction of the ktuples of parts (P<inf>i1</inf>,P<inf>ik</inf>) are homogeneous in the sense that either every ktuple (p<inf>i1</inf>,P<inf>ik</inf>.) ? P<inf>i1</inf> x · · · x P<inf>ik</inf> belongs to E or none of them do. Here c > 0 is a constant that depends on the complexity of H. We also establish an improved lower bound, single exponentially decreasing in k, on the best constant ?> 0 such that the vertex classes P<inf>1</inf>,?P<inf>k</inf> of every kpartite kuniform semialgebraic hypergraph H = (P<inf>1</inf> ? ? ? P<inf>k</inf>, E) with E ? ?IIk<inf>j=1</inf>P<inf>i</inf> have, for 1 ? i ? k, ?P<inf>i</inf>element subsets P?<inf>i</inf>? P<inf>i</inf> satisfying P?<inf>1</inf> x? x P?<inf>k</inf> ? E. The best previously known lower bound on ? due to Bukh and Hubard decreased double exponentially fast in k. We give three geometric applications of our results. In particular, we establish the following strengthening of the socalled sametype lemma of Barany and Valtr: Any disjoint finite sets P<inf>1</inf>,?,P<inf>k</inf> ? ?d (k < d) have for 1 ? i ? k subsets P?<inf>i</inf> of size at least 2o (d3k log k)P<inf>i</inf> with the property that every ktuple formed by taking one point from each P?<inf>i</inf> has the same order type. The above techniques carry over to property testing. We show that for any typical hereditary hypergraph property Q, there is a randomized algorithm with query complexity (1/?)c (o) to determine (with probability at least .99) whether a kuniform semialgebraic hypergraph H = (P, E) with constant description complexity is enear to having property Q, that is, whether one can change at most ?Pk hyperedges of H in order to obtain a hypergraph that has the property. The testability of such properties for general kuniform hypergraphs was first shown by Alon and Shapira (for graphs) and by Rodl and Schacht (for k > 2). The query complexity time of their algorithms is enormous, growing considerably faster than a tower function. Copyright © 2015 by the Society for Industrial and Applied Mathmatics.

Típus: 
Conference or Workshop Item
NonPeerReviewed

Formátum: 
text

Azonosító: 
Fox, Jacob and Pach, János and Suk, Andrew (2015) Density and regularity theorems for semialgebraic hypergraphs. In: Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms, 2015.01.042015.01.06, San Diego.

Kapcsolat: 