Papers

We give the first positive combinatorial rule for the multiplicities of irreducible $GL$-representations in the coordinate rings of type $A$ quiver orbit closures, valid for every orientation of the quiver. Previously, for the special case of varieties of complexes, work of De Concini–Strickland in the early 1980s gave an implicit description of these multiplicities. The combinatorial objects in our rule carry a crystal structure whose highest-weight elements compute these multiplicities.

The semi-random graph process is an adaptive random graph process in which an online algorithm is initially given an empty graph on $n$ vertices. In each round, a vertex $u$ is presented to the algorithm independently and uniformly at random. The algorithm then adaptively selects a vertex $v$, and adds the edge $uv$ to the graph. We also consider the offline version of the process in which the algorithm is given the entire sequence of random vertex choices before the selection takes place. For a given graph property, the objective of the algorithm is to force the graph to satisfy this property asymptotically almost surely in as few rounds as possible. In this paper, we focus on the property of being triangle-saturated and establish upper and lower bounds on the number of rounds required to construct a triangle-saturated graph in both the online and offline versions of the process.

Let z(m,n;s,t) be the largest number of ones in an m x n zero-one matrix with no s x t all-ones submatrix. Roman's 1975 inequality remains the best general upper bound for s>=3, but it is not attained on a large part of the range just below the design threshold T=(t-1)C(m,s)/(s+1). The proof has two steps. First, for n=T-c with 1<=c<=sT/(s+2), Roman's bound equals the elementary counting bound (s+1)(T-c)+floor(2c/s), adding nothing beyond a budget inequality and convexity. Second, attainment forces all but at most one column to have size s+1 or s+2; each such column has a point lying in a number of s-sets divisible by d=gcd(s,C(s+1,2)), pinning the leftover coverage there to a single residue mu mod d, which a global count rules out. With r=c mod s and slack sigma(r) depending only on s, we prove z(m,T-c;s,t) <= Rom(m,T-c)-1 whenever 1<=sigma(r)<d and m*mu != s*sigma(r), or mu != 0 and m*mu > s*sigma(r). The first case is an odd-s phenomenon confined to one residue class, giving order-m^s values of n; the second needs mu != 0 but covers the whole interval once m exceeds a threshold depending only on s and mu. For s=4, t=2, m=28 it covers all 2730 values of n; when c=(s+1)/2 and an s-(m,s+1,t-1) design exists, z=(s+1)(T-c) exactly. Finally we relate the obstruction to linear programming: the relaxation over all 2^m subset variables collapses, under symmetrisation, to the counting bound, so no linear relaxation of the covering constraints alone can beat the bound of Chen, Horsley, and Mammoliti (arXiv:2310.12685, "Zarankiewicz numbers near the triple system threshold"). For the refined program of Davies, Gill, and Horsley, its optimum is still attained at the Roman vertex on an explicit sub-family, and we record where their program does better.

A fixed simplex, randomly projected into three dimensions and joined in Hamiltonian order, produces a rich and unusually tractable model of random stick knots. We prove that Gaussian projections and Haar-random Stiefel projections have exactly the same knot-type law, despite having different metric shapes, and that at every stick budget the model gives positive probability to precisely the knot types realizable with that many sticks. Its linear-algebraic structure yields an exact marginal distance law, an exact mean planar-crossing count, and crossing concentration, while in the first nontrivial six-stick case the complete tetrahedral sign pattern gives an exact unknot-versus-handed-trefoil classifier for every generic sample. The result is a direct bridge from random projections and finite sign geometry to the topology of random knots.

