Papers

We study Turán-type extremal problems for graphs containing a large $F$-sparse vertex set, meaning a vertex set whose induced subgraph contains few copies of $F$. For integers $r>s\ge 1$, we prove that if a $K_{r+1}$-free graph $G$ on $n$ vertices contains a set $M$ of size $m\ge \lceil sn/r\rceil$ such that $G[M]$ is $K_{s+1}$-free, then \[ e(G)\le m(n-m)+t_s(m)+t_{r-s}(n-m). \] We characterize the equality cases as the complete $r$-partite graphs whose vertex classes split into two balanced groups of total sizes $m$ and $n-m$, consisting of $s$ and $r-s$ classes, respectively. We also prove a color-critical extension for forbidden graphs that embed into a join of two edge-critical graphs, together with an asymptotic extension for general $H$-free graphs in which the prescribed large vertex set spans few copies of a fixed graph $F$ with $\chi(F)<\chi(H)$.

For an integer $L\ge2$, let $a=\lfloor L/2\rfloor$. Let $H(n,L)$ be the join of $K_a$ and an independent set of order $n-a$, with one extra edge in the independent set when $L$ is odd. We prove that, for fixed integers $q\ge4$ and $L>q$, and for all sufficiently large $n$, the graph $H(n,L)$ maximizes the number of copies of $C_q$ among all $n$-vertex graphs of circumference at most $L$. This settles a conjecture of Zhu, Győri, He, Lv, Salia and Xiao~[Bull. Lond. Math. Soc. 55 (2023)]. For even $q\ge6$, we also prove the boundary case $L=q$. We further determine the corresponding maximum when a long path is forbidden.

A binary Coxeter code associated with a finite Coxeter system $(W,S)$ is an ${\mathbb F}_2$-linear span of indicators of standard cosets of a fixed rank. Coxeter codes, introduced in a recent paper by N. Coble and A. Barg, are a generalization of Reed–Muller codes which arise when $W={\mathbb Z}_2^m$ is the Coxeter group of type $mA_1$. In that paper, the authors proposed a conjectural value for the minimum distance of a general Coxeter code. This conjecture is proved in the present work. As a consequence, we obtain a Coxeter-theoretic generalization of Reed's majority-logic decoding algorithm for Reed–Muller codes.

Following Alon, Hanneke, Holzman, and Moran (FOCS 2021), we define a partial concept class (PCC) as a family of partial functions \(f: V\to\{0,1,\ast\}\); equivalently, its concepts partition the ground set into black ($f^{-1}(1)$), grey ($f^{-1}(\ast)$), and white parts ($f^{-1}(0)$). Its VC dimension is defined by shattering sets on which the value $\ast$ is not taken. We study two geometric PCCs in real Banach spaces, both with a margin \(\delta>0\): expanded half-spaces, where the grey part is a strip of width at least \(\delta\) adjacent to a half-space, and expanded balls, where the grey part is an annulus of width \(\delta\) around a unit radius ball. Our main results are dimension-free upper bounds on the VC dimension of the PCC of expanded balls in \(L_p\parenth{\mu}\), \(1\le p<\infty\), including the non-Euclidean and algorithmically particularly relevant case \(\ell^d_1\). These bounds depend on the margin and on the radii, but not on the ambient dimension or the underlying measure space. These are extensions of the work of Bourneuf, Charbit, and Thomassé (FOCS 2025) who studied the PCC of expanded balls in Euclidean space, that is, $\ell_2^d$. We also prove lower bounds on the VC dimension that match the upper bounds in terms of the margin parameter $\delta$. Finally, we derive a Dense Neighborhood Lemma in \(L_p\)-spaces, again extending the known Euclidean results. Our method relies on the linearization of the distance through a map into a space of non-trivial Rademacher type, and then the use of a balanced signed-sum estimate, or a no-dimensional Radon theorem. The arguments rely on ideas from functional analysis that are clearly explained for the non-expert in that field.

