Papers

How much does an algorithm's running-time distribution under independent randomness reveal about its behavior when independence is no longer guaranteed? We study sources satisfying $\nu[w]\le DP[w]^s$ for every finite prefix $w$, where $P$ is an independent reference law, $0<s\le1$, and $D\ge1$. The constraint controls complete-prefix probabilities while allowing individual choices to be predictable, even fully determined by the past. For retry tasks, all deterministic history-dependent selectors have the same independent-source running-time law. Yet two orders have worst-case failure probabilities $1$ and $\exp[-\Theta(n)]$ at the same linear deadline under the same source constraint. We identify a static priority rule that is optimal at every deadline and every $D$. For the standard local walk on a $k$-CNF with at least $r$ true literals per clause under some assignment, $k/2<r<k$, we determine the sharp source threshold $s_*$. At and above it, the expected flip count is $O_{k,r}(\min\{L^3,L/(s-s_*)\})$, where $L=h+\log D+1$, $h$ is the initial Hamming distance to that assignment, and $L/0=\infty$. The bound allows arbitrary clause overlap and history-dependent clause selection. Matching instances admit one source forcing this delay with probability one for every selector. At criticality and fixed $D$, the delay is cubic despite a linear independent-source expectation. Variable-depth prefix covers, together with classical tree max-flow/min-cut, yield an exact criterion for restoring exponential tails by restarting on the same tape. We synthesize updates and restarts for explicit finite-state processes. Under a sufficient prefix guarantee, we also obtain noisy predecessor search with error at most $\eta$ and expected query count polynomial in the correct leaf's depth and $\log(D/\eta)$, without knowing the depth or tree height.

For the circulant graph $C_n(1,2)$ with $n\ge10$ even, the $\F_2$ system requiring every quadrilateral to be unbalanced is consistent and its solutions form exactly four switching classes. We show that the class containing the signing which is $+1$ on step-$1$ edges and $(-1)^i$ on step-$2$ edges has spectrum $\{\pm2\sqrt{\cos^2\theta_k+\cos^2 2\theta_k}\}$ and spectral radius exactly $2\sqrt2$, well below the Kesten bound $2\sqrt3$; that the quadrilateral system is equivalent to alternating triangle fluxes, so that the four classes are coordinatized by $(\tau_0,\alpha)$ and the spectral radius depends only on the Hamilton-cycle holonomy $\alpha$; and that the two twisted classes attain $\rho_-(n)=2\sqrt{\cos^2(\pi/n)+\cos^2(2\pi/n)}<2\sqrt2$. Exhaustive enumeration of all $2^{n+1}$ switching classes for $n\in\{8,10,12,14,16,18\}$ shows that $\rho_-(n)$ is the global minimum in every case, and we conjecture this for all even $n$; the lower bound is a flux-minimization statement in the sense of Lieb's flux-phase theorem. For odd $n$ the quadrilateral system is inconsistent.

The strong chromatic index $\chi'_s(G)$ is the smallest number of colours needed to colour the edges of a graph $G$ so that any two edges at distance at most $2$ receive different colours. Using the local flag algebra framework introduced in a companion paper, we prove $\chi'_s(G) \leq 1.73\,\Delta(G)^2$ for every graph $G$ of maximum degree $\Delta(G)$, $\chi'_s(G) \leq 1.6255\,\Delta(G)^2$ for every bipartite $G$, and $\chi'_s(G) \leq 1.6633\,\Delta_A(G)\,\Delta_B(G)$ for every bipartite $G$ of side maximum degrees $\Delta_A(G), \Delta_B(G)$ with rational $\Delta_B(G)/\Delta_A(G) \in (0, 1]$, provided $\Delta(G)$, $\Delta_A(G)$, $\Delta_B(G)$ are sufficiently large. These three bounds make progress towards three established conjectures: those of Erdős-Nešetřil (1985) for general graphs, Faudree-Gyárfás-Schelp-Tuza (1989) for bipartite graphs, and Brualdi-Quinn Massey (1993) in the asymmetric bipartite setting. Additionally, for the random bipartite graph $G \sim G(n_A, n_B, p)$ at constant $p \in (0,1)$ and bounded aspect ratio $\max(n_A, n_B) = O(\min(n_A, n_B))$, we prove the Brualdi-Quinn Massey bound $\chi'_s(G) \leq \Delta_A(G)\,\Delta_B(G)$ asymptotically almost surely.