Let $\alpha\models n$. We define a two-variable specialization $Z_\alpha(t,q)$ of the ribbon basis of noncommutative symmetric functions from cycle enumerators of an ordinary permutation and a rooted permutation, with $q$ recording reflection length. We realize $n!Z_\alpha(t,q)$ as the shifted bigraded Euler characteristic of an $\mathfrak S_n$-equivariant ordered-set-partition complex. When $\alpha$ has at most one odd part, each total decoration determines a set of simultaneous factorization cuts, and its fiber is the classical ribbon complex indexed by that cut set. This gives explicit nonnegative ribbon expansions for every bigraded homology representation. Organizing the complexes on labelled finite sets yields a counital differential graded comonoid in the Cauchy monoidal category of species, whose cut coproduct is compatible with the fiber decomposition. At a factorization cut, the induced map on top homology is injective; its cokernel has the near-concatenation ribbon character, and the kernel of the aggregate reduced cut coproduct on homology is $H_1$. For the zigzag compositions $\delta_n$, $Z_{\delta_n}(t,-1)$ is the order polynomial of the alternating fence. We prove \[ n!Z_{\delta_n}(t,-u)\in\mathbb N[t,u] \] using coefficientwise nonnegative recurrences derived from a Riccati equation. The same cut data define a nonnegative factorization defect $d=\lceil n/2\rceil-k-j$, which controls the homological support and makes the Euler sign constant on each defect layer. We also determine the full defect-zero edge by explicit Frobenius-character formulas.

This paper studies the Shannon capacity of lexicographic products of finite simple graphs, together with the Lovász theta function and the fractional Haemers number. The Shannon capacity is proved to be supermultiplicative under lexicographic products in either order, and these products are compared with the strong product. We explicitly construct three countably infinite families of lexicographic powers based on the Schläfli graph, the McLaughlin graph, and its second subconstituent; in each family, pairing each member with its complement yields strict supermultiplicativity and arbitrarily large multiplicative gaps. Bounds and exact-capacity criteria for lexicographic products are derived, and the resulting upper bounds are shown to be incomparable. The capacities of lexicographic products involving Kneser graphs, their complements, and $q$-analogues of Kneser graphs are determined. It is also shown that a lexicographic product with a complete outer factor preserves the Shannon capacity of an arbitrary inner factor. The capacities of iterated lexicographic powers are determined, including those of self-complementary graphs that are vertex-transitive or strongly regular. Elementary, self-contained proofs are also given for three known results: the multiplicativity of the Lovász theta function and the fractional Haemers number under lexicographic products, and the equality of the fractional and ordinary Lovász theta functions. Finally, an open problem concerning the Shannon capacities of lexicographic and strong products is posed.

Tuza conjectured that every finite simple graph $G$ satisfies $\tau(G) \leq 2\nu(G)$, where $\nu(G)$ is the maximum number of pairwise edge-disjoint triangles and $\tau(G)$ is the minimum number of edges whose deletion makes $G$ triangle-free. Puleo proved the conjecture for every graph of maximum average degree less than $7$; this covers maximum degree at most $6$ but no $7$-regular graph. We prove the conjecture for maximum degree at most $7$. The proof uses Puleo's reducible-set framework. At average degree seven his discharging step no longer forces a reducible configuration. In a minimal $7$-regular counterexample every vertex link is a connected seven-vertex graph outside the weak Konig-Egervary class. An exhaustive census of such links supplies, at every vertex, an incident edge lying in four, five or six triangles. We prove that its endpoints form a reducible pair: codegrees five and six use a packing and covering template and Fano-plane witnesses, while codegree four uses an explicit catalogue of 1,144 machine-checked local certificates. We do not provide a human-readable proof of that catalogue; the certificates and their verifiers accompany the paper. The constant $2$ is sharp already at maximum degree three.

We prove the inequality $R(k+1,s+1) \ge R(k,s) + 2k + 2s$ for classical Ramsey numbers, valid for all $5 \le k \le s$, and formalize the proof in Lean 4. As a consequence, we obtain the new lower bound $R(12,12) \ge 1641$.

Chartrand and Zhang asked whether there exists a graph $G$ without isolated vertices whose target Ramsey number satisfies $\mathrm{TR}(G) > \mathrm{R}(G)$. We answer the question affirmatively, even under strong structural restrictions. If $\Gamma_t = P_t \square P_t$ is the square $t \times t$ grid, then the elementary counting bound of Chartrand and Zhang gives $\mathrm{TR}(\Gamma_t) \geq 2t(t-1)+1$, whereas a theorem of Mota, Sarkozy, Schacht and Taraz gives $\mathrm{R}(\Gamma_t) = (3/2 + o(1))t^2$. Consequently, $\mathrm{TR}(\Gamma_t) > \mathrm{R}(\Gamma_t)$ for all sufficiently large $t$, so there are infinitely many connected, planar, bipartite counterexamples of maximum degree four. Higher-dimensional grids show that the ratio $\mathrm{TR}(G)/\mathrm{R}(G)$ is unbounded on connected bipartite graphs, while each fixed-dimensional witnessing family has bounded maximum degree. We also record an independent construction of disconnected counterexamples from the theorem of Burr, Erdos and Spencer on Ramsey numbers of multiple copies: if a fixed graph $H$ satisfies $e(H) > 2v(H) - \alpha(H)$, then $\mathrm{TR}(qH) > \mathrm{R}(qH)$ for every sufficiently large $q$.

