4 papers · 1 filter
Bisection width, max-cut and internal partitions of 5-regular graphs
Endre Csóka, Panna Tímea Fekete, Zoltán Lóránt Nagy +1
In this paper, we present a new factor of IID process based on the local algorithm introduced by Díaz, Serna, and Wormald (2007). This new approach allows us to improve the previou…
FIID homomorphisms and entropy inequalities
Endre Csoka, Zoltan Vidnyanszky
We investigate the existence of FIID homomorphisms from regular trees to finite graphs. Using entropy inequalities we show that there are graphs with arbitrarily large chromatic nu…
Block partitions in higher dimensions
Endre Csóka
Consider a set which is 1-dense, namely, it intersects every unit ball. We show that we can get from any point to any other point in in …
Finding cliques and dense subgraphs using edge queries
Endre Csóka, András Pongrácz
We consider the problem of finding a large clique in an Erdős--Rényi random graph where we are allowed unbounded computational time but can only query a limited number of edges. Re…