7 papers
A universal threshold for geometric embeddings of trees
Dylan J. Altschuler, Pandelis Dodos, Konstantin Tikhomirov +1
A graph is geometrically embeddable into a normed space when there is a mapping such that if and only if , f…
Uniformity of extremal graph-codes
Noé de Rancourt, Pandelis Dodos, Konstantinos Tyros
It is an important fact that extremal discrete structures -- that is, discrete structures of maximal size among those that avoid certain configurations -- exhibit strong pseudorand…
Metric Poincaré inequalities for graphs
Dylan J. Altschuler, Pandelis Dodos, Konstantin Tikhomirov +1
This article obtains purely metric counterparts of cornerstone results in the theory of embedding graphs into normed spaces. Our first main result is a metric analogue of MatouÅ¡ek…
Discrete Poincaré inequalities and universal approximators for random graphs
Dylan J. Altschuler, Pandelis Dodos, Konstantin Tikhomirov +1
Nonlinear Poincaré inequalities are indispensable tools in the study of dimension reduction and low-distortion embeddings of graphs into metric spaces, and have found remarkable al…
Forbidden sparse intersections
Pandelis Dodos, Miltiadis Karamanlis
Let be a positive integer, let , and let be a nonnegative integer. We prove that if $\mathcal{F},\mathcal{G}\subseteq…
A combinatorial approach to nonlinear spectral gaps
Dylan J. Altschuler, Pandelis Dodos, Konstantin Tikhomirov +1
A seminal open question of Pisier and Mendel--Naor asks whether every degree-regular graph which satisfies the classical discrete Poincaré inequality for scalar functions, also sa…