For a fixed poset P, a family F of subsets of [n] is induced P-saturated if F does not contain an induced copy of P, but for every subset S of [n] such that S ∉ F, P is an induced subposet of F ∪{S}. The size of the smallest such family F is denoted by sat∗ (n, P). Keszegh, Lemons, Martin, Pálvölgyi and Patkós [Journal of Combinatorial Theory Series A, 2021] proved that there is a dichotomy of behaviour for this parameter: given any poset P, either sat* (n, P) = O(1) or (Formula presented). In this paper we improve this general result showing that either (Formula presented). Our proof makes use of a Turán-type result for digraphs. Curiously, it remains open as to whether our result is essentially best possible or not. On the one hand, a conjecture of Ivan states that for the so-called diamond poset (Formula presented) we have (Formula presented); so if true this conjecture implies our result is tight up to a multi-plicative constant. On the other hand, a conjecture of Keszegh, Lemons, Martin, Pálvölgyi and Patkós states that given any poset P, either sat* (n, P) = O(1) or (Formula presented). We prove that this latter conjecture is true for a certain class of posets P.
We develop a limit theory of Latin squares, paralleling the recent limit theories ofdense graphs and permutations. We introduce a notion of density, an appropriate version ofthe cut distance, and a space of limit objects — so-called Latinons. Key results of our theoryare the compactness of the limit space and the equivalence of the topologies induced by thecut distance and the left-convergence. Last, using Keevash’s recent results on combinatorialdesigns, we prove that each Latinon can be approximated by a finite Latin square.
The famous Erdos-Rademacher problem asks for the smallest number of r-cliques in a graph with the given number of vertices and edges. Despite decades of active attempts, the asymptotic value of this extremal function for all r was determined only recently, by Reiher [Annals of Mathematics, 184 (2016) 683-707]. Here we describe the asymptotic structure of all almost extremal graphs. This task for r = 3 was previously accomplished by Pikhurko and Razborov [Combinatorics, Probability and Computing, 26 (2017) 138-160].
We present a sufficient condition for the stability property of extremal graph problems that can be solved via Zykov's symmetrisation. Our criterion is stated in terms of an analytic limit version of the problem. We show that, for example, it applies to the inducibility problem for an arbitrary complete bipartite graph B, which asks for the maximum number of induced copies of B in an n-vertex graph, and to the inducibility problem for K2,1,1,1 and K3,1,1, the only complete partite graphs on at most five vertices for which the problem was previously open.
A set of integers is sum-free if it does not contain any solution for x+y=z. Answering a question of Cameron and Erdős, Balogh, Liu, Sharifzadeh and Treglown recently proved that the number of maximal sum-free sets in {1,…,n} is Θ(2μ(n)/2), where μ(n) is the size of a largest sum-free set in {1,…,n}. They conjectured that, in contrast to the integer setting, there are abelian groups G having exponentially fewer maximal sum-free sets than 2μ(G)/2, where μ(G) denotes the size of a largest sum-free set in G.
We settle this conjecture affirmatively. In particular, we show that there exists an absolute constant c>0 such that almost all even order abelian groups G have at most 2(1/2−c)μ(G) maximal sum-free sets.
Let f(n, r) denote the maximum number of colourings of A ⊆ {1, …, n} with r colours such that each colour class is sum-free. Here, a sum is a subset {x, y, z} such that x + y = z. We show that f(n, 2) = 2⌈n/2⌉, and describe the extremal subsets. Further, using linear optimisation, we asymptotically determine the logarithm of f(n, r) for r ≤ 5. Similar results were obtained by Hán and Jiménez in the setting of finite abelian groups.