For every odd integer $t\ge17$, we prove that an explicit circulant graph on $5t-10$ vertices is doubly saturated $R(3,t)$-good. The graph is triangle-free and has independence number $t-1$. Adding any nonedge creates a triangle, whereas deleting any edge creates an independent set of order $t$. This settles Conjecture 2 of Przybocki, Mackey, Heule, and Subercaseaux. A cyclic sumset identity and explicit witnesses prove the local saturation properties. Writing $t=2m+1$, a five-layer reduction proves the independence bound via a uniform affine certificate for $m\ge30$ and an exhaustive checker for $8\le m\le29$. The checker soundness and the complete argument are formalized in Lean 4.32.2. Consequently, $2t-1\le \operatorname{DS}(3,t)\le 5t-10$ for odd $t\ge17$.

In this paper, we obtain new upper and lower bounds on the colorful Helly number and the Tverberg number in an abstract convexity space with Radon number $r$. We prove an upper bound of $(r-1)2^r$ on the colorful Helly number, which is a factor $O(r)$ far from the lower bound, $2^{r-1}-1$. The best previous bound, by Holmsen and Lee (2021), was $r^{r^{\log r}}$. As a consequence, we obtain improved quantitative bounds for fractional Helly numbers, the selection lemma, weak $\varepsilon$-nets, and the $(p,q)$-theorem, in abstract convexity spaces. Furthermore, using the improved colorful Helly bound, we prove that the Tverberg number $r_k$ is at most $O(r^{\lceil \log_2 r \rceil})k$. The best previous bound, by Pálvölgyi (2022), was $r^{r^{r^{\log r}}}k$. We also study the $t$-wise Tverberg number $r_{k,t}$, which is the least $\ell$ for which any $\ell$ points can be divided into $k$ parts such that the convex hulls of any $t$ parts intersect. We prove the optimal bound $r_{k,t} = O_t(kr)$, in any $S_4$ separable space. In the other direction, we construct a separable space in which $r_k = \Theta(r^2 k)$, while $r_{k,2}=\Theta(rk)$. This proves that the weak version of Eckhoff's conjecture, which suggested that $r_k=O(rk)$ in any abstract convexity space, fails even in separable spaces. In addition, this shows that the abstract analogue of Reay's conjecture (1979), suggesting that $r_{k,2}=r_k$ in Euclidean spaces, already fails in separable convexity spaces.

We present a method for partitioning the solution space of statements in extremal set theory. Compared with domain-agnostic partitioning methods like look-ahead, we perform case analysis on the strategies by which a candidate solution can be constructed. We demonstrate that our approach can decompose problems in extremal set theory more effectively than look-ahead. Combining this new partitioning strategy with an exact proof-producing MILP solver, we are able to verify larger finite cases of Chvátal's Conjecture—a long-standing open question in extremal combinatorics—compared to previous work.

We give weighted-matrix formulas for the components of the $CWR$ invariant of oriented non-split alternating links. After recalling the known trace formulas for $CWR_{2}$ and $CWR_{3}$, we give a construction uniform in $k$: attaching an independent commuting variable to each vertex of a consolidated Tait graph and extracting the squarefree part of the resulting trace isolates simple cycles from closed walks. This yields a formula for $CWR_k$ for every $k\ge 3$, a log-determinant generating polynomial for each of the two Tait graphs, and an equivalent Moebius-inversion formula over principal submatrices. Specializing the uniform formula, we obtain explicit closed weighted formulas for $CWR_{4}$ and $CWR_{5}$. We also record a bipartiteness criterion for the vanishing of all odd components and a characteristic-polynomial formula for the unweighted specialization of the first nonvanishing odd component. The graph-theoretic constructions apply to arbitrary finite simple loopless weighted graphs; the alternating-link hypothesis enters through the invariance theorem for $CWR$.