The transmission of a vertex $v$ in a connected graph $G$ is the sum of distances from $v$ to all vertices in $G$. A transmission irregular (TI) graph is a connected graph in which any two distinct vertices have different transmissions. We extend the concept of transmission to edges by defining the transmission of an edge as the sum of the transmissions of its two endpoints. A connected graph can now be called edge transmission irregular (ETI) if any two distinct edges have different transmissions. We show that almost all graphs are not ETI and then investigate several related order realizability problems involving chemical ETI graphs. In particular, we prove that for every $n \ge 15$, there exists a subcubic tree of order $n$ that is both TI and ETI.

We construct the planar Linares–Otto–Tempelmayr Hopf algebra, thereby filling the missing planar noncommutative multi-index corner in the square relating the LOT, Butcher–Connes–Kreimer, and Munthe-Kaas–Wright Hopf algebras. Starting from the free associative algebra on a weighted alphabet $\mathbb Z_{\ge -1}\times A$, we define an insertion-type product yielding a post-Lie structure on the Lie algebra generated by the linear span $V(A)$ of weight $-1$ monomials whose proper left prefixes all have nonnegative weight, and the Guin–Oudom construction then produces the planar LOT Hopf algebra. We introduce a planar tree fertility map from decorated planar rooted trees to monomials in $V(A)$, prove that it is a linear isomorphism, and obtain a natural Hopf algebra isomorphism with the Munthe-Kaas–Wright Hopf algebra. We further derive an explicit coproduct formula in terms of left-admissible cuts, establish the extraction-contraction coproduct, and construct a word symmetrization operator compatible with the classical tree symmetrization operator.

A Hopf monoid structure on extended generalized permutahedra (EGP) was recently introduced by M.Aguiar and F.Ardila. We investigate the existence of a cointeracting bialgebra structure on EGP's. We show that a suitable notion of cointeraction exists, not in the classical comodule sense, but via the framework of measuring algebras. The comodule-type map assigns to each polyhedron the sum of pairs of face and tangent cone at the face. EGP's and affine cone EGP's form the cointeracting bimonoids in species with EGP as a third measuring structure. EGP's are in bijection to extended submodular functions. For an EGP, we also describe explicitly the submodular functions of its faces and tangent cones. The braid fan and its relation to preorders play a key role in this description.

In present paper, with the help of the Faà di Bruno formula and identities of partial Bell polynomials, the author establishes explicit formulas of the Gauss hypergeometric functions \begin{gather*} {\,}_2F_1\biggl(\frac{1-n}{2},\frac{2-n}{2};\frac{3}{2}-m;z^2\biggr), \quad {\,}_2F_1\biggl(-\frac{n}{2},\frac{1-n}{2};\frac{1}{2}-m;z^2\biggr),\\ {\,}_2F_1\biggl(a,a+\frac{1}{2};\frac{3}{2}-m;z^2\biggr), \quad {\,}_2F_1\biggl(a,a+\frac{1}{2};\frac{1}{2}-m;z^2\biggr) \end{gather*} for $m,n\in\mathbb{N}$ and $a\in\mathbb{C}$, and then derives two combinatorial identities \begin{equation*} \sum_{k=0}^{m}\frac{2^k}{k!} \binom{2m-2k}{m-k} \sum_{\ell=0}^{k} \frac{(-1)^\ell}{2^\ell} \frac{(2k-2\ell-1)!!}{(n-\ell)!} \binom{2k-\ell-1}{\ell-1} =\frac{1}{n!}\binom{2m-n}{m} \end{equation*} and \begin{equation*} \sum_{k=1}^{m}\frac{1}{(k!)^2}\binom{2m-2k}{m-k} \sum_{\ell=1}^{k} \binom{k}{\ell}\ell(2k-\ell-1)! (2a)_\ell =\binom{2m+2a}{m}, \end{equation*} where $m\in\mathbb{N}_0$, $n\in\mathbb{Z}$, and $a\in\mathbb{C}$. These newly-established identities generalize the nice and beautiful combinatorial identity \begin{equation*} \sum_{k=0}^{n} \frac{2^{k}}{k!}\binom{2n-2k}{n-k} \sum_{j=0}^{k}\frac{(-1)^{j}}{2^j} \frac{(2k-2j-1)!!}{(n-j)!} \binom{2k-j-1}{j-1} =\frac{1}{n!}, \quad n\in\mathbb{N}_0, \end{equation*} which was obtained in Theorem 4 of the recent paper "F. Qi, C.-Y. He, and D. Lim, Explicit formulas of two Gauss hypergeometric functions and several combinatorial identities, Discrete Appl. Math., Vol. 393 (2026), 215–229. DOI: https://doi.org/10.1016/j.dam.2026.06.023".

