Abstract. A graph [Formula: see text] is Ramsey for a pair of graphs [Formula: see text] if any red/blue-coloring of the edges of [Formula: see text] yields a copy of [Formula: see text] with all edges colored red or a copy of [Formula: see text] with all edges colored blue. Two pairs of graphs are called Ramsey equivalent if they have the same collection of Ramsey graphs. The symmetric setting, that is, the case [Formula: see text], received considerable attention. This led to the open question whether there are connected graphs [Formula: see text] and [Formula: see text] such that [Formula: see text] and [Formula: see text] are Ramsey equivalent. We make progress on the asymmetric version of this question and identify several nontrivial families of Ramsey equivalent pairs of connected graphs. Certain pairs of stars provide a first, albeit trivial, example of Ramsey equivalent pairs of connected graphs. Our first result characterizes all Ramsey equivalent pairs of stars. The rest of the paper focuses on pairs of the form [Formula: see text], where [Formula: see text] is a tree and [Formula: see text] is a complete graph. We show that if [Formula: see text] belongs to a certain family of trees, including all nontrivial stars, then [Formula: see text] is Ramsey equivalent to a family of pairs of the form [Formula: see text], where [Formula: see text] is obtained from [Formula: see text] by attaching disjoint smaller cliques to some of its vertices. In addition, we establish that for [Formula: see text] to be Ramsey equivalent to [Formula: see text], [Formula: see text] must have roughly this form. On the other hand, we prove that for many other trees [Formula: see text], including all odd-diameter trees, [Formula: see text] is not equivalent to any such pair, not even to the pair [Formula: see text], where [Formula: see text] is a complete graph [Formula: see text] with a single edge attached.

Abstract. A graph [Formula: see text] is said to be [Formula: see text]-Ramsey for a [Formula: see text]-tuple of graphs [Formula: see text], denoted by [Formula: see text], if every [Formula: see text]-edge-coloring of [Formula: see text] contains a monochromatic copy of [Formula: see text] in color [Formula: see text] for some [Formula: see text]. Let [Formula: see text] denote the smallest minimum degree of [Formula: see text] over all graphs [Formula: see text] that are minimal [Formula: see text]-Ramsey for [Formula: see text] (with respect to subgraph inclusion). The study of this parameter was initiated in 1976 by Burr, Erdős, and Lovász, who determined its value precisely for a pair of cliques. Over the past two decades the parameter [Formula: see text] has been studied by several groups of authors, their main focus being on the symmetric case, where [Formula: see text] for all [Formula: see text]. The asymmetric case, in contrast, has received much less attention. In this paper, we make progress in this direction, studying asymmetric tuples consisting of cliques, cycles, and trees. We determine [Formula: see text] when [Formula: see text] is a pair of one clique and one tree, a pair of one clique and one cycle, and a pair of two different cycles. We also generalize our results to multiple colors and obtain bounds on [Formula: see text] in terms of the size of the cliques [Formula: see text], the number of cycles, and the number of cliques. Our bounds are tight up to logarithmic factors when two of the three parameters are fixed.

We study edge-labelings of the complete bidirected graph $\overset{\tiny\leftrightarrow}{K}_n$ with functions from the set $[d] = \{1, \dots, d\}$ to itself. We call a cycle in $\overset{\tiny\leftrightarrow}{K}_n$ a fixed-point cycle if composing the labels of its edges results in a map that has a fixed point, and we say that a labeling is fixed-point-free if no fixed-point cycle exists. For a given $d$, we ask for the largest value of $n$, denoted $R_f(d)$, for which there exists a fixed-point-free labeling of $\overset{\tiny\leftrightarrow}{K}_n$. Determining $R_f(d)$ for all $d >0$ is a natural Ramsey-type question, generalizing some well-studied zero-sum problems in extremal combinatorics. The problem was recently introduced by Chaudhury, Garg, Mehlhorn, Mehta, and Misra, who proved that $d \leq R_f(d) \leq d^4+d$ and showed that the problem has close connections to EFX allocations, a central problem of fair allocation in social choice theory. In this paper we show the improved bound $R_f(d) \leq d^{2 + o(1)}$, yielding an efficient ${(1-\varepsilon)}$-EFX allocation with $n$ agents and $O(n^{0.67})$ unallocated goods for any constant $\varepsilon \in (0,1/2]$; this improves the bound of $O(n^{0.8})$ of Chaudhury, Garg, Mehlhorn, Mehta, and Misra. Additionally, we prove the stronger upper bound $2d-2$, in the case where all edge-labels are permulations. A very special case of this problem, that of finding zero-sum cycles in digraphs whose edges are labeled with elements of $\mathbb{Z}_d$, was recently considered by Alon and Krivelevich and by Mészáros and Steiner. Our result improves the bounds obtained by these authors and extends them to labelings from an arbitrary (not necessarily commutative) group, while also simplifying the proof.

Given any graph $H$, a graph $G$ is said to be $q$-Ramsey for $H$ if every coloring of the edges of $G$ with $q$ colors yields a monochromatic subgraph isomorphic to $H$. Such a graph $G$ is said to be minimal $q$-Ramsey for $H$ if additionally no proper subgraph $G'$ of $G$ is $q$-Ramsey for $H$. In 1976, Burr, Erdös, and Lovász initiated the study of the parameter $s_q(H)$, defined as the smallest minimum degree among all minimal $q$-Ramsey graphs for $H$. In this paper, we consider the problem of determining how many vertices of degree $s_q(H)$ a minimal $q$-Ramsey graph for $H$ can contain. Specifically, we seek to identify graphs for which a minimal $q$-Ramsey graph can contain arbitrarily many such vertices. We call a graph satisfying this property $s_q$-abundant. Among other results, we prove that every cycle is $s_q$-abundant for any integer $q\geq 2$. We also discuss the cases when $H$ is a clique or a clique with a pendant edge, extending previous results of Burr and co-authors and Fox and co-authors. To prove our results and construct suitable minimal Ramsey graphs, we use gadget graphs, which we call pattern gadgets and which generalize earlier constructions used in the study of minimal Ramsey graphs. We provide a new, more constructive proof of the existence of these gadgets.

Abstract Two $$n \times n$$ n × n Latin squares $$L_1, L_2$$ L 1 , L 2 are said to be orthogonal if, for every ordered pair (x, y) of symbols, there are coordinates (i, j) such that $$L_1(i,j) = x$$ L 1 ( i , j ) = x and $$L_2(i,j) = y$$ L 2 ( i , j ) = y . A k-MOLS is a sequence of k pairwise-orthogonal Latin squares, and the existence and enumeration of these objects has attracted a great deal of attention. Recent work of Keevash and Luria provides, for all fixed k, log-asymptotically tight bounds on the number of k-MOLS. To study the situation when k grows with n, we bound the number of ways a k-MOLS can be extended to a $$(k+1)$$ ( k + 1 ) -MOLS. These bounds are again tight for constant k, and allow us to deduce upper bounds on the total number of k-MOLS for all k. These bounds are close to tight even for k linear in n, and readily generalise to the broader class of gerechte designs, which include Sudoku squares.