We show that the licci property of an ideal cannot, in general, be determined from its Betti table by exhibiting two $\mathfrak{m}$-primary monomial ideals containing the cubes the variables that have identical Betti tables, yet only one is licci. In contrast, we show that for monomial ideals containing the square of each variable, the licci property is completely determined by the Betti table; indeed, it is determined by its first two columns.

We study the maximum size of a set system that contains no $k$-Venn diagram, denoted by $VD_k$, as a trace. For every fixed $k\ge 3$, we prove $\text{ex}_{tr}(n,VD_k)=O_k(n^{2^k-2k+1})$, improving the direct Sauer-Shelah bound $O_k(n^{2^k-1})$. In particular, for $k=4$ the exponent decreases from $15$ to $9$. The proof starts from the theorem of Keevash, Leader, Long and Wagner for $VD_3$ and uses induction on $k$ in which two new Venn regions are forced for free at each added edge. We also record lower-bound constructions for Venn diagrams in fixed uniformity, explicit bounds for the $4$-uniform $3$-Venn problem, and a fixed uniformity trace result for the loose triangle.

We develop an affine $\mathbb F_2$ framework for structured signings of regular graphs. A family-averaging identity converts even spectral moments into parity-weighted closed-walk counts supported on the span of prescribed short even cycles, while a kernel-averaged Ihara identity gives the corresponding decomposition at the non-backtracking level. We give a finite-scale bounded-rank counting estimate and a conditioning corollary showing that, on bicycle-free graph sequences, any parity family of uniformly bounded codimension contains near-Ramanujan signings whenever the corresponding random-signing theorem applies. The latter is a transfer statement rather than a new concentration theorem. Finally, on $C_n(1,2)$ for even $n\ge10$, the quadrilateral-unbalanced family has exactly four switching classes and its twisted classes attain $\rho_-(n)=2\sqrt{\cos^2(\pi/n)+\cos^2(2\pi/n)}$; a period-$8$ signing has spectral radius $r_*=2.793604493334841\ldots$ for every positive multiple of $8$. Thus for $n=8m\ge32$ the constrained minimum is strictly larger than a value attained by an unrestricted signing, while equality of $r_*$ with the unrestricted minimum remains conjectural.

A coloring of a finite $k$-out directed graph $G$ is viewed as a deterministic complete automaton with state set $V(G)$. The graph $G$ is called totally synchronizing if every coloring is synchronizing. We prove that total synchronization imposes strong restrictions on symmetry: if $G$ is strongly connected and totally synchronizing, then $Aut(G)$ contains no semiregular element; in particular, if $|Aut(G)|$ is divisible by a prime $p>k$, then $G$ is not totally synchronizing. We then give general constructions of strongly connected $k$-out graphs with prescribed quotients and prescribed automorphism group that are not totally synchronizing. On the quotient side, we relate graph congruences to strong lumpability of the uniform random walk on $G$ and introduce totally simple graphs, characterized by the absence of nontrivial congruences. In this setting we obtain a Perron–Frobenius sufficient condition for total synchronization: a strongly connected non-lumpable graph whose integer Perron–Frobenius eigenvector admits at most one nontrivial equipartition is totally synchronizing. Finally, we show that deciding whether a primitive $k$-out graph admits a non-synchronizing coloring is NP-complete, resolving an open problem of Gusev–Szykuła, and prove NP-completeness of deciding whether a graph admits a nontrivial Eulerian lumping.

We give an affirmative answer to Owings's sumset question: for any $2$-coloring of natural numbers, there is an infinite $B\subseteq\mathbb{N}$ such that $B+B$ is monochromatic. More generally, for every $m,\ell\in\mathbb{N}$ and every $2$-coloring of $\mathbb{N}$, there is an infinite $B\subseteq\mathbb{N}$ such that $$ (m+\ell)B\cup\{mx+\ell y:x,y\in B,\ x<y\} $$ is monochromatic.