We show that, for sufficiently large $n$, every properly edge-coloured $n$-vertex complete graph contains a path with $n-1$ vertices which uses each colour at most once (that is, a rainbow path). This resolves a conjecture of Andersen from 1989 for all large $n$ and improves previous results of Alon-Pokrovskiy-Sudakov, and then Balogh-Molla, which showed that rainbow paths/cycles of length $n-O(n^{1/2}\log n)$ exist in this setting. Furthermore, with related methods, we show that, for every sufficiently large $n$, every Latin square of order $n$ contains a cycle-free transversal of order $n-2$, confirming a conjecture of Gyárfás and Sárközy from 2014 for large $n$.

We develop a framework for proving universality results in sparse random graphs. As a first application, we show that there exists an absolute constant $C>1$ such that, with high probability, for every fixed constant $\Delta$, the binomial random graph $G(n,C\ln n/n)$ contains every $n$-vertex tree with maximum degree at most $\Delta$. This answers a question of Montgomery (Advances in Mathematics, 2019). We also determine, for every $p$ satisfying $C\ln n/n\leq p=n^{-1+o(1)}$, the minimum girth $\ell$ (up to an absolute multiplicative constant) for which with high probability $G(n,p)$ contains all cycle factors of girth at least $\Omega(\ell)$. In particular, with high probability $G(n,C\ln n/n)$ contains all cycle factors of girth at least $100\ln n/\ln\ln n$, which is optimal up to a constant factor. This extends an earlier result of Ferber, Kronenberg, and Luh (Transaction of the American Mathematical Society, 2019) and significantly improves a corollary of a deep result of Kahn, Lubetzky, and Wormald (Communications on Pure and Applied Mathematics, 2017). One of the key ingredients in the proofs is establishing the optimal depth of linking systems in sparse random graphs.

We develop a common framework for random width laws, spectral populations, and geometric reconstruction. For a $d$-dimensional orthotope, we prove an exact parity law for the maximal $\pi^{-1}$-grade of every spherical width cumulant, including noncancellation and sign in all dimensions and orders. The first $d$ scalar width moments recover the unordered side vector, and $d-1$ moments are generically insufficient. Each Laplace mode generates an auxiliary width law whose upper endpoint satisfies $M_{n,a} = \lambda_n(a)^{1/2}/\pi$. At high energy the modal coordinate partitions converge to a universal Dirichlet law, while an unsmoothed measure-valued cutoff expansion retains the first geometric memory at face scale. Its simplex moment determines, up to an explicit nonzero factor and a separate off-diagonal argument, a basis-independent projector-gradient Weyl tensor that reconstructs the orthotope. Genuine edge-scale jumps obstruct a third coefficient for the total raw cutoff; exact mixed-boundary Mobius inversion isolates every coordinate stratum and restores a recursive bulk-boundary expansion with a smaller remainder. Beyond orthotopes, we prove direction-labelled identifiability for a canonical linear-quadratic class and finite recovery from direction-sensitive ridge moments under a generator bound. In dimension three, a global great-circle incidence calculus gives the exact step, fold, endpoint-fold, and corner coefficients of reduced zonotopal width densities, including an explicit non-simple corner cancellation. The results distinguish universal aggregation, recoverable geometric memory, and the remaining scalar inverse problem.

The symmetric group $S_n$ is generated by transpositions, and problems of sorting permutations using transpositions are well studied. In recent work, Adin, Alon, and Roichman studied the related problem of sorting $n$ points on a circle, and gave a formula for the maximum number of adjacent swaps required. This is equivalent to the number of adjacent transpositions required to transform any permutation into a power of the cyclic permutation $(1,2,\ldots, n)$. The focus of this work is an analogous question in the alternating group $A_n$, which is generated by $3$-cycles. That is, using 3-cycles instead of transpositions, what is the maximum number of steps required to transform an even permutation into a power of $(1,2,\ldots, n)$ in the alternating group? We determine this number exactly for even $n$ and $n \equiv 1 \pmod{4}$. For $n \equiv 3 \pmod{4}$, we show that the sorting number can take one of two possible values and give explicit constructions demonstrating that the larger value occurs infinitely often.