Alesandroni proved that Betti numbers of monomial ideals in at most four variables are independent of the characteristic of the base field, while characteristic-dependent Betti numbers occur in six variables. We prove that the five-variable case is characteristic-independent. More precisely, if $S=k[x_1,\ldots,x_5]$ and $M\subseteq S$ is a monomial ideal, then the multigraded, graded, and total Betti numbers of $S/M$ are independent of $\operatorname{char}(k)$. The proof reduces arbitrary monomial ideals to squarefree twin ideals and then applies Hochster's formula. The topological input is that simplicial complexes on at most five vertices have torsion-free integral homology. The six-variable example arising from the six-vertex triangulation of $\mathbb{RP}^{2}$ shows that the bound is sharp. We also record a computation of the graded Betti tables of squarefree monomial ideals in five variables up to relabeling.

The Token Jumping and Sliding Token problems are fundamental reconfiguration problems defined on the independent sets of an undirected graph. Given two independent sets $I$ and $J$, each of size $k$, these problems ask whether there exists a sequence of elementary operations transforming $I$ into $J$ such that every intermediate configuration is also an independent set of size $k$. Suppose a token is placed on each vertex of $I$: in Sliding Token, an operation moves a token from a vertex $u \in I$ to an adjacent vertex $v \notin I$; in Token Jumping, the token may instead move to any vertex $v \notin I$. While both problems are $\mathsf{PSPACE}$-complete on general graphs, polynomial-time algorithms for one or both variants have been developed for several graph classes, including trees, block graphs, bipartite permutation graphs, cographs, $P_4$-tidy graphs, and interval graphs. In this paper, we prove that both problems are solvable in polynomial time on threshold signed graphs, also known as Dilworth-2 graphs. A graph $G=(V,E)$ is a threshold signed graph if there exist a mapping $a:V\to\mathbb{R}$ and positive real constants $S,T>0$ such that $|a(v)|< \min\{S,T\}$ for all $v \in V$, and for any distinct vertices $u,v\in V$, $\{u,v\}\in E$ if and only if $|a(u)+a(v)|\ge S$ or $|a(u)-a(v)|\ge T$. More generally, we also show that Token Jumping can be solved in time $n^{O(\mathcal{D}(G))}$, where $\mathcal{D}(G)$ denotes the Dilworth number of $G$. Thus, Token Jumping belongs to $\mathsf{XP}$ when parameterised by the Dilworth number. This graph class is a subclass of permutation graphs, for which the complexity of these problems remains open, and is incomparable with the class of bipartite permutation graphs studied by Fox-Epstein et al. (ISAAC, 2015).

We prove that, on finite graphs of rank-width at most two, VR-recognizability and counting monadic second-order definability coincide. This advances the recognizability-versus-definability problem from bounded linear clique-width to the first nontrivial bounded rank-width level beyond the rank-width-one split-decomposition case. The proof first treats split-prime graphs. The maximal partial-tree theory of Clark and Whittle organizes the non-sequential cut-rank-two separations, while a single strong separation orients all strong equivalence classes and yields a CMSO-definable laminar family of canonical cores. Although the auxiliary partial tree is not itself transduced, it proves that every canonical local piece has a port-contiguous layout of uniformly bounded linear rank-width. The width argument uses partition atoms and the branch-width-three display theorem of Hall, Oxley, Semple, and Whittle and does not assume that graph torsos remain prime. Coherent ordered rank-two frames then permit a finite-state bottom-up evaluation whose local transitions are definable by the bounded-linear-clique-width theorem of Bojańczyk, Grohe, and Pilipczuk. Finally, the CMSO-transducible canonical split decomposition lifts the result from prime graphs to arbitrary graphs of rank-width at most two.

