Papers

For any permutation of a nontrivial finite abelian group, the differential uniformity is at least two; permutations attaining this bound are called almost perfect nonlinear (APN). We construct three infinite classes of APN permutations on the cyclic group $\mathbb{Z}_n$ using Singer cycles, binomials inducing projective permutations, and completed reciprocals combined with parity and quadratic characters. The respective domain orders are $q+1$ for prime powers $q>2$, $(3^d-1)/2$ for integers $d\ge2$, and $2p$ for primes $p>5$ with $p\equiv5\pmod6$. Each class contains an infinite subclass of composite orders outside the standard forms $r-1$, $r-2$, $r-3$, and $r-4$, where $r$ is a prime power. These forms arise in the Welch–Costas, Panario–Sakzad–Stevens–Wang, and Golomb constructions. To the best of our knowledge, these are the first infinite APN constructions on $\mathbb{Z}_n$ reported since 2011 that yield infinitely many composite orders outside these standard forms.

The $s$-vertex expansion hypergraph $G^{[s]}$ is the $2s$-uniform hypergraph obtained by replacing each vertex of a graph $G$ with $s$ new vertices. A closed walk in $G$ is called an $s$-multiple closed walk if the number of times it arrives at each vertex of $G$ is divisible by $s$. In this paper, we obtain an expression for the spectral moments of $G^{[s]}$ in terms of $s$-multiple closed walks in $G$. Using these spectral moments, we give the characteristic polynomial of $G^{[s]}$.

Let $r\geq3$ and $k_1\geq k_2\geq\cdots\geq k_r\geq t$. Let $\mathcal{F}_1,\mathcal{F}_2,\ldots,\mathcal{F}_r$ be families of subspaces, of respective dimensions $k_1,k_2,\ldots,k_r$, in an $n$-dimensional vector space over the finite field $\mathbb{F}_q$. The $r$ families are called $r$-cross $t$-intersecting if $\dim \left(F_{1} \cap F_{2} \cap \cdots \cap F_{r}\right) \geq t$ for all $F_{i} \in \mathcal{F}_{i}, i = 1,2,\dots,r$. In 2016, Frankl and Tokushige conjectured that $\prod_{i=1}^{r}|\mathcal{F}_i|\leq\prod_{i=1}^{r}{n-1\brack k_i-1}$ for $t=1$ and $n\geq rk_1/(r-1)$. The appealing conjecture suggests establishing intersection theorems for $n\sim ck_1$ with $c=c(r)\in(1,2)$, a direction that has long been challenging. In this paper, we overcome this barrier by proving that $$\prod_{i=1}^{r}|\mathcal{F}_i|\leq\prod_{i=1}^{r}{n-t\brack k_i-t}\;\;\mbox{for all}\;\;t\geq1\;\mbox{and}\;n\geq rk_1/(r-1)+C(t,r),$$ where $C(t,r)=rt/(r-1)+1$. This proves the Frankl–Tokushige conjecture except for at most three values of $n$, and establishes an Erdős–Ko–Rado type theorem for almost all values of parameters. Furthermore, we characterize all extremal configurations. Our proof is purely combinatorial and based on the $t$-cover method, with several essential refinements. We also obtain almost complete intersection theorems for $r$-wise $t$-intersecting families and non-trivial $r$-cross $t$-intersecting families.

The Habsieger–Kadell $q$-Morris constant term identity, which is equivalent to the famous $q$-Selberg integral, has been generalized in numerous ways since the 1980s. Among these, there are two important generalizations: (i) the $q$-Baker–Forrester ex-conjecture, which was conjectured by Baker and Forrester in 1998 and proved by Károlyi, Nagy, Petrov and Volkov in 2015; (ii) the AFLT-type $q$-Morris identity (equivalently, the AFLT-type $q$-Selberg integral), which was obtained by Albion, Rains and Warnaar in 2021, as a $q$-analog of the result of Alba, Fateev, Litvinov and Tarnopolskiy (AFLT). In this paper, by the Gessel–Xin method and the Macdonald polynomials with prescribed symmetry, we unify these two generalizations.

