9 papers · 1 filter
Counterexamples to statements on isometric graph coverings
Paul Bastide, Julien Duron, Jędrzej Hodor +2
A connected subgraph of a graph is isometric if it preserves distances. In this short note, we provide counterexamples to several variants of the following general question: When a…
Circular sorting, strong complete mappings and wreath product constructions
Paul Bastide, Anurag Bishnoi, Carla Groenland +2
We continue the study of Adin, Alon and Roichman [arXiv:2502.14398, 2025] on the number of steps required to sort labelled points on a circle by transpositions. Imagine that th…
Cube Height, Cube Width and Related Extremal Problems for Posets
Paul Bastide, Jędrzej Hodor, Hoang La +1
Given a poset , a family of sets indexed by the elements of is called an inclusion representation of if in if and only if…
Smaller universal posets
Paul Bastide, Carla Groenland, Rajko Nenadov
We show that there is a constant such that for each integer , there is a poset on at most elements that contains each -element poset as an (i…
Faithful universal graphs for minor-closed classes
Paul Bastide, Louis Esperet, Carla Groenland +3
It was proved by Huynh, Mohar, Šámal, Thomassen and Wood in 2021 that any countable graph containing every countable planar graph as a subgraph has an infinite clique minor. We pro…
Random embeddings of bounded degree trees with optimal spread
Paul Bastide, Clément Legrand-Duchesne, Alp Müyesser
A seminal result of Komlós, Sárközy, and Szemerédi states that any n-vertex graph G with minimum degree at least (1/2 + α)n contains every n-vertex tree T of bounded degree. Recent…