Finding the smallest integer such that in every configuration of points in in general position, there exist points in convex position is one of the most classical problems in extremal combinatorics, known as the Erdős-Szekeres problem. In 1935, Erdős and Szekeres famously conjectured that holds, which was nearly settled by …
The disjoint paths logic, FOL+DP, is an extension of First Order Logic (FOL) with the extra atomic predicate expressing the existence of internally vertex-disjoint paths between and for . This logic can express a wide variety of problems that escape the expressibility potential of FOL. We prove that for every …
Fix and consider a family F of -free graphs, each having minimum degree linear in its number of vertices. Such a family is known to have bounded chromatic number; equivalently, each graph in F is homomorphic to a complete graph of bounded size. We disprove the analogous statement for homomorphic images that …
Various types of independent sets have been studied for decades. As an example, the minimum number of maximal independent sets in a connected graph of given order is easy to determine (hint; the answer is written in the stars). When considering this question for twin-free graphs, it becomes less trivial and one discovers some surprising …
