Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
We considerm-colorings of the edges of a complete graph, where each color class is defined semi-algebraically with bounded complexity. The casem= 2 was first studied by Alon et al., who applied this framework to obtain surprisingly strong Ramsey-type results for intersection graphs of geometric objects and for other graphs arising in computational geometry. Considering larger values ofmis relevant, e.g., to problems concerning the number of distinct distances determined by a point set. Forp >= 3 andm >= 2, the classical Ramsey numberR(p; m) is the smallest positive integernsuch that anym-coloring of the edges ofK(n), thecompletegraph onnvertices, contains a monochromaticK(p). It is a longstanding open problem that goes back to Schur (1916) to decide whetherR(p; m)