Let $q$ be an odd prime power and $\mathbb{F}_q$ be the finite field of order $q$. We prove an extraction theorem for the Erdős-Falconer distance conjecture in even dimensions, showing that the conjecture for all even dimensions reduces to the planar case. As consequences, we obtain improved thresholds on the pinned distance problem and the distribution of triangles, achieving new records of $\frac{d}{2}+\frac{1}{4}$ over prime fields and $\frac{d+1}{2}+\frac{1}{10}$ over arbitrary finite fields, respectively.

A graph is matchable if it admits a perfect matching. Recently, Goedgebeur et al. asked whether there exists a constant $c<12$ such that infinitely many matchable planar $3$-connected graphs, each with exactly $c$ perfect matchings. We answer this question by proving that every matchable planar $3$-connected graph on at least 40 vertices has at least 12 perfect matchings, and this lower bound is sharp.

Signed enumerations of l-regular partitions by the parity of the number of parts are known to correspond to partitions with congruence conditions. Inspired by the recent combinatorial approaches of Ballantine-Merca and Liu for such identities, we provide combinatorial proofs of three identities for l-regular partitions and their variants. Two of these were originally established analytically by Hickerson and Robbins, respectively.

Brouwer conjectured that the sum of the $k$ largest Laplacian eigenvalues of an $n$-vertex graph is less than or equal to the number of its edges plus $\binom{k+1}{2}$ for every $k\in \{1,2,\dots,n\}$, which has been confirmed by Kothari and Tudose (2026) recently. In this note, we characterize the equality case in this inequality. Our main result is that for every $n$-vertex graph $G=(V,E)$ and for every $k\in \{1,2,\dots,n-1\}$, the equality $\sum_{i=1}^k\mu_i(G)=|E(G)|+\binom{k+1}{2}$ holds if and only if $G$ is a threshold graph with clique number $k+1$, where $\mu_1(G)\geq \mu_2(G)\geq \cdots\geq \mu_{n}(G)$ are the Laplacian eigenvalues of $G$. This, together with the confirmed Brouwer's conjecture, would yield a complete solution to the full Brouwer's conjecture posed by Li and Guo (2022). Our proof relies on the projection method of Kothari and Tudose and shows directly that the equality case can occur only for threshold graphs.

Let $n\ge1$ and $C\subseteq\mathbb{R}^n$ be a closed convex cone with conic intrinsic volumes $v_0(C),\ldots,v_n(C)$. We prove the long-standing log-concavity conjecture for this sequence, in the stronger form \[ v_k(C)^2\ge \rho_k\rho_{n-k}v_{k-1}(C)v_{k+1}(C), \qquad 1\le k\le n-1, \] where, for $l\ge1$, $\rho_l=\frac{l+1}{l}\frac{\omega_{l-1}\omega_{l+1}}{\omega_l^2}>1$ and $\omega_j$ is the volume of the Euclidean unit ball in $\mathbb{R}^j$. The proof applies the Alexandrov–Fenchel inequality to the Takemura–Kuriki identity \[ V(A[k],D[n-k])=\frac{\omega_k\omega_{n-k}}{\binom nk}v_k(C),\qquad A=C\cap B^n,\quad D=C^\circ\cap B^n, \] where $C^\circ$ is the polar cone, $B^n$ is the Euclidean unit ball, and repeated arguments are indicated by brackets. A Master Steiner argument gives the identity directly for arbitrary closed convex cones, including degenerate ones. We also give a circular-cone counterexample to the standard ultra-log-concavity normalizations.

For every fixed integer $t \geq 2$, we give an upper bound on the multicolor vector space Ramsey number $R_2(t; k)$ that is a tower function of height independent of $k$. For $t \geq 3$, this is the first bound of its form, significantly improving upon the earlier bounds that are towers of height linear in $k$. We achieve this by reducing the problem to a classical hypergraph Ramsey problem via binary simplex codes. In particular, we prove that $$R_2(t; k) \leq \left\lceil \log R(K_s^{(r)}; k + 1) \right\rceil \leq \mathrm{twr}_{r-1}(c k\log k),$$ for $r = 2^{t - 1}$ and $s = 2^t - 1$, where $R(K_{s}^{(r)}; k + 1)$ is the classical $(k + 1)$-color Ramsey number for the complete $r$-uniform hypergraph on $s$ vertices. This improvement also translates into an improved lower bound on the chromatic number of the binary projective space with respect to $(t - 1)$-flats. For $t = 2$, it recovers the connection with multicolor Ramsey numbers for triangles.

