Működés kezdete:
Működés vége:
Bemutatkozás:
Effective Random Methods in Discrete Mathematics
The probabilistic method, pioneered by Paul Erdős, can show the existence of combinatorial objects without hinting how to construct them effectively. Recent developments concerning the constructive version of Lovsz Local Lemma (LLL) showed how to modify the probabilistic method to make it effective. This proposal lists four research directions in analysis, combinatorics, and cryptography, where this method opened new possibilities to go beyond our present knowledge.
- The measurable version of LLL is the question whether the object, guaranteed by LLL, can additionally be measurable? In some special cases the answer is in the affirmative. What are the constraints which guarantee measurability, and when is it impossible to achieve this? Results are relevant for classical problems of measure group theory.
- A novel approach improving the celebrated sunflower lemma also uses effective probabilistic tools. We will use a similar approach to improve the best estimates for multicolor Ramsey numbers, Schur numbers, and to explore a number of other classical problems.
- Several new phenomena arise in extremal graphs when either the vertices or the edges are linearly ordered. To investigate them we use methods from effective probabilistic sampling. The answers would be relevant in discrete geometry, algorithm design, etc.
- An emerging phenomenon in certain cryptographic primitives including secret sharing will be addressed: relaxing the strict requirements of correctness by allowing negligible errors can lead to significant improvement in efficiency. It is a direct consequence of the mostly unknown structure of the boundary of the entropy region. Using tools and results from the other parts of the project we will explore this boundary giving hints for why, and tools for where and when such efficiency gaps might occur.
Publications:
- Spanners in Planar Domains via Steiner Spanners and non-Steiner Tree Covers
Author(s): Sujoy Bhore, Balázs Keszegh, Andrey Kupavskii, Hung Le, Alexandre Louvet, Dömötör Pálvölgyi, Csaba D. Tóth
Published in: Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2025
Publisher: Society for Industrial and Applied Mathematics
DOI: 10.1137/1.9781611978322.145 - On the Extremal Functions of Acyclic Forbidden 0-1 Matrices
Author(s): Seth Pettie, Gábor Tardos
Published in: Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2024
Publisher: Society for Industrial and Applied Mathematics
DOI: 10.1137/1.9781611977912.45 - A Refutation of the Pach-Tardos Conjecture for 0-1 Matrices
Author(s): Seth Pettie, Gábor Tardos
Published in: Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2025
Publisher: Society for Industrial and Applied Mathematics
DOI: 10.1137/1.9781611978322.152
Csoportvezető:

Tardos Gábor
kutatóprofesszor
kutatóprofesszor
-
Kutatócsoport:GeoScapeERMiD
-
Kutatási osztály:Gráfelmélet
-
Szoba:III/6
-
Telefon:06 1 483-8348
-
Email:tardos.gabor (at) renyi.hu
Munkatársak:

Csirmaz László
tudományos főmunkatárs
tudományos főmunkatárs
-
Kutatócsoport:ERMiD
-
Kutatási osztály:Gráfelmélet
-
Szoba:-
-
Telefon:-
-
Email:csirmaz.laszlo (at) renyi.hu

Jung Attila
tudományos segédmunkatárs
tudományos segédmunkatárs
-
Kutatócsoport:ERMiD
-
Kutatási osztály:Gráfelmélet
-
Szoba:III.18.
-
Telefon:+3614838353
-
Email:jung.attila (at) renyi.hu

Ligeti Péter
tudományos főmunkatárs
tudományos főmunkatárs
-
Kutatócsoport:ERMiD
-
Kutatási osztály:Gráfelmélet
-
Szoba:-
-
Telefon:-
-
Email:ligeti.peter (at) renyi.hu

Pálvölgyi Dömötör
tudományos főmunkatárs
tudományos főmunkatárs
-
Kutatócsoport:ERMiD
-
Kutatási osztály:Gráfelmélet
-
Szoba:III.10.
-
Telefon:+3614838306
-
Email:palvolgyi.domotor (at) renyi.hu