We define a generalized monoid of words, an asymptotic quotient of moderate nets of finite words, to regularize divergent products of arithmetic origin. Divergent sequences are encoded as moderate nets over a finite alphabet, while prefix-dependent observables are evaluated along admissible asymptotic scales. We characterize the evaluation and renormalization schemes axiomatically. Once the asymptotic scale and class of admissible regular expansions are fixed, the constant-term prescription is uniquely determined. Thus the regularized value is canonical relative to the chosen scale and evaluation functional, without absolute uniqueness. The regularizing functionals arise as expectations of logarithmic-prefix functionals under empirical distributions of sign oscillations. The alternating product of integers is regularized to $\sqrt{2/\pi}$, matching zeta regularization, while the alternating product of factorials yields $(2/\pi)^{1/4}$ and satisfies $\mathfrak{F}_{\mathrm{ren}}=\sqrt{P_{\mathrm{ren}}}$. Products governed by dyadic block signs acquire finite values through logarithmic-scale averaging in the corresponding dyadic quotient, invariant under dyadic equivalence. For the Thue–Morse sequence, zeta regularization is well defined via meromorphic continuation of its Dirichlet series. A separate convergent functional associated with its logarithmic partial sums yields $\exp(\mathcal F)\approx0.9732$. We also study numerically a substitution-generated sign sequence with exact square-root growth on dyadic blocks and fractal log-periodic structure. Its Dirichlet series shows a candidate log-periodic pole structure, separating local scale constants from a candidate global regularized value. The choice of asymptotic scale is determined by the arithmetic structure of the sequence: logarithmic scales for ordinary alternating products and dyadic scales for block-automatic sequences.

Resolving Babai's minimal Cayley graph problem, we construct finite minimal Cayley graphs with arbitrarily large chromatic number.

Suppose that $n=2m$, $k=2t$ and $n > 10 k^7$. We show that if a family $\mathcal F$ of $k$-subsets of an $n$-set has only even pairwise intersections then $|\mathcal F| \leq \binom{m}{t}$. Moreover, every extremal family has an atomic structure. This result was previously proved by Frankl and Tokushige for $n > n_{FT}(k)$, where $n_{FT}(k)$ is at least exponential. The main technique is Delsarte linear programming.

Determining the combinatorial structures that maximize the number of prescribed substructures is a central theme in extremal combinatorics. Grzesik, Král', Lovász and Volec showed that when $\ell$ is not divisible by $4$, the random tournament contains asymptotically the most directed cycles of length $\ell$ among all $n$-vertex tournaments. In the paper, we resolve the remaining cases where $\ell$ is divisible by $4$. We show that, in this regime, the so-called carousel tournament asymptotically maximizes the number of directed $\ell$-cycles among all $n$-vertex tournaments, and in particular contains strictly more such cycles than the random tournament. This confirms the conjecture of Bartley and Day.

Much work in knot theory has consisted of categorifying, and thereby strengthening, knot invariants. We take the opposite approach: decategorification, more commonly called combinatorics. We introduce a technique that relates the dual braid group generators, the Hecke images of pure braids, and factorization problems in reflection groups to knot invariants. We prove that the $(a,z{=}0)$-HOMFLYPT polynomial can be computed as a solution to such a problem. This technique was motivated by Coxeter–Catalan combinatorics. For example, we give a new proof of EL-shellability of the noncrossing partition lattice using the image of the full twist in the Hecke algebra; in a surprising sort of combinatorial reciprocity, its inverse computes the homotopy type. Similarly, noncrossing partitions naturally arise from our construction applied to positive powers of the full twist, while cluster complexes come from the same construction applied to negative powers. In crystallographic type, we exploit the conjugacy of all Coxeter elements to give the first reflection subword models for rational noncrossing Catalan objects. Our reciprocity gives two models: one generalizing noncrossing partitions, and one generalizing clusters. Applying the same method produces two (rational) noncrossing parking models.

In this paper, we build upon the analysis initiated by Gennadiy Averkov and Matthias Schymura (2022) and establish that the number of distinct columns of a $\Delta$-modular matrix $A \in \mathbb{Z}^{m \times n}$ of rank $m$ is $O(m^3 \Delta)$. This upper bound was previously known only for odd values of $\Delta$. Recall that a matrix is called $\Delta$-modular if the maximum of the absolute values of its $m \times m$ minors equals $\Delta$.