Let $X$ be an alphabet, let $t\geq 0$ and $n\geq t+1$, and let $((a_i,b_i))_{i=1}^{m}$ be an ordered family of word pairs in $X^n$ satisfying $dist(a_i,b_i)\geq t+1$ for every $i$ and $dist(a_i,b_j)\leq t$ whenever $i<j$. We prove the sharp bound $m\leq 2^{t+1}$, thereby resolving a problem posed by Alon, Jin, and Sudakov. Our proof uses a linear-algebraic method based on a characteristic-two algebra, which may be of independent interest.

Let $N$ be an arbitrary positive integer and let $\lambda=(\lambda_1, \lambda_2, \ldots, \lambda_l)$ be a partition of $N$ of length $l$, i.e., $\sum_{i=1}^l\lambda_i= N$ with parts $\lambda_1\ge \lambda_2\ldots \lambda_l\ge 1$. Define $T(\lambda)$ as the partition of $N$ with parts $l,\lambda_1-1\lambda_2-1,\ldots \lambda_l-1$,ignoring any zeros that might occur. Starting with a partition $\lambda$ of $N$, we describe Bulgarian solitaire by repeatedly applying the shift operation $T$ to obtain the sequence of partitions $$ \lambda, T(\lambda), T^2(\lambda),\ldots . $$ We say a partition $\mu$ of $N$ is $T$-cyclic if $T(\mu) = \mu$ for some $i\ge 1$. In 1982 Brandt [9] characterized all $T$-cyclic partitions for Bulgarian solitaire. Bulgarian solitaire is a dynamical system on integer partition of a positive integer $N$ which converges to a unique fixed point if $N=1+2+\cdots +k$ is a triangular number. In this paper we present a short survey of the game Bulgarian solitaire and several variations of this game.

Let $k$ be a positive integer. Jackson and Thomassen conjectured in 1989 that there exists an integer function $f(k)$ such that every $f(k)$-strong digraph admits a spanning $k$-strong oriented subdigraph. They even conjectured that one can take $f(k)=2k$ [Ann. N. Y. Acad. Sci. 555 (1989) 402-412]. Already the existence of $f(2)$ is open for general digraphs. Thomassen proved that $f(2)=4$ for symmetric digraphs. For general $k$, the existence of $f(k)$ was only known for locally semicomplete digraphs and quasi-transitive digraphs. Guo proved that every ${(3k-2)}$-strong locally semicomplete digraph contains a spanning $k$-strong local tournament [Discrete Appl. Math. 79 (1997) 119–125]. One can deduce from Guo's result that we have $f(k)\leq 3k-2$ for quasi-transitive digraphs. In this paper, we prove the existence of $f(k)$ for two subclasses of the semicomplete multipartite digraphs, namely extended semicomplete digraphs and semicomplete split digraphs. We prove that every $(4k+1)$-strong extended semicomplete digraph contains a spanning $k$-strong oriented subdigraph and every $5k$-strong semicomplete split digraph contains a spanning $k$-strong oriented subdigraph. The first result implies that for the large class of digraphs which can be obtained from some semicomplete digraph $S$ on at least 3 vertices by substituting arbitrary digraphs for each vertex of $S$ we also have $f(k)\leq 4k+1$.

We give an introduction to the grammatical calculus, which originated from the umbral calculus of Rota. Context-free grammars arise in computer science. Differential operators can be viewed as the production rules of context-free grammars. By the properties of differential operators, we may perform the grammatical calculus on a rigorous basis, for the purposes of deriving combinatorial identities and computing generating functions. A grammatical labeling serves as a bridge between a combinatorial structure and the grammar. A grammar may be instrumental in constructing a bijection between two combinatorial structures sharing the same grammar. Such a bijection is called a grammar assisted bijection. Many combinatorial structures admit recursive constructions that are context-free in some sense, such as those corresponding to the Eulerian polynomials, Bell polynomials, the Ramanujan polynomials and the Narayana polynomials.

