
On the number of hyperedges in the hypergraph of lines and pseudodiscs
Consider the hypergraph whose vertex set is a family of n lines in gener...
read it

At most 4.47^n stable matchings
We improve the upper bound for the maximum possible number of stable mat...
read it

An improved constant factor for the unit distance problem
We prove that the number of unit distances among n planar points is at m...
read it

Almostmonochromatic sets and the chromatic number of the plane
In a colouring of R^d a pair (S,s_0) with S⊆R^d and with s_0∈ S is almos...
read it

On Communication Complexity of Fixed Point Computation
Brouwer's fixed point theorem states that any continuous function from a...
read it

Adaptive Majority Problems for Restricted Query Graphs and for Weighted Sets
Suppose that the vertices of a graph G are colored with two colors in an...
read it

The range of nonlinear natural polynomials cannot be contextfree
Suppose that some polynomial f with rational coefficients takes only nat...
read it

Unlabeled Compression Schemes Exceeding the VCdimension
In this note we disprove a conjecture of Kuzmin and Warmuth claiming tha...
read it

Plane drawings of the generalized Delaunaygraphs for pseudodisks
We study general Delaunaygraphs, which are a natural generalizations of...
read it

Coloring DelaunayEdges and their Generalizations
We consider geometric graphs whose vertex set is a finite set of points ...
read it

Acyclic orientations with degree constraints
In this note we study the complexity of some generalizations of the noti...
read it

Complexity of Domination in Triangulated Plane Graphs
We prove that for a triangulated plane graph it is NPcomplete to determ...
read it
Dömötör Pálvölgyi
is this you? claim profile