Publication
Letter Graphs and Geometric Grid Classes of Permutations: Characterization and Recognition
Publications associées (24)
Metastability of the Potts Ferromagnet on Random Regular Graphs
We study the performance of Markov chains for the q-state ferromagnetic Potts model on random regular graphs. While the cases of the grid and the complete graph are by now well-understood, the case of random regular graphs has resisted a detailed analysis ...
SPRINGER2023Recoloring subgraphs of K-2n for sports scheduling
The exploration of one-factorizations of complete graphs is the foundation of some classical sports scheduling problems. One has to traverse the landscape of such one-factorizations by moving from one of those to a so-called neighbor one-factorization. Thi ...
ELSEVIER2021Letter graphs and geometric grid classes of permutations: Characterization and recognition
In this paper, we reveal an intriguing relationship between two seemingly unrelated notions: letter graphs and geometric grid classes of permutations. An important property common for both of them is well-quasi-orderability, implying, in a non-constructive ...
ELSEVIER2020The Schur-Erdos problem for sesmi-algebraic colorings
We considerm-colorings of the edges of a complete graph, where each color class is defined semi-algebraically with bounded complexity. The casem= 2 was first studied by Alon et al., who applied this framework to obtain surprisingly strong Ramsey-type resul ...
HEBREW UNIV MAGNES PRESS2020Improved Ramsey-type results for comparability graphs
Istvan Tomon, Dániel József Korándi
Several discrete geometry problems are equivalent to estimating the size of the largest homogeneous sets in graphs that happen to be the union of few comparability graphs. An important observation for such results is that if G is an n-vertex graph that is ...
CAMBRIDGE UNIV PRESS2020Who Started This Rumor? Quantifying the Natural Differential Privacy of Gossip Protocols
Rachid Guerraoui, Hadrien Hendrikx
Gossip protocols (also called rumor spreading or epidemic protocols) are widely used to disseminate information in massive peer-to-peer networks. These protocols are often claimed to guarantee privacy because of the uncertainty they introduce on the node t ...
Schloss Dagstuhl, Leibniz-Zentrum2020Generalized Turan problems for disjoint copies of graphs
Given two graphs H and F, the maximum possible number of copies of H in an F-free graph on n vertices is denoted by ex(n, H, F). We investigate the function ex(n, H, kF), where kF denotes k vertex disjoint copies of a fixed graph F. Our results include cas ...
ELSEVIER2019Ordered Graphs And Large Bi-Cliques In Intersection Graphs Of Curves
An ordered graph G(
COMENIUS UNIV2019Ordered graphs and large bi-cliques in intersection graphs of curves
An ordered graph G(
ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD2019The Erdos-Hajnal conjecture for rainbow triangles
We prove that every 3-coloring of the edges of the complete graph on n vertices without a rainbow triangle contains a set of order ohm(n(1/3) log(2) n) which uses at most two colors, and this bound is tight up to a constant factor. This verifies a conjectu ...
Academic Press Inc Elsevier Science2015