When exploring the Hankel determinant of the sequence $\mu_{k}=B_{k+1}/(k+1)$, where $B_{k}$ is the $k$-th Bernoulli number, we obtained two interesting results. The first one applies in general to all sequences $(c_{k})_{k\geq0}$ with all even-indexed term $0$, except for $c_{0}$. In this case, the coefficient of the second highest order of the corresponding monic orthogonal polynomials determines the Hankel determinants. Our second result shows, the corresponding J-fractions, obtained from the generating function of $\mu_{k}$, is exactly the same as in early work of Cao, on a faster sequence converging to the Euler–Mascheroni constant.

Fix a base $b\ge2$ and a digit set $\mathcal{D}\subset\{0,1,\dots,b-1\}$, and let $\mathcal C_k$ be the set of integers in $[0,b^k)$ whose $k$ base-$b$ digits all lie in $\mathcal D$. We study prime pairs and three-term arithmetic progressions in primes whose difference, or common difference, belongs to $\mathcal C_k$. Under a natural digit non-resonance condition, we establish a localized Fourier criterion guaranteeing asymptotic formulae with explicit leading constants for both problems. Using a transfer-operator argument, we verify this criterion in explicit parameter ranges for several natural families of digit sets.

For an $n\times n$ oscillatory matrix $A$, let $e_k(A)$ be the least positive integer $m$ for which every minor of order $k$ of $A^m$ is positive. We determine the profile $(e_1(A),\ldots,e_n(A))$. For every nonsingular totally nonnegative matrix, the column index sets of positive entries in each compound row form an interval in the componentwise order. The endpoint maps are order-preserving and compose under multiplication. This yields a two-corner criterion for positivity of all minors of a fixed order. Consequently, $e_k(A)$ is the larger of the first positivity times of two remote corner minors. We prove the sharp inequalities $e_k(A)\leq\max{k,n-k}$ for $1\leq k<n$ and $|e_{k+1}(A)-e_k(A)|\leq1$ for $1\leq k\leq n-2$. For $D=\operatorname{diag}(1,-1,1,-1,\ldots)$, the matrix $DA^{-1}D$ is oscillatory and satisfies $e_k(DA^{-1}D)=e_{n-k}(A)$ for $1\leq k<n$; the determinant exponent remains one. The ordered positions of the positive factors in an adjacent bidiagonal factorization determine the profile independently of their values. Each one-sided factor sequence can be represented by a single permutation, giving a finite characterization of all profiles and an integer unimodular realization of each. We also obtain a compatibility condition across minor orders: if $3\leq k\leq n-3$ and $e_k(A)\leq2$, then $e_j(A)\leq2+\lceil |j-k|/2\rceil$ for $2\leq j\leq n-2$. In particular, $e_k(A)\leq2$ implies $e_{k+2}(A)\leq3$ for $3\leq k\leq n-4$, and both the constant and this range are sharp.

Is it possible to walk to infinity, avoiding three collinear points, using as steps only the standard unit basis vectors $(0,0,\ldots, 0, 1, 0, \ldots, 0)$? We prove this is possible in $16$ dimensions.

Li, Ponomarenko and Zeman state their belief that every polyhedral graph (i.e. every $3$-connected planar graph) is Schurian: that its coherent closure $WL(X)$ coincides with the orbital configuration of $Aut(X)$. Combined with their Theorem 1.1, this would imply that every polyhedral graph has Weisfeiler-Leman dimension at most $2$. We report a computational verification of the Schurian property for all polyhedral graphs with at most $16$ vertices, a total of 413,024,847,068 graphs, none of which is non-Schurian. The computation combines the generator plantri with a one-sided $1$-WL discreteness filter and, for every graph surviving that filter, a full comparison of the stable $2$-WL partition of $\Omega^2$ with the orbit partition of $Aut(X)$. The computation is guarded by the published anchor counts, a seeded re-enumeration of the two largest stages, independent nauty cross-checks and control graphs with mathematically fixed verdicts; code, checkpoints and a verification script accompany the note as ancillary files. For $n\le 13$ the result reproduces what already follows from the published enumeration of coherent configurations, by an entirely different route; from $n=14$ on, deriving it from that side would require a step we could not find in the literature, and at $n=16$ the all-graphs statement fails outright - the Shrikhande graph is non-Schurian - so there the polyhedral restriction carries the result. The statement is established by exhaustive computation; with respect to the general conjecture it is instance evidence, not a proof. A companion note treats the torus side, where non-Schurian triangulation graphs do occur at $n = 16$.

