Search

The typical extremal problem asks how large a structure can be without containing a forbidden substructure. The Erdős–Rothschild problem, introduced in 1974 by Erdős and Rothschild in the context of extremal graph theory, is a coloured extension, asking for the maximum number of colourings a structure can have that avoid monochromatic copies of the forbidden substructure. The celebrated Erdős–Ko–Rado theorem is a fundamental result in extremal set theory, bounding the size of set families without a pair of disjoint sets, and has since been extended to several other discrete settings. The Erdős–Rothschild extensions of these theorems have also been studied in recent years, most notably by Hoppen, Koyakayawa and Lefmann for set families, and Hoppen, Lefmann and Odermann for vector spaces. In this paper we present a unified approach to the Erdős–Rothschild problem for intersecting structures, which allows us to extend the previous results, often with sharp bounds on the size of the ground set in terms of the other parameters. In many cases we also characterise which families of vector spaces asymptotically maximise the number of Erdős–Rothschild colourings, thus addressing a conjecture of Hoppen, Lefmann and Odermann. [ABSTRACT FROM AUTHOR]

Motivated by a question of Grinblat, we study the minimal number v ( n ) that satisfies the following. If A 1 , … , A n are equivalence relations on a set X such that for every i ∈ [ n ] there are at least v ( n ) elements whose equivalence classes with respect to A i are nontrivial, then A 1 , … , A n contain a rainbow matching, i.e. there exist 2 n distinct elements x 1 , y 1 , … , x n , y n ∈ X with x i ∼ A i y i for each i ∈ [ n ] . Grinblat asked whether v ( n ) = 3 n − 2 for every n ≥ 4 . The best-known upper bound was v ( n ) ≤ 16 n / 5 + O ( 1 ) due to Nivasch and Omri. Transferring the problem into the setting of edge-coloured multigraphs, we affirm Grinblat's question asymptotically, i.e. we show that v ( n ) = 3 n + o ( n ) . [ABSTRACT FROM AUTHOR]

In the Oriented-cycle game, introduced by Bollobás and Szabó [7] , two players, called OMaker and OBreaker, alternately direct edges of K n . OMaker directs exactly one previously undirected edge, whereas OBreaker is allowed to direct between one and b previously undirected edges. OMaker wins if the final tournament contains a directed cycle, otherwise OBreaker wins. Bollobás and Szabó [7] conjectured that for a bias as large as n − 3 OMaker has a winning strategy if OBreaker must take exactly b edges in each round. It was shown recently by Ben-Eliezer, Krivelevich and Sudakov [6] , that OMaker has a winning strategy for this game whenever b < n / 2 − 1 . In this paper, we show that OBreaker has a winning strategy whenever b > 5 n / 6 + 1 . Moreover, in case OBreaker is required to direct exactly b edges in each move, we show that OBreaker wins for b ⩾ 19 n / 20 , provided that n is large enough. This refutes the conjecture by Bollobás and Szabó. [ABSTRACT FROM AUTHOR]