Collective decisions in agent networks emerge from repeated local interactions, as agents update their opinions (colors) based on their neighbors, potentially leading to consensus. In sparse communication graphs, repeated interactions can amplify both the initial majority preference and the random fluctuations caused by individual agents. Understanding when the initial majority determines the final preference and how quickly an agreement emerges is, therefore, a basic question in collective decision-making. We study binary majority dynamics as an idealized model of this process. At each round, the interaction graph is independently resampled from the Erdős–Rényi model $\mathbb{G}(N,p)$, with $p=b\log N/N$ and fixed $b>1$. Each agent adopts the majority opinion among its neighbors, retaining its current opinion if there is a tie. For a fixed initial configuration, let $\Delta_0$ denote the initial difference between the number of blue agents and the number of red agents. We identify three regimes for the consensus time, determined by $|\Delta_0|$. First, when $\Delta_0\sqrt p=O(1)$, the probability of blue unanimity is $$ \Phi\left(\Delta_0\sqrt{2p/\pi}\right) + o(1), $$ where $\Phi$ is the cumulative distribution function of a standard Gaussian. Moreover, consensus is reached after $(1+o(1))\log N/\log\log N$ rounds with high probability. Second, in the intermediate regime $1\ll\Delta_0 \sqrt{p}\lesssim \sqrt{N}$, we establish explicit high probability upper and lower bounds on the time to blue-unanimity. Lastly, when the initial blue advantage is above an explicit constant multiple of $N/\sqrt{\log N}$, blue unanimity is guaranteed within two rounds with high probability. Our findings provide a complete description of how the initial advantage influences winner selection and the speed of consensus in this type of majority dynamics with sparse interactions.

In the $3$-neighbor bootstrap percolation process, a vertex becomes (and remains) infected if at least three of its neighbors are infected. We say that an initial configuration of infected vertices percolates if eventually all vertices are infected. We exactly determine the size of the minimum percolating set for the $3$-neighbor bootstrap percolation process on all remaining open cases for rectangular grid graphs $P_m\square P_n$. This extends earlier work of Dukes, Noel, and Romer. Additionally, we consider the same question for the toroidal grids $C_m\square C_n$, proving upper and lower bounds which are at most one apart and determining the answer precisely in many divisibility cases.

A compact metrizable system is null if its topological sequence entropy vanishes along every sequence of times. We prove that nullness is equivalent to polynomial maximal pattern complexity for every finite open cover, while equicontinuity is equivalent to sublinear maximal pattern complexity. The first characterization is obtained from finite fat-shattering at every positive scale and polynomial empirical covering of orbit-distance classes. We also construct transitive nonminimal null systems with properties excluded in the minimal setting: one is uniformly rigid and has two fixed points, and another is two-scattering. These results settle several long-standing open problems from the literature on polynomial maximal pattern growth and on the structure of transitive nonminimal null systems.

A finite nonempty set $F\subset\mathbb{N}$ is Schreier if $\min F\ge |F|$. First, we prove a linear recurrence relation and compute initial counts for Schreier sets consisting of intervals. Two intervals of integers are separated if their union is not an interval. If $\mathcal J_{k,n}$ is the collection of Schreier sets that are the union of exactly $k$ separated intervals, then the sequence $(|\mathcal{J}_{k,n}|)_{n=1}^\infty$ satisfies the characteristic polynomial $p_k(x) = (x-1)^{2k+1}(x+1)^k$. Furthermore, we introduce the new concept of $k$-super-Schreier sets and let $\mathcal{S}_{k,n}$ denote the collection of $k$-super-Schreier sets whose maximum is $n$. We show that the sequence $(|\mathcal{S}_{k,n}|)_{n=1}^\infty$ satisfies a Fibonacci-type recurrence with a remainder term expressible as a polynomial of $n$.

Let $u(n)$ be the largest integer $d$ such that every $n$-vertex claw with at most $d$ branches occurs in every tournament on $n$ vertices, and let $c_{\mathrm{claw}}=\limsup_{n\to\infty}u(n)/n$. In 1998, Lu, Wang and Wong proved that $19/50\le c_{\mathrm{claw}}\le11/23$, and these have remained the best bounds known. We improve them to $2/5\le c_{\mathrm{claw}}\le10/21$. We also isolate two parameters $\theta$ and $\sigma$ which place the lower- and upper-bound arguments in a common framework: we show $\sigma\le\theta$ and $1/21\le\sigma\le\theta\le1/5$, our two bounds being the images of the endpoints under $\alpha\mapsto\frac12-\frac{\alpha}{2}$, and $\sigma=\theta$ would force $\lim u(n)/n$ to exist.

