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.
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 ...
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 ...
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 ...
Cao and Yuan obtained a Blichfeldt-type result for the vertex set of the edge-to-edge tiling of the plane by regular hexagons. Observing that the vertex set of every Archimedean tiling is the union of translates of a fixed lattice, we take a more general v ...
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 ...
We study the extinction time tau of the contact process started with full occupancy on finite trees of bounded degree. We show that, if the infection rate is larger than the critical rate for the contact process on Z, then, uniformly over all trees of degr ...
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
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(
We develop random graph models where graphs are generated by connecting not only pairs of vertices by edges, but also larger subsets of vertices by copies of small atomic subgraphs of arbitrary topology. This allows for the generation of graphs with extens ...
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 ...