We study three closely related questions arising from the recent work of Andrews and El Bachraoui on the two-color partition series \[ S_1(q)=\sum_{n\ge0}s_1(n)q^n=\sum_{a\ge0}q^a(-q^{a+1};q)_\infty^2 \] and its odd companion, denoted by $T_o(q)$. First, for the eta-normalized companion \[ C(q)=(q;q)_\infty T_o(q)=\sum_{n\ge0}c(n)q^n, \] we prove a strong form of the Andrews–El Bachraoui sign conjecture that $\limsup c(n)=+\infty$ and $\liminf c(n)=-\infty$. Second, we construct an involution using the Franklin-type involution of Chen and Liu to combinatorially explain Andrews–El Bachraoui congruence for $s_1(n)$ modulo 4. Third, we introduce a two-variable refinement of $S_1(q)$ which records the difference of the lengths of the two colored components. Using Ramanujan's partial theta identity and heat-type equations, we obtain a closed formula for all of its even moments, and we show that the eta-normalized moments satisfy termwise congruences modulo $p^{2k}$ for every prime $p\equiv5\pmod6$.

In this paper, we study pinned $k$-star distance sets associated to compact subsets of $\mathbb{R}^n$, $n\geq 2$. For pins $x_1,\dots,x_k\in E$, the pinned $k$-star distance set is \[ \Delta_{x_1,\dots,x_k}^{k\text{-star}}(E) = \{(|x_1-x|,\dots,|x_k-x|):x\in E\}\subset\mathbb{R}^k. \] We obtain improved Hausdorff-dimension thresholds on $E$ guaranteeing that pinned $k$-star distance sets have positive $k$-dimensional Lebesgue measure. The main analytic input is a reformulation of the connection, first observed in \cite{IPPS22}, between $k$-stars in $\mathbb{R}^n$ and pinned dot products on the paraboloid in $\mathbb{R}^{n+1}$. In our framework, $L^2(\mathbb{R}^k)$ estimates for the densities of pinned $k$-star distance measures are reduced to a weighted Fourier extension estimate for the paraboloid whose weight is defined explicitly in terms of Frostman measures on $E$. For $1\leq k<n$, this yields the threshold \[\dim(E)>\alpha_{+}(n,k):=\frac{n^2+nk+k}{2n+1}=\frac{n+k-1}{2}+\frac14 +\frac{2k+1}{4(2n+1)}.\] Using the graph-building machinery of \cite{BFOPR2026}, our positive-measure results for $k$-stars can be used as building blocks for finite distance graph configurations with prescribed pins. As a consequence, we improve the best-known positive-measure thresholds for pinned $k$-simplices in every dimension $n\geq 3$ and for necklace graphs (cycles) in every dimension $n\geq 3$. We further prove nonempty interior results for $k$-stars. In the special case $k=1$, corresponding to the pinned nonempty interior of the distance set $\Delta_{x}(E)=\{|x-y|\colon y\in E\}$, we use a sharper argument to improve the pinned nonempty-interior thresholds of \cite{BFOP2026} in all dimensions $n\geq 4$.