Beisegel et al. [SWAT 2024] introduced the concept of simultaneous $\mathcal{C}$-numbers which associate a graph class $\mathcal{C}$ with a graph parameter. Given a graph $G$, the simultaneous $\mathcal{C}$-number is the smallest number $d$ for which there is a graph $H \in \mathcal{C}$ and a function $L : V(G) \to \mathcal{P}(\{1,\dots,d\})$ such that two vertices $u$ and $v$ are adjacent in $G$ if and only if they are adjacent in $H$ and their sets $L(u)$ and $L(v)$ are not disjoint. We study the relation of these simultaneous $\mathcal{C}$-numbers to other graph parameters. In particular, we investigate which parameters fulfill the following property: Parameter $p$ is bounded on class $\mathcal{C}$ if and only if $p$ is bounded on the class of graphs of simultaneous $\mathcal{C}$-number $d$ for any fixed $d$. We show that many well-known graph parameters have this property. Examples are cliquewidth, twin-width, mim-width, tree independence number, thinness as well as boxicity. We furthermore present some parameters, including modular-width and tree-length, that do no have this property. We also study when a parameter forms an upper bound on a simultaneous $\mathcal{C}$-number. We characterize those graph classes $\mathcal{C}$ for which the parameters treewidth, pathwidth, bandwidth, and treedepth upper bound the simultaneous $\mathcal{C}$-number. Furthermore, we present sufficient conditions on a class $\mathcal{C}$, such that $\mathcal{P}$-modular cardinality upper bounds the simultaneous $\mathcal{C}$-number, where $\mathcal{P}$ is replaced by the complete graphs, the edgeless graphs, cographs, or the class $\mathcal{C}$ itself. On the contrary, we show that modular width never forms an upper bound on a non-trivial simultaneous $\mathcal{C}$-number. Finally, we present some general algorithmic results on the clique problem and computation of simultaneous $\mathcal{C}$-numbers.

Given a graph $G=(V,E)$, $f : V \rightarrow \{0, 1, 2\}$ is a \emph{Roman $\{2\}$-dominating function} of $G$ if for every vertex $v\in V$ with $f(v) =0$, either there exists a vertex $u$ adjacent to $v$ with $f(u) = 2$, or two distinct vertices $x,\; y$ both adjacent to $v$ with $f(x)=f(y)=1$ (Chellali et al. 2016). Every graph $G$ satisfies $\gamma_{\{R2\}}(G) \leq 2\gamma(G)$, where $\gamma_{\{R2\}}(G)$ denotes the minimum weight of a $\{2\}$-Roman dominating function of $G$ and $\gamma(G)$ is the domination number of $G$. \emph{$\{2\}$-Roman graphs} are those for which the equality is reached (Klostermeyer et al. 2019). A characterization of $\{2\}$-Roman trees was given by Henning et al. in 2017. In 2025, Ferrari et al. characterized the $\{2\}$-Roman property by the existence of a minimum $\{2\}$-Roman dominating function of $G$ that assumes only $0, 2$-values. Afterwards in 2025, Bešter Štorgel et al. introduced the problem of recognizing $\{2\}$-Roman graphs, proved polinomiality for middle graphs, and characterized \hbox{$\{2\}$-Roman} split graphs that can be decomposed with respect to the split join operation into two smaller split graphs. Recognition complexity is still open for general graphs. In this paper we study the \hbox{$\{2\}$-Roman} property on graphs that can be decomposed into two smaller graphs with respect to the join and union operations, allowing to completely characterize the $\{2\}$-Roman property. The 4-path is the non trivial connected non $\{2\}$-Roman graph with the fewest number of vertices and edges. We classify the $\{2\}$-Roman property within specific families of non decomposable graphs with a limited number of 4-paths which are present in the decomposition of partner limited graphs; these are well-labelled spiders, the graphs in ZOO and some special split graphs.