Results by Jackson and Frank imply that every 2k-arc-strong digraph D contains a spanning k-arc-strong oriented subdigraph. This is best possible, even for very dense digraphs. A digraph is semicomplete if at least one of the arcs xy,yx is present for every pair of distinct vertices x,y. A tournament has exactly one of xy,yx for every such pair. Clearly every semicomplete digraph D contains a spanning tournament T which is obtained by deleting one arc from every 2-cycle of D. We prove that every (2k-1)-arc-strong semicomplete digraph on at least 2k+1 vertices contains a spanning k-arc-strong tournament. Both bounds 2k-1 and 2k+1 are best possible. The proof uses Frank's general orientation theorem for graphs as well as counting arguments based on the semicomplete structure.

A counting problem arising naturally from game theory leads to the problem of estimating the coefficients $t_{ij}$ of a particular bivariate rational function. Restricting to the diagonal sequences $t_{j+k,k}$ (with $k$ fixed) allows us to study these sequences using elementary one-variable methods.

Let $A:\mathbb{F}_2^n\to\mathbb{F}_2^m$ be a binary linear map with fixed coordinate bases, let $C_A=\ker A$, and let $\lambda_A(y)$ be the minimum Hamming weight of a preimage of the syndrome $y$. We define $\operatorname{Shat}_{q,s}(A)$ as the least common check support of a $q$-dimensional syndrome subspace whose every nonzero element has coset-leader weight at least $s$. It therefore distinguishes release of $q$ independent syndromes from release of a subspace with no easy linear combination. Deleting check coordinates $F$ releases $\ker A_{\bar{F}}/\ker A$, canonically isomorphic to $(\operatorname{im} A)[F]$. Finiteness implies $R_q(C_A)\ge \mathsf{N}_2(q,s)$, where $\mathsf{N}_2(q,s)$ is the shortest length of a binary code of dimension $q$ and distance at least $s$; profile-Griesmer bounds independently control common check support. The hierarchy is coordinate-relabeling invariant but can change under a change of check basis. For the pair-repetition code $C_n=\{(x,x):x\in\mathbb{F}_2^n\}$, the standard realization $H_0=[I_n\ I_n]$ has $\operatorname{Shat}_{q,s}(H_0)=\mathsf{N}_2(q,s)$ whenever feasible. For every $q\ge 1$ and $s\ge 2$, with $n=\mathsf{N}_2(q,s)$, a row-equivalent realization of the same code has value $q$. For a simplicial coboundary map $A=\delta_k$, check erasure is top-face erasure and the released quotient is emergent cohomology. At $s=1$ the hierarchy reduces to generalized Hamming weights and is Tutte-determined; for $s\ge 2$, even identical labeled cut codes can have different values.

