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.
Several discrete geometry problems are equivalent to estimating the size of the largest homogeneous sets in graphs that happen to be the union of few comparability graphs. An important observation for such results is that if G is an n-vertex graph that is ...
The Boolean lattice (2[n],subset of) is the family of all subsets of [n]={1,MIDLINE HORIZONTAL ELLIPSIS,n}, ordered by inclusion. Let P be a partially ordered set. We prove that if n is sufficiently large, then there exists a packing P of copies of P in (2 ...
Let P be a partially ordered set. The function La* (n, P) denotes the size of the largest family F subset of 2([n]) that does not contain an induced copy of P. It was proved by Methuku and Palvolgyi that there exists a constant C-P (depending only on P) su ...
Two subsets A,B of an n-element ground set X are said to be crossing, if none of the four sets AB, A\B, B\A and X(AB) are empty. It was conjectured by Karzanov and Lomonosov forty years ago that if a family F of subsets of X does not contain k pairwise cr ...
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(
Let P be a partially ordered set. If the Boolean lattice (2[n],⊂) can be partitioned into copies of P for some positive integer n, then P must satisfy the following two trivial conditions: (1) the size of P is a power of 2, (2) P has a unique maximal and m ...
