Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Publication

A Polynomial Regularity Lemma For Semialgebraic Hypergraphs And Its Applications In Geometry And Property Testing

János Pach
2016
Journal Articles

Abstract

In this paper, we prove several extremal results for geometrically defined hypergraphs. In particular, we establish an improved lower bound, single exponentially decreasing in k, on the best constant delta > 0 such that the vertex classes P-1,...,P-k of every k -partite k -uniform semialgebraic hypergraph H = (P-1 U center dot center dot center dot U P-k, E) with vertical bar E vertical bar >= epsilon ll(j=1)(k) vertical bar P-i vertical bar have, for 1

Official source

https://infoscience.epfl.ch/entities/publication/d4492630-6ca9-4f18-a4f1-6864d7a65261

János Pach
2016
Journal Articles

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/d4492630-6ca9-4f18-a4f1-6864d7a65261

Related concepts (32)

Vertex cover

In graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices that includes at least one endpoint of every edge of the graph. In computer science, the problem of finding a minimum vertex cover is a classical optimization problem. It is NP-hard, so it cannot be solved by a polynomial-time algorithm if P ≠ NP. Moreover, it is hard to approximate – it cannot be approximated up to a factor smaller than 2 if the unique games conjecture is true. On the other hand, it has several simple 2-factor approximations.

BPP (complexity)

In computational complexity theory, a branch of computer science, bounded-error probabilistic polynomial time (BPP) is the class of decision problems solvable by a probabilistic Turing machine in polynomial time with an error probability bounded by 1/3 for all instances. BPP is one of the largest practical classes of problems, meaning most problems of interest in BPP have efficient probabilistic algorithms that can be run quickly on real modern machines.

Independent set (graph theory)

In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set of vertices such that for every two vertices in , there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in . A set is independent if and only if it is a clique in the graph's complement. The size of an independent set is the number of vertices it contains. Independent sets have also been called "internally stable sets", of which "stable set" is a shortening.

Related publications (30)

A Polynomial Regularity Lemma For Semialgebraic Hypergraphs And Its Applications In Geometry And Property Testing

Graph Chatbot

Graph generative deep learning models with an application to circuit topologies

Efficient Continual Finite-Sum Minimization

Reactive collision-free motion generation in joint space via dynamical systems and sampling-based MPC