A square matrix is called Hessenberg whenever each entry below the subdiagonal is zero and each entry on the subdiagonal is nonzero. A Hessenberg pair is an ordered pair of diagonalizable linear maps on a nonzero finite-dimensional vector space, that each act on an eigenbasis of the other one in a Hessenberg fashion. A Hessenberg system $\Phi$ an `oriented' version of a Hessenberg pair. It is known that $\Phi$ is determined up to isomorphism by its parameter array; this consists of the eigenvalue sequence of $\Phi$, the dual eigenvalue sequence of $\Phi$, and a sequence of nonzero scalars $\{\phi_i\}_{i=1}^d$ called the split sequence of $\Phi$. We are interested in some types of Hessenberg matrices, said to be circular, quasi-circular, tridiagonal, and irreducible tridiagonal. We are interested in the families of Hessenberg systems for which the associated Hessenberg matrices have one of the above types. A Hessenberg system of irreducible tridiagonal type is often called a Leonard system. In this case the associated Hessenberg pair satisfies two relations, called the tridiagonal relations. We are interested in the family of Hessenberg systems for which the associated Hessenberg pair satisfies the tridiagonal relations. We are also interested in the family of Hessenberg systems for which the eigenvalue sequence and dual eigenvalue sequence satisfy a linear three-term recurrence. In the present paper we have two main goals. First, we show how the above families of Hessenberg systems are related to each other. Second, we describe each family in terms of the parameter array.

There is significant interest in the study of calculus on graphs, especially regarding the use of gradient-based methods for applications in data driven problems such as classification, clustering and regularisation for inverse problems. Geometric graphs, whose vertices are take from from a Euclidean domain and whose edge structure is determined by the distance between the nodes in the domain, have been central in theoretical studies. Typical approaches for analysis, such as studying consistency and the existence of continuum limits, rely on $\Gamma$-convergence. This technique has some limitations, as it requires the typical length scale which determines the connectivity structure of the graph to be much larger than the scales frequently used for applications. Moreover, it may fail to provide quantitative results. This paper provides necessary and sufficient conditions on the asymptotic behaviour of this length scale for the existence of a uniform collection of Sobolev inequalities on a sequence of geometric graphs. Furthermore, these inequalities hold when the length scales are much smaller than what is typically assumed for $\Gamma$-convergence results and within the range of what is used for data-driven problems. The Sobolev inequalities provide a quantitative estimate on the $L^q$-regularisation effect of discrete gradients.

Spread codes are a well-known family of constant-dimension subspace-metric codes. For constant dimension $k$ and ambient space dimension $n$ being a multiple of $k$, these codes have minimum distance $2k$ and a rich geometric structure. In this paper, we study the decoding capabilities of the Nearest Neighbor Decoder for Desarguesian spread codes, establishing that unique decoding is still achievable beyond half the minimum distance. Motivated by this, we develop a new decoding algorithm to uniquely decode Desarguesian spread codes in the presence of both insertions and deletions, which increase and decrease, respectively, the dimension of the transmitted codeword. Even when the sum of the dimensions of insertions and deletions exceeds half the minimum distance, provided that deletions are of dimension at most $k-2$, the algorithm succeeds with a small decoding failure. We also propose two refinements to this algorithm that, empirically, can handle nearly as many insertions as the Nearest Neighbor Decoder.

The neighbourhood complexity $nc(G,k)$ of a graph $G$ is a quantity measuring, for a graph $G$ and an integer $k$, the maximum possible number (over all vertex subsets $S$ of size $k$) $|\{N[v]\cap S, v\in V(G)\}|$ of $S$-neighbourhoods in $G$. This notion is important in structural graph theory and algorithm design (especially in parameterized complexity, in particular model checking and kernelization). While generally $nc(G,k)\leq 2^k$ and this bound can be achieved, it is known that sparse graphs and structured dense graphs have linear neighbourhood complexity, that is, $nc(G,k)\in O(k)$ for any such graph $G$. However, for many graph classes, the best possible constants are not known. We focus on graphs of bounded treewidth and pathwidth, showing that (when $k\geq w+1$) (i) if $G$ has treewidth $w\geq 2$, then $nc(G,k)\leq (k-w+1)2^{w}+w$, and (ii) if $G$ has pathwidth $w\geq 2$, then $nc(G,k)\leq (k-w+2)2^{w-1}+2k-w-2$. Moreover, we provide constructions that reach these bounds, whenever $w\geq 2$ and $k\geq 2w+1$ ($k\geq 2w-1$ for pathwidth). Interestingly, in contrast, we also have the tight bound $nc(G,k)\leq \frac{7}{3}k$, for graphs $G$ with pathwidth 1 or treewidth 1.

We study variants of graph colouring with parity constraints. More specifically, we consider $q$-colourings $c\colon V(G)\rightarrow \{1,\dots,q\}$ of a graph $G$ where, for every vertex $v\in V(G)$, the number of neighbours $w$ of $v$ with $c(w)=c(v)$ is restricted to be odd, even, positive, zero or a combination thereof. For every colour $i\neq c(v)$ the number of neighbours $w$ of $v$ with $c(w)=i$ is restricted by a constraint of similar type. Many known colouring problems such as proper colouring, defective colouring, exact defective colouring, odd colouring, and strong odd colouring can be described within this framework of constraining graph colourings, and therefore considering variants constitutes a natural generalisation of known colouring problems. We provide a comprehensive study of the computational complexity of different combinations of constraints involving parity.

For a graph $H$ denote by $\operatorname{emb}\left(H, m\right)$ the maximal number of labeled embeddings of $H$ in a graph of size $m$. Erdős posed the question of finding $\operatorname{emb}\left(H, m\right)$ for different values of $H$ and $m$. Following related asymptotic and stability results, we determine the value of $\operatorname{emb}\left(H, {\binom{n}{2}}\right)$ for every graph $H$ with fractional independence number $v_H/2$ and all sufficiently large $n$. We also show that for those $H$ (except for matchings) and $n$ the only graph with a maximal number of embeddings is $K_n$. This fully characterizes the graphs for which $K_n$ achieves the maximal number of embeddings.

A hypergraph is linear if every pair of vertices is contained in at most one hyperedge. We study linear Turán numbers of acyclic $r$-uniform hypergraphs, extending earlier work of Gyárfás, Ruszinkó, and Sárközy from uniformity $3$ to general $r$, with emphasis on hypertrees with four hyperedges. For the linear path $P_4^r$, we prove $\operatorname{ex}^{\mathrm{lin}}_r(n,P_4^r)\le (r+1)n/r$, with equality precisely for disjoint unions of Steiner systems $S(2,r,r^2)$, whenever such systems exist. We also give counterexamples to a structural claim used in a previously proposed proof for $r=4$. The same bound and equality characterization hold for the broom $B_4^r$. For the crown $E_4^r$, writing $B=\{v:d(v)\le r\}$ and $C=\{v:r+1\le d(v)\le2r-1\}$, we prove $|E(H)|\le r|B|/(r-1)+(2r-1)|C|/r$, and hence $\operatorname{ex}^{\mathrm{lin}}_r(n,E_4^r)\le(2r-1)n/r$. We also give a lower-bound construction and formulate a sharper conjecture. Finally, for the linear star $S_k^r$, we prove $\operatorname{ex}^{\mathrm{lin}}_r(n,S_k^r)\le n(k-1)/r$, with equality precisely for $(k-1)$-regular linear $r$-uniform hypergraphs, whenever such hypergraphs exist. Under suitable divisibility and existence assumptions, we also construct $T_k^r$-free examples with $n(k-1)/r$ edges for every linear $r$-uniform hypertree $T_k^r$ with $k$ hyperedges.

We introduce ideal Gårding polynomials, a convexity-enhanced subclass of Gårding polynomials whose Gårding components are recursively convex under partial differentiation. This class strictly contains real stable polynomials and, after translation and homogenization, lies in the Lorentzian class. Our main result is that ideal Gårding polynomials still admit a robust structure theory despite this additional convexity: they are preserved under polarization, satisfy natural closure properties, and support a linear preserver theory. A key contribution of this paper is a universal model for univariate Gårding polynomials, described by monotone root sequences and equivalently by volume polynomials of Pitman–Stanley polytopes. We establish quotient concavity, and Newton–Maclaurin type inequalities, which leads to the polarization theorem, and suggests further connections with convex geometry and Lorentzian polynomials.

Given a graph $G$, its chromatic polynomial $P (G, k)$ counts proper $k$-colorings, while the corresponding list color function $P_{\ell} (G, k)$ counts the minimum number of proper colorings across all assignments of $k$ colors to each vertex. While it is clear that $P_{\ell} (G, k) \leq P (G, k)$, Donner showed in 1992 that $P_{\ell} (G, k) = P (G, k)$ whenever $k$ is sufficiently large. In 1985, Hanlon defined and studied the chromatic polynomial for an unlabeled graph. A list version of Hanlon's notion was introduced in 2024 by Kaul and Mudrock, who further raised the question of whether the analog of Donner's result holds in the unlabeled case. While they proved this for all connected point-determining graphs, even the case of the edgeless graph on $n$ vertices remained open and was posed as a conjecture. We prove this conjecture and show that it implies that, more generally, a disconnected graph satisfies the unlabeled analog of Donner's result if all of its connected components do.