We introduce the ideal zero-product probability, a new probabilistic invariant associated with a finite commutative ring $R$, defined by \[ \zeta_k(R) = \frac{ |\{(I_1,\ldots,I_k)\in\mathcal I(R)^k : I_1\cdots I_k=(0)\}| } {|\mathcal I(R)|^k}, \] where $\mathcal I(R)$ denotes the set of all ideals of $R$. This quantity gives the probability that the product of $k$ independently and uniformly chosen ideals is the zero ideal. We establish its basic properties, including invariance under ring isomorphisms, monotonicity in $k$, and multiplicativity with respect to finite direct products. Explicit formulas are obtained for finite fields, finite Boolean rings, finite chain rings, and finite principal ideal rings. For finite chain rings, we prove that the invariant depends only on the Loewy length. We also derive closed formulas using inclusion–exclusion and bounded compositions, together with generating functions. Finally, we study the asymptotic behaviour of $\zeta_k(R)$ and prove that it converges to $1$ as $k\to\infty$. We also compare the ideal zero-product probability with the classical zero-product probability of ring elements on finite chain rings, obtaining explicit formulas and showing that the two invariants capture fundamentally different structural information.

The VC-dimension is a fundamental measure of the complexity of a set system. In this paper, we introduce and study a colorful variant of VC-dimension that captures the behavior of set systems on colored ground sets. By studying this new notion, we obtain a variety of geometric results. First, we prove that separable abstract convexity spaces with Radon number $D$ admit a Tverberg theorem with Tverberg number $O(D^2 r \log r)$. This bound significantly improves the $O(Dr^2\log r)$ bound of Alon and Smorodinsky from SODA'26 and is the first quasi-linear bound in $r$, in which the dependence on $D$ is not super-exponential. Second, we prove the first colorful $k$-wise Tverberg theorem for separable abstract convexity spaces. Using this theorem, we obtain a colorful selection lemma with $O(D^3)$ colors, an uncolored selection lemma for subsets of size $O(D^3)$, a weak $\varepsilon$-net theorem with nets of size $O_D(\varepsilon^{-O(D^3)})$, and a $(p,q)$-theorem with exponent of $\mathrm{poly}(D)$. All these quantitative bounds are significantly better than the best previously known general bounds for abstract convexity spaces. Finally, we extend our method to obtain a colorful Tverberg theorem for unions of convex sets, generalizing the uncolored theorem of Alon and Smorodinsky (SODA'26).

We study synchronous Boolean dynamics on finite loopless directed graphs in which a vertex is active at the next time step exactly when its number of active in-neighbors is prime. We call these systems Pulse Graphs. Let $L(n)$ denote the largest attractor period realizable on $n$ vertices. Exhaustive enumeration gives \[ L(1),\ldots,L(5)=1,1,1,3,9. \] Our main result determines the exponential order of the maximum period: \[ 2^{n-3}-1\leq L(n)\leq2^n-n-1 \qquad(n\geq5). \] The lower bound is obtained by implementing a maximal-length affine feedback register using prime-count logic gates. For $n\geq6$, the construction is loopless, has maximum in-degree five, and uses only $O(n)$ edges. For odd $n\geq7$, a period-3 control module improves the lower bound to \[ 3(2^{n-4}-1). \] For complete directed graphs, we derive an exact update formula, classify all attractors as fixed points or complement two-cycles, prove that every orbit reaches its eventual attractor within three updates, and count the attractors explicitly. We also derive the activation probability under independent random inputs. For sparse random directed graphs, the associated prime-Poisson mean-field map undergoes a nondegenerate fold at \[ c_\ast\approx3.824963, \qquad \rho_\ast\approx0.368241, \] with local bistability immediately above the threshold.

We prove Krattenthaler's conjecture from 2001 about the $1/3$-phenomenon for lozenge tilings of semiregular hexagons. In a first step we reduce the problem to the case of regular hexagons. In a second step we further reduce the question to a special case already covered in the literature. This is achieved by vast application of the celebrated Zeilberger Algorithm and the Holonomic Ansatz.

Graphs that change over time arise throughout applications, but there is no single standard way to decompose them into smaller pieces. In this paper, we propose a systematic categorical method for doing so. The main idea is to combine structured decompositions, which generalize graph decompositions, such as tree-decompositions, with persistent narratives, which model time-varying data as diagrams. We prove that, under suitable categorical hypotheses, any static theory of decompositions can be lifted to a corresponding temporal theory. As case studies, we apply this construction to time-varying graphs and recover natural temporal analogues of ordinary tree-width, complemented tree-width, and the tree-independence number.

