Publication

A note on discrete lattice-periodic sets with an application to Archimedean tilings

Publications associées (28)

Random walks and forbidden minors III: poly(d epsilon(-1))-time partition oracles for minor-free graph classes

Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and n be the number of vertices of such a graph. Graphs in these classes have hyperfinite decompositions, where, one removes a small ...

IEEE COMPUTER SOC2022

Modeling Network Populations via Graph Distances

Sofia Charlotta Olhede

This article introduces a new class of models for multiple networks. The core idea is to parameterize a distribution on labeled graphs in terms of a Frechet mean graph (which depends on a user-specified choice of metric or graph distance) and a parameter t ...

AMER STATISTICAL ASSOC2021

Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples

Mikhail Kapralov, Slobodan Mitrovic, Ashkan Norouzi Fard, Jakab Tardos

Given a source of iid samples of edges of an input graph G with n vertices and m edges, how many samples does one need to compute a constant factor approximation to the maximum matching size in G? Moreover, is it possible to obtain such an estimate in a sm ...

ASSOC COMPUTING MACHINERY2020

Local approximation of the Maximum Cut in regular graphs

Etienne Michel François Bamas

This paper is devoted to the distributed complexity of finding an approximation of the maximum cut (MAXCUT) in graphs. A classical algorithm consists in letting each vertex choose its side of the cut uniformly at random. This does not require any communica ...

ELSEVIER2020

Ordered Graphs And Large Bi-Cliques In Intersection Graphs Of Curves

János Pach, Istvan Tomon

An ordered graph G(

COMENIUS UNIV2019

Ordered graphs and large bi-cliques in intersection graphs of curves

János Pach, Istvan Tomon

An ordered graph G(

ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD2019

On the Turan number of ordered forests

Gábor Tardos, Istvan Tomon, Dániel József Korándi

An ordered graph H is a simple graph with a linear order on its vertex set. The corresponding Turan problem, first studied by Pach and Tardos, asks for the maximum number ex(

ACADEMIC PRESS INC ELSEVIER SCIENCE2019

No Small Linear Program Approximates Vertex Cover Within a Factor 2-epsilon

Ola Nils Anders Svensson, Abbas Bazzi

The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regev [Khot S, Regev O (2008) Vertex cover might be hard to approximate to within 2 - epsilon. J. Comput. System Sci. 74(3): 335-349 ...

INFORMS2019

Stability results for vertex Turan problems in Kneser graphs

Abhishek Methuku

The vertex set of the Kneser graph K(n, k) is V = (([n])(k)) and two vertices are adjacent if the corresponding sets are disjoint. For any graph F, the largest size of a vertex set U subset of V such that K(n, k)[U] is F-free, was recently determined by Al ...

2019

Analysis of a Canonical Labeling Algorithm for the Alignment of Correlated Erdős-Rényi Graphs

Matthias Grossglauser, Osman Emre Dai, Negar Kiyavash

Graph alignment in two correlated random graphs refers to the task of identifying the correspondence between vertex sets of the graphs. Recent results have characterized the exact information-theoretic threshold for graph alignment in correlated Erdös-Rény ...

Association for Computing Machinery (ACM)2019

New Graph Algorithms via Polyhedral Techniques

Jakub Tarnawski

In this thesis we give new algorithms for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress. S ...

EPFL2019

Embryonic lateral inhibition as optical modes: An analytical framework for mesoscopic pattern formation

Andrew Charles Oates, Jose Negrete Jr

Cellular checkerboard patterns are observed at many stages of embryonic development. We study an analytically tractable model for lateral inhibition and show that the steady states are analogous to optical phonons at the Gamma point, which have the wave nu ...

2019

Local Approximation of the Maximum Cut in Regular Graphs

Etienne Michel François Bamas

This paper is devoted to the distributed complexity of finding an approximation of the maximum cut in graphs. A classical algorithm consists in letting each vertex choose its side of the cut uniformly at random. This does not require any communication and ...

SPRINGER INTERNATIONAL PUBLISHING AG2019

When Stuck, Flip a Coin : New Algorithms for Large-Scale Tasks

Slobodan Mitrovic

Many modern services need to routinely perform tasks on a large scale. This prompts us to consider the following question: How can we design efficient algorithms for large-scale computation? In this thesis, we focus on devising a general strategy to addr ...

EPFL2018

Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover

Slobodan Mitrovic, Mohsen Ghaffari

We present O(log log n)-round algorithms in the Massively Parallel Computation (MPC) model, with a(n) memory per machine, that compute a maximal independent set, a 1 + epsilon approximation of maximum matching, and a 2 + epsilon approximation of minimum ve ...

ASSOC COMPUTING MACHINERY2018

Monochromatic cycle covers in random graphs

Dániel József Korándi

A classic result of Erdos, Gyarfas and Pyber states that for every coloring of the edges of K-n with r colors, there is a cover of its vertex set by at most f(r)=O(r2logr) vertex-disjoint monochromatic cycles. In particular, the minimum number of such cove ...

WILEY2018

On Simplices in Diameter Graphs in R-4

Andrei Kupavskii

A graph G is a diameter graph in R-d if its vertex set is a finite subset in R-d of diameter 1 and edges join pairs of vertices a unit distance apart. It is shown that if a diameter graph G in R-4 contains the complete subgraph K on five vertices, then any ...

Maik Nauka/Interperiodica/Springer2017

A Polynomial Regularity Lemma For Semialgebraic Hypergraphs And Its Applications In Geometry And Property Testing

János Pach

In this paper, we prove several extremal results for geometrically defined hypergraphs. In particular, we establish an improved lower bound, single exponentially decreasing in k, on the best constant delta > 0 such that the vertex classes P-1,...,P-k of ev ...

Society for Industrial and Applied Mathematics2016

On the Zarankiewicz problem for intersection hypergraphs

János Pach

Let d and t be fixed positive integers, and let denote the complete d-partite hypergraph with t vertices in each of its parts, whose hyperedges are the d-tuples of the vertex set with precisely one element from each part. According to a fundamental theorem ...

Academic Press Inc Elsevier Science2016

A Precise Threshold For Quasi-Ramsey Numbers

János Pach

We consider the variation of Ramsey numbers introduced by Erdos and Pach [J. Graph Theory, 7 (1983), pp. 137-147], where instead of seeking complete or independent sets we only seek a t-homogeneous set, a vertex subset that induces a subgraph of minimum de ...

SIAM Publications2015