In this paper, we study rooted spanning forests in the wheel graph $W_{N+1}$. For a root set $R$ consisting of rim vertices, we give an explicit formula, in terms of Fibonacci and Lucas numbers, for the number of rooted spanning forests in which each connected component contains exactly one vertex of $R$. When the central vertex is also included in the root set, we obtain a simple product formula involving only Fibonacci numbers. Furthermore, by using the correspondence between rooted spanning forests and vertex identification, we derive explicit formulas for the number of spanning trees of quotient graphs of wheel graphs obtained by identifying several vertices into one vertex. We then rewrite the obtained formulas combinatorially in terms of the numbers of matchings in path graphs and cycle graphs. In addition, for a fixed number $r$ of rim root vertices, we express the sum of the numbers of rooted spanning forests over all rim root sets of size $r$ as coefficients of generating functions, and we solve the extremal problem for the arrangement of roots.

Families of sequences with low mutual aperiodic crosscorrelation assist the design of systems for multi-user asynchronous communications and multiple-input multiple-output radar. The crosscorrelation demerit factor of a pair of sequences is the sum of the squared magnitudes of their crosscorrelation values at every shift when the sequences are normalized to unit Euclidean norm, and the merit factor is the reciprocal of the demerit factor. For each positive integer $\ell$, we endow the $2^{2 \ell}$ pairs of binary sequences of length $\ell$ with uniform probability measure and study the distribution of their crosscorrelation demerit factors. Sarwate showed that the mean value is always $1$ regardless of length $\ell$. We develop a method for finding an exact formula for the $p$th central moment (for any positive integer $p$) as a function of $\ell$. Formulae for the variance and third central moment ($p=2$ and $3$) are then obtained by hand calculations, while the fourth through sixth central moments are obtained by computer-assisted calculations. Our theory also shows that all the central moments must be strictly positive for $p\geq 2$ and $\ell \geq 3$.