For positive integers $n$ and $m$, let $f(n,m)$ be the least integer $h\ge0$ such that $(m,m+h]$ contains distinct integers $a_1,\ldots,a_n$ satisfying $i\mid a_i$ for $1\le i\le n$, and put $F(n)=\max_{m\in\mathbb{N}} f(n,m)$. A recent theorem of van Doorn [INTEGERS, 2026; arXiv:2601.16972] gives $F(n)-f(n,n)>0.36\,n\log n/\log\log n$ for sufficiently large $n$. We prove \[ \liminf_{n\to\infty} \frac{F(n)-f(n,n)}{n\log n} \ge \frac{1}{\mathrm{e}}. \] Thus, for every fixed $c<1/\mathrm{e}$ and all sufficiently large $n$, some interval of length $c\,n\log n$ contains no system of pairwise distinct multiples of $1,2,\ldots,n$. The proof applies an Erdős–Pomerance smooth-number obstruction at starting points $m\asymp n\log n$, using local saddle-point estimates of Hildebrand and Tenenbaum.

We provide a definitive analysis of the number of correct guesses in the complete-feedback card guessing game after an asymmetric single-shelf shuffle with parameter $p\in (0, 1)$. We explicitly describe the optimal strategy that maximizes the expected number of correct guesses. We study the number of correct guesses, under an optimal strategy, using methods from analytic combinatorics. In addition, we find the explicit distribution for the number of correct guesses, and thus find the mean and the variance for the number of correct guesses. We show that the distribution of the number of correct guesses is log-concave. We also study the limiting behaviour of the number of correct guesses as the number of cards goes to infinity. In particular, we prove a (local) central limit theorem and a large deviation principle with an explicit rate function. We also prove phase transitions for the number of correct guesses near $p=0$ and $p=1$. Prior to this work, only the optimal strategy and the expected number of correct guesses under the optimal strategy were known for the special case of $p=1/2$.

We study the additive structure of dense subset sum in multi-dimension, and use the structure to develop efficient algorithms for the dense subset sum problem. More precisely, given a set $A$ of $n$ vectors in the $d$-dimensional hyperrectangle $[N_1]\times [N_2]\times\cdots\times [N_d]$, we study the structure of $\mathcal{S}(A)$, which is the set of all subset sums of $A$. We focus on the dense regime of the problem where $n \gg \sqrt{\Phi}$ and $\Phi = N_1 \times \cdots \times N_d$. We show that for any constant $d\geq 1$, if $n \gg \sqrt{\Phi}$, then $\mathcal{S}(A)$ contains a long generalized progression in multi-dimension. If we further have that no non-trivial lattice can contain the majority of $A$, then $\mathcal{S}(A)$ contains all the integer points in the zonotope $\{x_1\vec{a}_1 + \cdots + x_n\vec{a}_n: o(1)\leq x_j \leq 1-o(1), x_j \in \mathbb{R}\}$. Compared to the previous results for $d \geq 2$, our result significantly reduces the density threshold and enlarges the region inside which all the integer points belong to $\mathcal{S}(A)$. Also, it matches the bound for the 1-dimensional case. Using our combinatorics result, we also develop an $\tilde{O}(n)$-time algorithm for the dense subset sum problem in multi-dimension.

The metric dimension, which has lots of variants and numerous applications in other fields, is one of the most important and most extensively studied topics in metric graph theory. Results in which resolvability is achieved by considering multisets of distances from a fixed vertex, instead of vectors as in the original version, are surveyed. The concepts discussed are multiset dimension, outer multiset dimension, local multiset dimension, edge multiset dimension, and $k$-multiset antidimension. Along the way, sharp lower bounds on the outer multiset dimension of diameter two graphs and join graphs with edgeless graphs are proved, which solves two open problems from the literature. New results on graphs with local multiset dimension equal to two are also proved. In particular, such graphs are characterized among block graphs. Finally, a list of open problems from the literature is compiled, and several new problems are added to the list for future research.

