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

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

We establish new results on the weak containment of quasi-regular and Koopman representations of a second countable locally compact group G

G

associated with nonsingular G

G

-spaces. We deduce that any two boundary representations of a hyperbolic locally ...

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 ...

We study a model of crowd motion following a gradient vector field, with possibly additional interaction terms such as attraction/repulsion, and we present a numerical scheme for its solution through a Lagrangian discretization. The density constraint of t ...

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 ...

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 ...

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 ...

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(

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

2-level polytopes naturally appear in several areas of pure and applied mathematics, including combinatorial optimization, polyhedral combinatorics, communication complexity, and statistics. In this paper, we present a study of some 2-level polytopes arisi ...

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 ...

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 ...

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 ...

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 ...

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

Chat with Graph Search

A type I conjecture and boundary representations of hyperbolic groups

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

Lagrangian Discretization Of Crowd Motion And Linear Diffusion

Modeling Network Populations via Graph Distances

Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples

Local approximation of the Maximum Cut in regular graphs

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

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

On the Turan number of ordered forests

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

Stability results for vertex Turan problems in Kneser graphs

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

New Graph Algorithms via Polyhedral Techniques

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

Local Approximation of the Maximum Cut in Regular Graphs

On 2-Level Polytopes Arising In Combinatorial Settings

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

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

Monochromatic cycle covers in random graphs

On Simplices in Diameter Graphs in R-4