Pavel Pudl'ak

collaborators

3 papers

math.CO2024

A lower bound on the Ramsey number $R_{k} (k + 1, k + 1)$

Pavel Pudlák, Vojtěch Rödl, William J. Wesley

We will prove that $R_{k} (k + 1, k + 1) \geq 4 t w_{⌊ k /4 ⌋ - 3} (2)$ , where $tw$ is the tower function defined by $tw_{1} (x) = x$ and $tw_{i + 1} (x) = 2^{tw_{i} (x)}$ . We also give pro…

cs.CC2024

Local Enumeration and Majority Lower Bounds

Mohit Gurumukhani, Ramamohan Paturi, Pavel Pudlák +2

Depth-3 circuit lower bounds and $k$ -SAT algorithms are intimately related; the state-of-the-art $Σ_{3}^{k}$ -circuit lower bound and the $k$ -SAT algorithm are based on the same combina…

math.CO2024

Colorings of $k$ -sets with low discrepancy on small sets

Pavel Pudlák, Vojtěch Rödl

For $0 < δ \leq 1$ , let $R_{k} (m; δ)$ denote the smallest $N$ such that every coloring of $k$ -element subsets by two colors yields an $m$ -element set $M$ with relative discrepancy $δ$ , w…

A lower bound on the Ramsey number Rk​(k+1,k+1)

Local Enumeration and Majority Lower Bounds

Colorings of k-sets with low discrepancy on small sets

A lower bound on the Ramsey number $R_{k} (k + 1, k + 1)$

Colorings of $k$ -sets with low discrepancy on small sets