We study a family of highly symmetric instances of the stable marriage problem built from regular actions of finite groups. Given a finite group G of order n and an ordering A of its elements, we define the regular anti-phase template P(G,A). These templates have n canonical stable matchings. We show that the anti-phase condition is canonical: among automorphism-maximal profiles, the anti-phase templates are exactly those satisfying a constant rank-sum identity. This gives a structural characterization rather than an ad hoc definition. We prove a generator criterion and its exact converse: the stable set has size n if and only if each adjacent quotient generates the group. This result holds for all finite groups and does not require commutativity. We further establish a counting lower bound for the number of stable matchings in terms of subgroup indices. The bound is sharp for groups of order at most 5 and for all groups of order 4; in particular, it yields at least 10 stable matchings for the Klein group, with equality confirmed by enumeration. Finally, we show that cyclic profiles do not always produce chains; the structure depends on the ordering. All computational claims are verified by an accompanying script.

We study the graphs $MECS_{b,n}^a \cong \overline{K}_a \join \big(n(K_b+K_2)\big)$, obtained by attaching an independent set of size $a$ to $n$ disjoint copies of the block $K_b+K_2$. For $n=1$, we get $MECS_{b,1}^a$, and recover the results of one-block case studied in [Anand, Gupta, Rather and Singh, Homological invariants of some complete split-like graphs, Beitr. Algebra Geom. (2025)]. Using Hochster's formula, tensor products of minimal free resolutions over disjoint variable sets, and the Betti-number formula for graph joins, we derive explicit descriptions of the independence complex, independence polynomial and its analytic properties, Hilbert series, linear and quadratic Betti strands, regularity, projective dimension, and several structural invariants of $MECS_{b,n}^a$. We further classify the well-covered and unmixed members, compute induced matching numbers, show that the family is never Cohen–Macaulay, and record algorithmic procedures for evaluating the Betti data.

Reciprocal matrices are a fundamental tool in the Analytic Hierarchy Process (AHP), where priority vectors are typically derived from pairwise comparisons. The efficiency of a positive vector, in the sense of Pareto optimality, can be characterized through the strong connectivity of a directed graph $G_{A,w}$ associated with a reciprocal matrix $A$ and a vector $w$. In this paper, we investigate the structure of the condensation digraph of $G_{A,w}$ in the case where $w$ is inefficient, with particular emphasis on the Perron vector. We provide a characterization of this structure and derive several constructive results. In particular, we show how efficiency can be achieved by modifying a single pair of reciprocal entries, and we construct an augmented reciprocal matrix whose efficient vector extends $w$. Finally, we propose a procedure to transform $w$ into an efficient vector for $A$.

The Combinatorial Discretizable Distance Geometry Problem combines a finite binary lateration process with additional distance constraints. When predecessor sets are not consecutive, these pruning constraints interact in ways that make the symmetry-based counting methods available for molecular instances insufficient. We establish an exact, dimension-uniform counting theorem for seed-fixed feasible realizations under strict discretization and a generic feasible framework assumption. Our approach identifies partial reflections through seed-free connected components of the lateration skeleton. These reflections are encoded by binary masks, while a labeled constraint matrix detects combinations that preserve all pruning distances. The feasible branch choices split into constrained choices generated by compatible partial reflections and unconstrained choices outside the predecessor closure of the pruning endpoints. The resulting count is obtained from graph operations and rank computations over the binary field, without enumerating the lateration tree. Completeness follows from the characterization of generic realizations of the relevant joined graphs by partial reflections. The theorem applies in every Euclidean dimension, including dimension one.

