Klas Markström

An edge-colouring of a graph $G$ can fail to be rainbow for two reasons: either it contains a monochromatic cherry (a pair of incident edges), or a monochromatic matching of size two. A colouring is a proper colouring if it forbids the first structure, and a star-colouring if it forbids the second structure. In this paper, we study rainbow subgraphs in star-coloured graphs and determine the maximum number of colours in a star-colouring of a large complete graph which does not contain a rainbow copy of a given graph $H$. This problem is a special case of one studied by Axenovich and Iverson on generalised Ramsey numbers and we extend their results in this case.

Condorcet domains are fundamental objects in the theory of majority voting; they are sets of linear orders with the property that if every voter picks a linear order from this set, assuming that the number of voters is odd, and alternatives are ranked according to the pairwise majority ranking, then the result is a linear order on the set of all alternatives. In this paper we present an efficient orderly algorithm for the generation of all non-isomorphic maximal Condorcet domains on $n$ alternatives. The algorithm can be adapted to generate domains from various important subclasses of Condorcet domains. We use an example implementation to extend existing enumerations of domains from several such subclasses and make both data and the implementation publicly available.

Let $$\textbf{G}:=(G_1, G_2, G_3)$$G : = ( G 1 , G 2 , G 3 ) be a triple of graphs on the same vertex set V of size n. A rainbow triangle in $$\textbf{G}$$G is a triple of edges $$(e_1, e_2, e_3)$$( e 1 , e 2 , e 3 ) with $$e_i\in G_i$$e i ∈ G i for each i and $$\{e_1, e_2, e_3\}$${ e 1 , e 2 , e 3 } forming a triangle in V. The triples $$\textbf{G}$$G not containing rainbow triangles, also known as Gallai colouring templates, are a widely studied class of objects in extremal combinatorics. In the present work, we fully determine the set of edge densities $$(\alpha _1, \alpha _2, \alpha _3)$$( α 1 , α 2 , α 3 ) such that if $$\vert E(G_i)\vert > \alpha _i n^2$$| E ( G i ) | > α i n 2 for each i and n is sufficiently large, then $$\textbf{G}$$G must contain a rainbow triangle. This resolves a problem raised by Aharoni, DeVos, de la Maza, Montejanos and Šámal, generalises several previous results on extremal Gallai colouring templates, and proves a recent conjecture of Frankl, Győri, He, Lv, Salia, Tompkins, Varga and Zhu.

In this paper we extend the study of Arrow's generalisation of Black's single-peaked domain and connect this to domains where voting rules satisfy different versions of independence of irrelevant alternatives. First we report on a computational generation of all non-isomorphic Arrow's single-peaked domains on $n\leq 9$ alternatives. Next, we introduce a quantitative measure of richness for domains, as the largest number $r$ such that every alternative is given every rank between 1 and $r$ by the orders in the domain. We investigate the richness of Arrow's single-peaked domains and prove that Black's single-peaked domain has the highest possible richness, but it is not the only domain which attains the maximum. After this we connect Arrow's single-peaked domains to the discussion by Dasgupta, Maskin and others of domains on which plurality and the Borda count satisfy different versions of Independence of Irrelevant alternatives (IIA). For Nash's version of IIA and plurality, it turns out the domains are exactly the duals of Arrow's single-peaked domains. As a consequence there can be at most two alternatives which are ranked first in any such domain. For the Borda count both Arrow's and Nash's versions of IIA lead to a maximum domain size which is exponentially smaller than $2^{n-1}$, the size of Black's single-peaked domain.

We study sets of mutually orthogonal Latin rectangles (MOLR), and a natural variation of the concept of self-orthogonal Latin squares which is applicable on larger sets of mutually orthogonal Latin squares and MOLR, namely that each Latin rectangle in a set of MOLR is isotopic to each other rectangle in the set. We call such a set of MOLR \emph{homogeneous}. In the course of doing this, we perform a complete enumeration of non-isotopic sets of $t$ mutually orthogonal $k\times n$ Latin rectangles for $k\leq n \leq 7$, for all $t < n$. Specifically, we keep track of homogeneous sets of MOLR, as well as sets of MOLR where the autotopism group acts transitively on the rectangles, and we call such sets of MOLR \emph{transitive}. We build the sets of MOLR row by row, and in this process we also keep track of which of the MOLR are homogeneous and/or transitive in each step of the construction process. We use the prefix \emph{stepwise} to refer to sets of MOLR with this property. Sets of MOLR are connected to other discrete objects, notably finite geometries and certain regular graphs. Here we observe that all projective planes of order at most 9 except the Hughes plane can be constructed from a stepwise transitive MOLR.