Apparaît dans la collection : Model Theory and Combinatorics

Let k +/= 1 be a fixed integer. It is conjectured that any graph on n vertices that can be drawn in the plane without k pairwise crossing edges has O(n) edges. Two edges of a hypergraph cross each other if neither of them contains the other, they have a nonempty intersection, and their union is not the whole vertex set. It is conjectured that any hypergraph on n vertices that contains no k pairwise crossing edges has at most O(n) edges. We discuss the relationship between the 5 above conjectures and explain some partial answers, including a recent result of Kupavskii, Tomon, and the speaker, improving a 40 years old bound of Lomonosov.