We consider the family of operators of stack sorting (s_m)_{m >= 1} acting on words according to the following rule: s_m(w) is the output produced by the usual West algorithm of stack sorting on the input word w, but allowing for at most m repetitions of the same letter stacked in succession. Our first main theorem gives an explicit formula for the action of the operator s_m on binary words w = a^p b a^q (with distinct letters a > b): s_m(a^p b a^q) = a^max(p-m,0) b a^min(p,m)+q, d_m(a^k b) = ceil(k/m). From the above formulas it follows that for every m < m' we have d_m(w) >= d_{m'}(w) for binary words w = a^k b, and moreover, the ratio d_m(w)/d_{m'}(w) is always possible to be chosen exactly m'/m, so the ratios d_m/d_{m'} are unbounded for this family on the specified class – this is an explicit form of the expected separation-speedup phenomenon. Additionally, we provide explicit constructions of words of length 4 for which s_m and s_{m'} do not commute, and words of length 7 for which the speed d_m is not monotonic in m. Further, we provide a full recursive characterization – generalizing the classical 231-avoidance result of Knuth and West – of words which can be sorted using s_m only once, and then we employ it to show that there cannot exist an m-independent classical pattern avoidance condition for one-pass sortable words. Finally, we give a complete proof of the inequality d_1(w) >= d_m(w) >= d_infinity(w) for all m for two-letter words, together with a structural result establishing it for a single pass in general; nevertheless, we show that the family of operators (s_m) does not, after all, lie entirely between s_1 and s_infinity, exhibiting for every n >= 7 an explicit word w_n with d_1(w_n) = n-4 < n-3 = d_m(w_n) for every m >= 2, including m = infinity, so that the inequality above is false in general.

In quantum information theory, the state space of a multipartite quantum system is modeled by a tensor product. In the tensor-product space $\mathbb C^{d_1}\otimes\cdots\otimes\mathbb C^{d_p}$, a nonzero vector is a product state if it can be written as $\lvert \varphi_1\rangle\otimes\cdots\otimes\lvert \varphi_p\rangle$ with $\lvert \varphi_j\rangle\in\mathbb C^{d_j}\setminus\{0\}$. An unextendible product basis (UPB) is a finite family of pairwise orthogonal product states such that no nonzero product state is orthogonal to all of them. UPBs play a key role in investigating quantum entanglement and nonlocal phenomena. Finding a smallest UPB is a natural extremal problem: it asks how few pairwise orthogonal product states suffice to prevent any further product state from being added. The general minimum-size problem for UPBs has been studied for over two decades since the seminal work of Alon and Lovász. For local dimensions $d_1,\ldots,d_p\ge2$, let $f_m(d_1,\ldots,d_p)$ be the minimum cardinality of a UPB and let $f_{LB}(d_1,\ldots,d_p)=1+\sum_{j=1}^{p}(d_j-1)$ be the natural lower bound. Alon and Lovász determined exactly when $f_m$ attains the lower bound $f_{LB}$, but the obstructed multipartite cases remained open in general. We prove a stabilization theorem: for every non-all-qubit system with $p\ge3$, whenever parity prevents the natural lower bound $f_{LB}$ from being attained, the true minimum is exactly $f_{LB}+1$. Equivalently, if the number of even local dimensions is positive and even, and at least one local dimension is greater than two, then $f_m(d_1,\ldots,d_p)=f_{LB}(d_1,\ldots,d_p)+1$. The proof is built on a unified graph-theoretic framework. Our result, together with earlier work, settles the minimum-cardinality problem for UPBs in all finite quantum systems.

We determine the maximum rank of $4\times 4\times 4$ and $k\times 4\times 3$ multidimensional arrays over the finite field $\mathbb{F}_2$. These results are made possible by a new method of enumerating non-isomorphic tensors.

Let $(X_1,\ldots,X_n)$ be a random variable in $(\mathbb{R}\setminus\{0\})^n$ that is both exchangeable and sign-invariant. For every $k\in[n]$, let $S_k=\sum_{i=1}^kX_i$. Define the weak persistence probability as $\mathbb{P}(S_1,\ldots,S_n\geq0)$, and the strong persistence probability as $\mathbb{P}(S_1,\ldots,S_n>0)$. From previous results, the optimal lower bound for $\mathbb{P}(S_1,\ldots,S_n\geq0)$ and the optimal upper bound for $\mathbb{P}(S_1,\ldots,S_n>0)$ are known. We complete the picture by determining the optimal upper bound for $\mathbb{P}(S_1,\ldots,S_n\geq0)$ and the optimal lower bound for $\mathbb{P}(S_1,\ldots,S_n>0)$ as follows. \[\frac{1}{2^n}\binom{n-1}{\lfloor (n-1)/2\rfloor}\leq\mathbb{P}(S_1,\ldots,S_n>0)\leq\frac{1}{4^n}\binom{2n}{n}\leq\mathbb{P}(S_1,\ldots,S_n\geq0)\leq\frac{1}{2^n}\binom{n}{\lfloor n/2\rfloor}.\] In particular, this implies that the weak and strong persistence probabilities of every exchangeable and sign-invariant random variable $(X_1,\ldots,X_n)$ in $(\mathbb{R}\setminus\{0\})^n$ are of the order $n^{-1/2}$. We also obtain some related results, one in the deterministic setting, and one when the random variables are allowed to take the value 0.

Let $d=(n-1)^2+1$, the dimension of the real linear span of the $n\times n$ permutation matrices. We prove that $d$ independent uniformly random permutation matrices fail to form a basis with probability $(1+o(1))n^2(1-1/n)^d=(e^{3/2}+o(1))n^2e^{-n}$. The same asymptotic holds for a uniformly random $d$-element subset, confirming a conjecture of Kushwaha and Tripathi and identifying the leading obstruction: a matrix position avoided by every sample. More generally, for any fixed number of additional samples, we determine the first three exponential orders of the failure probability. To prove these results, we develop support estimates valid over arbitrary fields, derive Fourier bounds from permanental minors, and introduce a counting argument for concentrated assignment functionals over large prime fields. We also give a sparse lifting argument showing that real rank deficiency without an annihilating functional of small support has probability $o(e^{-Cn})$ for every fixed $C>0$.

In this paper we obtain all doubly-stochastic solutions to the Yang-Baxter-like matrix equation $AXA = XAX$ when $A$ is a permutation matrix. We characterize the permutation solutions, proper doubly stochastic solutions, and we accompany our results with suitable examples.

The Erd\H os–Sós conjecture states that every $n$-vertex graph with more than $(k-2)n/2$ edges contains every $k$-vertex tree. We prove that for every $\gamma$ there is an $n_0$ such that for all $n\ge n_0$ and $k \ge \gamma n$ the conjecture holds. As a corollary of our result, we obtain a solution of a 51-year-old problem of Erd\H os and Graham on the multicolor Ramsey numbers of trees.

By Tutte's classic theorem of 1956 that every 4-connected planar graph is Hamiltonian, every planar graph of order at least three with toughness greater than $\frac{3}{2}$ is Hamiltonian. In 1999, Owens constructed a sequence of maximal planar graphs whose toughness approaches $\frac{3}{2}$ from below and which do not contain even a 2-factor, and he asked whether there exists a maximal planar graph with toughness exactly $\frac{3}{2}$ and with no 2-factor. In 2025, Shan constructed a $\frac{3}{2}$-tough plane triangulation with no 2-factor. In that construction, there are many pairs of vertices of degree $3$ that have a common neighbor. By imposing a distance condition on the vertices of degree $3$, Hao, Ma, Shan, and Yang recently proved that every $\frac{3}{2}$-tough plane triangulation of order at least three whose vertices of degree $3$ are pairwise at distance at least $3$ has a 2-factor, and they asked whether every such graph is Hamiltonian. We answer this question in the negative, and in fact prove the following stronger statement: for every positive integer $\ell$, there exists a $\frac{3}{2}$-tough non-Hamiltonian plane triangulation whose vertices of degree $3$ are pairwise at distance at least $\ell$. Thus, although the distance condition guarantees the existence of a 2-factor, it does not guarantee that the graph is Hamiltonian: the essential obstruction to a Hamiltonian cycle is a certain local configuration involving a vertex of degree $3$, rather than the proximity of such configurations in the graph.

The Erd\H os–Sós conjecture states that every $n$-vertex graph $G$ with more than $(k-2)n/2$ edges contains every $k$-vertex tree. We solve the extremal cases of this conjecture, showing that for some fixed $\mu>0$, the conjecture holds for each $G$ that minimally satisfies the assumptions of the conjecture and has a subgraph~$H$ of minimum degree $\delta(H)\ge (1-\mu)k$. In our proof, we mainly have to deal with $H$ taking two different shapes: either $H$ is close to the complete graph $K_k$ or $H$ is close to the complete bipartite graph $K_{k,k}$.

We determine, up to a factor of $2^{o(k)}$, the number of $k$-sets $A \subset \{1, \ldots, n\}$ such that $|A + A| \leq m$, where $k = \Theta(\log n)$ and $m \leq k^{1 + \alpha}$, for small $\alpha > 0$, answering a question of Green and Morris.

In the uniform sparsest cut problem we are asked to find a vertex set that cuts few edges relative to the number of vertex pairs it separates. The Goemans-Linial SDP coupled with the Arora-Rao-Vazirani rounding gives an $\mathcal{O}(\sqrt{\log n})$ approximation on arbitrary graphs on $n$ vertices. We study this relaxation on finite Abelian Cayley graphs. First we show that when the second normalized Laplacian eigenvalue of $G= \mathrm{Cayley}(\Gamma, S)$ is realized by a Fourier character with image size at most four then $\lambda_2(G)=\mathrm{SDP}_{\mathrm{GL}}(G)=\psi(G)$. Geometrically, a character maps the vertices onto a regular polygon where the squared chord distance satisfies the triangle inequalities exactly when the polygon has at most four vertices. Grouping equal character fibers gives a cyclic quotient where the optimal cut can be found exactly and so the relaxation is exact on finite Abelian Cayley graphs on groups of exponent at most four. Second, we replace each generator $s$ of $S$ by a uniformly random element of its cyclic subgroup (including identity). If $r_s$ is the order of $s$, we let $\alpha(r_s)$ to be the average number of $\pm s$ steps needed to simulate such a move, and let $\rho(S)=\max_{s\in S}\alpha(r_s)$ be its worst case. Full cyclic averaging eliminates character phases and choosing a nontrivial character $\chi^*$ minimizing the auxiliary eigenvalue and taking $K=\mathrm{ker}\chi^*$ gives \[ \psi(G)\leq\psi_G(K)\leq\frac{q^*}{q^*-1} \cdot\rho(S)\cdot\mathrm{SDP}_{\mathrm{GL}}(G)\leq 2\rho(S)\cdot\mathrm{SDP}_{\mathrm{GL}}(G), \] where $q^*=|\chi^*(\Gamma)|$. If all generator orders are at most $R$, this is an $R/2$ approximation. Finally, we construct an infinite family of finite Abelian Cayley graphs with Goemans-Linial integrality gap exactly $16/15$.

We determine the full Sprague-Grundy sequence and its least period for a class of three-move subtraction games whose sequences are periodic from the start. Write the move set as $S=\{a,b,c\}$, with $0<a<b<c$ and $\gcd(a,b,c)=1$. The case $a=1$ is known and is summarized separately. For $a\ge2$ and $c\ne a+b$, we give three explicit sufficient tests for pure periodicity, associated with the candidate periods $a+b$, $c+a$, and $c+b$. For fixed $a,b$, the tests depend only on $c\bmod(a+b)$ and are computed from the losing positions of the two-move game $\{a,b\}$. Whenever a test succeeds, we give the losing positions in closed form, reconstruct the remaining values, and prove that the least period is the smallest candidate whose test succeeds. The construction shows how the added move $c$ modifies the two-move pattern to form a repeating block. We also give a uniform formulation of the known additive case $c=a+b$. For $a\ge2$, we conjecture that the tests cover every purely periodic non-additive game. In this range, when $c\ge2(a+b)$, we prove necessity for purely periodic games with least period at most $a+b$.

We study multiplicative inequalities among the coefficients of Lorentzian polynomials through the notion of bounded ratios. Our main structural result completely characterizes the cone of bounded ratios for Lorentzian polynomials of degree $n$ in $k$ variables. We show that the dual of the cone of bounded ratios is generated by equivalence classes of M-convex functions modulo affine functions. For ternary Lorentzian forms of arbitrary degree $n\ge3$, we show that the cone of bounded ratios is generated by triangular ratios and determine the optimal bounding constant of every bounded ratio. Furthermore, we characterize the pairs $(n,k)$ for which the cone of bounded ratios can be computed by tropicalizing products of $n$ linear forms in $k$ variables with nonnegative coefficients.

Recently, the study of the number of $k$-colored generalized Frobenius partitions, denoted by $c\phi_k(n)$, has witnessed renewed interest. In this paper, we investigate congruence properties of $c\phi_{16}(n)$ and $c\phi_{18}(n)$. Our main result is a proof of the conjecture of Cui, Gu, and Tang \cite{CGT25} that, for all $n\ge0$, $c\phi_{18}(3n+2)\equiv0\pmod{2187}$. The proof uses a $(p,k)$-parametrization together with $q$-series identities and dissections. We also establish congruences for $c\phi_{16}(n)$ modulo $1024$ and $2048$, and for $c\phi_{18}(n)$ modulo $8$ and $81$.

Let $C$ be an $[n,k]_q$ maximum distance separable (MDS) code with $4\le k\le q-3$, and suppose that it has a $2$-transitive permutation automorphism group. In this paper we show that $n\le q+1$, so the MDS conjecture holds for this class of codes.

We study a natural extension of Ramsey theory relative to the classes of maximally planar and maximally outerplanar graphs. This can be seen as a continuation of the study of `Planar Ramsey theory', introduced by Axenovich et al. The question we ask is the following: For a fixed family $\mathcal{K}$ of graphs and a pair of graphs $\{H,F\}$, does there exist an integer $r_{\mathcal{K}} (H, F)$ such that for every graph $G \in \mathcal{K}$ with $|G| \geq r_{\mathcal{K}}(H, F)$, every red/blue edge-colouring of $G$ admits a red copy of $H$ or a blue copy of $F$? When such an integer exists, we say $\{H,F\}$ is unavoidable in $\mathcal{K}$,, and otherwise $\{H,F\}$ is avoidable in $\mathcal{K}$. Our work focuses on this problem where $\mathcal{K} = \mathcal{K}_{\mathrm{MOP}}$ and $\mathcal{K} = \mathcal{K}_{\mathrm{MP}}$, which denote the families of maximal outerplanar (MOP) graphs and maximal planar (MP) graphs, respectively. This framework generalises the classical Ramsey problem relative to these classes, as the case with $\mathcal{K} = \{K_n \colon n \geq 2\}$ corresponds to classical Ramsey. We also study the corresponding Ramsey numbers for MOP and MP, which we denote as $r_{\mathrm{MOP}}(H, F)$ and $r_{\mathrm{MP}}(H, F)$. In the case when $\mathcal{K} = \mathcal{K}_{\mathrm{MOP}}$, we completely determine all unavoidable pairs $\{H, F\}$ with $|E(F)| \geq 2$, together with upper bounds and sometimes exact values of $r_{\mathrm{MOP}}(H, F)$. When $\mathcal{K} = \mathcal{K}_{\mathrm{MP}}$, we completely determine all unavoidable pairs in the diagonal case $\{H, H\}$ when $H$ is connected, showing that $H$ must be one of the graphs $P_3$, $P_4$, $P_5$, $K_{1, 3}$ or the fork graph $S_{2,1,1}$. This work opens up further possibilities in the study of Ramsey theory relative to a class, and we offer several open problems in this vein.

A total coloring of a graph is an assignment of colors to its vertices and edges so that adjacent or incident elements receive distinct colors, and it is equitable when the cardinalities of any two color classes differ by at most one. Stemock conjectured that every $4$-total coloring of a cubic graph of order less than $20$ is equitable. In this paper, we disprove this conjecture: the circular ladder $L_{12}$ admits a non-equitable $4$-total coloring and, moreover, no smaller counterexample exists: order $4$ is vacuous, and every $4$-total coloring of a cubic graph of order $6$, $8$, or $10$ is equitable. We also prove that the same property holds at order $14$. Our proofs rely on a decomposition lemma, which states that, in any $4$-total coloring of a cubic graph $G$, each color class consists of an independent set $S$ together with a perfect matching of $G-S$. We use the lemma to determine all possible color class configurations for orders $12$, $16$, and $18$, and we show that every listed configuration is attained. Finally, we provide a splicing construction showing that, for every even $n\geq16$, some connected cubic graph of order $n$ admits a non-equitable $4$-total coloring. We may conclude that $14$ is the largest order for which every $4$-total coloring of every cubic graph is equitable.

Dimension of partially ordered sets (posets for short) can be seen as a measure of how much space is needed to store posets. Refining the definition of dimension, or actually the local dimension, in this respect we obtain the notion of relative dimension. We discuss properties of relative dimension and we give bounds for relative dimension of some well-known families of posets.

We prove real-rootedness for the Chow polynomials of the noncrossing partition lattices by transferring tieless parking functions to finite-alphabet Smirnov words and applying an interlacing-preserving transition of M.~Leander. We also derive a triangular recurrence for peaks and ties and identify the peakless-tieless descent polynomial as the Narayana polynomial. For the toric $g$-contributions of Ehrenborg–Hetyei–Readdy, we exhibit a fixed-row common interlacer and establish real-rootedness of all nonnegative row sums. Individual real-rootedness follows in particular; Q.~Xiao also proved it by a different differential recurrence. We also give a second proof of the individual statement, by finite Schur–Szegő convolution, that does not use the common interlacer. These results prove Conjecture~4.2 of Xiao and Conjecture~11.2 of Ehrenborg–Hetyei–Readdy, with consequences for weakly 123-avoiding parking functions. We also prove real-rootedness for the image-size polynomial on all parking functions and for the ascent and descent polynomials of four two-pattern-avoiding classes.