A theorem of Payan says that a cubelike graph cannot have chromatic number exactly three. A nearby question, usually discussed as Payan's finite $(0,2)$-graph question, asks whether a finite graph in which every two distinct vertices have either zero or two common neighbours can have chromatic number exactly three. The finite hypothesis is meaningful: infinite three-chromatic $(0,2)$-graphs can be constructed \cite{Payan1992}. We prove that every finite three-colourable $(0,2)$-graph is bipartite. Thus, no finite $(0,2)$-graph has chromatic number exactly three.

For integers \(k\le s<t\), the hypergraph Erdős–Rogers function \(f^{(k)}_{s,t}(n)\) is the largest integer \(m\) such that every \(n\)-vertex \(K_t^{(k)}\)-free \(k\)-graph contains a set of \(m\) vertices spanning no copy of \(K_s^{(k)}\). We prove that, for every fixed \(s\ge4\), \[ f^{(4)}_{s,s+1}(n)=(\log n)^{o(1)}, \] thereby resolving a problem posed by Conlon, Fox and Sudakov. The key input is a new \(3\)-uniform estimate: for every fixed \(s\ge3\), \(f^{(3)}_{s,s+1}(n)=O(\frac{\log n}{\log\log n})\), which improves the logarithmic upper bound of Dudek and Mubayi. The proof develops a probabilistic pair-coloring construction based on a robust auxiliary palette and hypergraph containers. As a further consequence, we obtain \(f^{(k)}_{k+1,k+2}(n)=(\log_{(k-3)} n)^{o(1)}\) for every fixed \(k\ge5\), making substantial progress towards a conjecture of Mubayi and Suk.

Chan and Pak introduced the relative linear extension ratio $\rho(P,x)=e(P)/e(P-x)$, where $e(P)$ is the number of linear extensions of a finite poset $P$, and let $\nu(c,d)$ be the least number of elements of a poset that realizes $\rho(P,x)=d/c$. They proved that $\nu(c,d)\le d/c+O(\log d\log\log d)$ for $d\ge 3c$, and asked whether the hypothesis $d\ge 3c$ can be relaxed to $d\ge(1+\varepsilon)c$ or removed. We prove the fixed-gap form of this question: for every fixed $\varepsilon>0$, $\nu(c,d)\le \frac{d}{c}+O_{\varepsilon}(\log d\log\log d)$ whenever $d\ge(1+\varepsilon)c$, and the implied constant is absolute once $d\ge 2c$. The new ingredient is a one-element overlap construction: if $x$ is minimal in $P$ and $y$ is minimal in $Q$, then there is a poset $R$ with $|R|=|P|+|Q|-1$ and an element $z$ such that $\rho(R,z)=\rho(P,x)+\rho(Q,y)-1$. Together with the continued-fraction construction of Chan and Pak and Rukavishnikova's tail bound for sums of partial quotients, this removes the factor $3$ in their range. We also show that the fixed-gap hypothesis is essentially optimal for this construction. In the range $1 < d/c < 2$, with $h=d-c$, the size bound the construction can certify is at least $\lfloor c/h\rfloor$, so the method reaches the stated error term only when $h$ is at least of order $c/(\log c\log\log c)$. The remaining obstruction to removing the hypothesis is a short-interval problem for sums of partial quotients, which we describe. The deductive part of the argument has been checked with the Lean proof assistant.

We study maximum-sum red-blue matchings and matching equilibrium for finite planar point sets. For a red-blue perfect matching $M = \{(a_i,b_i) : 1 \le i \le n\}$, we define the gain of a directed red cycle as the change in total weight produced by cyclically shifting the corresponding blue partners. We prove that $M$ is maximum-sum if and only if every directed red cycle has nonpositive gain, and we derive a geometric sufficient condition for optimality from cyclic intersections of distance-difference regions. We then characterize balanced matchings, in which all red-blue perfect matchings have the same total weight. Equilibrium is shown to be equivalent to vanishing cycle gains, to an additive form of the distance matrix, and to a common level-set condition for distance-difference functions. In the squared Euclidean case this yields an orthogonality classification, while in the Euclidean case it yields a hyperbolic level-set description and a collinear-separation classification in the nondegenerate setting.