Umeå University's logo

Let (Formula presented.) be positive integers such that (Formula presented.) and (Formula presented.) be a tripartite graph with parts (Formula presented.) such that (Formula presented.). Denote the edge densities of (Formula presented.) and (Formula presented.) by (Formula presented.) and (Formula presented.), respectively. In this paper, we study edge density conditions for the existence of (Formula presented.) vertex-disjoint triangles in a tripartite graph. For (Formula presented.) we give an optimal condition in terms of densities (Formula presented.) for the existence of (Formula presented.) vertex-disjoint triangles in (Formula presented.). We also give an optimal condition in terms of densities (Formula presented.) for the existence of a triangle-factor in (Formula presented.).

We introduce near triple arrays as binary row-column designs with at most two consecutive values for the replication numbers of symbols, for the intersection sizes of pairs of rows, pairs of columns and pairs of a row and a column. Near triple arrays form a common generalization of such well-studied classes of designs as triple arrays, (near) Youden rectangles and Latin squares. We enumerate near triple arrays for a range of small parameter sets and show that they exist in the vast majority of the cases considered. As a byproduct, we obtain the first complete enumerations of 6×10 triple arrays on 15 symbols, 7×8 triple arrays on 14 symbols and 5×16 triple arrays on 20 symbols. Next, we give several constructions for families of near triple arrays, and e.g. show that near triple arrays with 3 rows and at least 6 columns exist for any number of symbols. Finally, we investigate a duality between row and column intersection sizes of a row-column design, and covering numbers for pairs of symbols by rows and columns. These duality results are used to obtain necessary conditions for the existence of near triple arrays. This duality also provides a new unified approach to earlier results on triple arrays and balanced grids.

In this paper, we study Condorcet domains, sets of linear orders from which majority ranking produces a linear order. We introduce a new class of Condorcet domains, called coherent domains, which is natural from both a voting theoretic and combinatorial perspective. After studying the properties of these domains we introduce set-alternating schemes. This is a method for constructing well-behaved coherent domains. Using this we show that, for sufficiently large numbers of alternatives n, there are coherent domains of size more than 2.1973n. This improves the best existing asymptotic lower bounds for the size of the largest general Condorcet domains.

A Condorcet domain is a collection of linear orders which avoid Condorcet's paradox for majority voting. We have developed a new algorithm for complete enumeration of all maximal Condorcet domains and, using a supercomputer, obtained the first enumeration of all maximal Condorcet domains on n≤7 alternatives. We investigate properties of these domains and use this study to resolve several open questions regarding Condorcet domains, and propose several new conjectures. Following this we connect our results to other domain types used in voting theory, such a non-dictatorial and strategy-proof domains. All our data are made freely available on the web.

We computationally completely enumerate a number of types of row-column designs up to isotopism, including double, sesqui, and triple arrays as known from the literature, and two newly introduced types that we call mono arrays and AO-arrays. We calculate autotopism group sizes for the designs we generate. For larger parameter values, where complete enumeration is not feasible, we generate examples of some of the designs, and for some admissible parameter sets, we prove non-existence results. We give some explicit constructions of sesqui arrays, mono arrays and AO-arrays, in particular, we prove constructively that AO-arrays exist for all feasible parameter sets. Finally, we investigate connections to Youden rectangles and binary pseudo-Youden designs.

In this paper we introduce CDL, a software library designed for the analysis of permutations and linear orders subject to various structural restrictions. Prominent examples of these restrictions include pattern avoidance, a topic of interest in both computer science and combinatorics, and never conditions, utilized in social choice and voting theory. CDL offers a range of fundamental functionalities, including identifying the permutations that meet specific restrictions and determining the isomorphism of such sets. To facilitate the exploration of large permutation sets or domains, CDL incorporates multiple search strategies and heuristics.

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 co-isotopic. In the course of doing this, we perform a complete enumeration of sets of t mutually orthogonal k × n Latin rectangles for k ≤ n ≤ 7, for all t < n up to isotopism, and up to paratopism. Additionally, for larger n we enumerate co-isotopic 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 transitive. We build the sets of MOLR row by row, and in this process we also keep track of which of the MOLR are co-isotopic and/or transitive in each step of the construction process. We use the prefix stepwise to refer to sets of MOLR with this property at each step of their construction. Sets of MOLR are connected to other discrete objects, notably finite geometries and certain regular hypergraphs. Here we observe that all projective planes of order at most 9 except the Hughes plane can be constructed from a stepwise transitive MOLR.

Let G:=(G₁,G₂,G₃) be a triple of graphs on a common vertex set V of size n. A rainbow triangle in G is a triple of edges (e₁,e₂,e₃) with e_i ∈ G_i for each i and {e₁,e₂,e₃} forming a triangle in V. In this paper we consider the following question: what triples of minimum degree conditions (∂(G₁),∂(G₂),∂(G₃)) guarantee the existence of a rainbow triangle? This may be seen as a minimum degree version of a problem of Aharoni, DeVos, de la Maza, Montejanos and Šámal on density conditions for rainbow triangles, which was recently resolved by the authors. We establish that the extremal behaviour in the minimum degree setting differs strikingly from that seen in the density setting, with discrete jumps as opposed to continuous transitions. Our work leaves a number of natural questions open, which we discuss.

Let G:=(G₁,G₂,G₃) be a triple of graphs on the same vertex set V of size n. A rainbow triangle in G is a triple of edges (e₁,e₂,e₃) with e_i ∈ G_i for each i and {e₁,e₂,e₃} forming a triangle in V. The triples 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 (α₁,α₂,α₃) such that if |E(G_i)| >α_in² for each i and n is sufficiently large, then 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 note, we report on a Condorcet domain of record-breaking size for n = 8 alternatives. We show that there exists a Condorcet domain of size 224 and that this is the largest possible size for 8 alternatives. Our search also shows that this domain is unique up to isomorphism. In this note we investigate properties of the new domain and relate them to various open problems and conjectures.