Papers

In this paper we study cycles in multiset permutations and parking functions. As combinatorial objects, multiset permutations are essential building blocks for mappings and permutations, while parking functions lie between mappings and permutations. We take both algebraic and analytic views in our investigation and present exact as well as asymptotic results. We point to a surprising correspondence between two statistics on multiset permutations, terminal closers and cyclic points, shedding light on the combinatorial structure.

Median decompositions were introduced by Stavropoulos in 2015 as a generalisation of tree decompositions. In this paper, we further develop and exposit this theory as a tool in structural graph theory to study systems of vertex separations. Generalising the well-known fact that nested systems of vertex separations produce tree decompositions of a graph over the structure tree, we describe how a (not necessarily nested) system of separations produces a median decomposition. The median graph in this decomposition is the `dual median graph' constructed by Sageev. If the system of cuts is nested then this median decomposition recovers precisely the aforementioned tree decomposition. We prove a theorem asserting that this decomposition is `uniquely minimal', and describe how Sageev–Roller duality manifests in median decompositions. As an application of our structural approach, we extend a theorem of Stavropoulos from finite graphs to all graphs, which states that the median-width a graph is equal to its clique number. We also describe the link between (canonical) median decompositions and (equivariant) coarse embeddings/quasi-isometries into median graphs. A corollary of these results is a characterisation of when a finitely generated group acts metrically-properly/geometrically on a median graph, in terms of canonical median decompositions of its Cayley graphs.

Recently, Ehret and Gilliers introduced the notion of a (trivially) restricted post-Lie algebra, recovering the concepts of a restricted Lie algebra and a restricted pre-Lie algebra. In this paper, we specifically introduce restricted Rota-Baxter Lie algebras of arbitrary weight with an intrinsic graph subalgebra characterization. We show that, via the splitting property, they give rise to restricted post-Lie algebras, and furthermore possess a novel replication property. We then present two natural constructions of such restricted Rota-Baxter structures in prime characteristic: one arising from Rota-Baxter associative algebras of arbitrary weight, and the other from Rota-Baxter Lie algebras of weight $1$. The Rota-Baxter $p$-envelopes of a Rota-Baxter Lie algebra are also examined.

We use a family of Rogers–Ramanujan-type combinatorial identities of Dousse–Konan involving coloured partitions to prove classical freeness of the simple vertex operator algebras based on $\widehat{\mathfrak{sl}}_n$ at level $1$. These identities are used to produce Gröbner bases for the relevant arc algebras.

For graphs $F$ and $H$, let $\ex(n,F,H)$ denote the maximum number of copies of $F$ in an $n$-vertex $H$-free graph. Janzer, Longbrake and Yepremyan recently proved that, for fixed $3<a\le b$ and sufficiently large $t$, \[ \ex(n,K_{a,b},K_{3,t})=\Theta(n^3). \] We make their threshold explicit, showing that this conclusion holds for all $t\ge \tau(b):=2\max\{3,\lceil b/2\rceil\}+1.$ In particular, for every even $b\ge 6$, this matches the necessary threshold $t=b+1$. The main new ingredient is an explicit finite-field point set whose plane sections are controlled directly, rather than through a general bounded-complexity algebraic lemma. This direct line-and-conic section analysis gives the required \(K_{3,t}\)-freeness while preserving many coplanar \(b\)-element subsets.

Terwilliger algebras are subalgebras of a matrix algebra constructed from an association scheme. Rie Tanaka defined what it means for a Terwilliger algebra to be almost commutative and gave five equivalent conditions in the case where the association scheme is commutative. A sixth condition for a Terwilliger algebra coming from a commutative Schur ring to be almost commutative has since been discovered. In this paper we first provide a classification of orbit Schur rings that produce an almost commutative Terwilliger algebra for a finite cyclic group. In particular, we show that the subgroup of automorphisms used to form the orbit Schur ring is either trivial, or the whole automorphism group when the cyclic group has prime power order. If the cyclic group has order $2^n$, these are the only options. If the cyclic group has order $p^n$, for an odd prime $p$, then the automorphism subgroup of order $p^{n-1}$ also works. If the group has a non-prime power order then the only orbit Schur ring that produces an almost commutative Terwilliger algebra comes from the trivial subgroup of the automorphism group. We then give a condition for when a wedge product of Schur rings produces an almost commutative Terwilliger algebra. This allows us to determine exactly when a Schur ring over a cyclic group produces an almost commutative Terwilliger algebra.

This ArXiv preprint of my doctoral dissertation, which, at this stage, has not yet been accepted by the doctoral thesis committee, is intended both to lay the groundwork for a series of papers, and to confirm the existence of a first proposed solution to the "Dual Amplituhedron" problem posed in 2014 by Princeton physicists N. Arkani-Hamed and J. Trnka, a mathematical object which encapsulate the calculation of scattering amplitudes in high-energy particle colliders. The first part of this thesis deals with a rewriting of the positive real Grassmannian and performing the singular gluing of its positroid varieties in a new way via Spectral Algebraic Geometry of J. Lurie on "structured" spaces and a categorification of his "Tannaka Duality for Quasi-coherent Stacks", finding in this formal moduli problem, a compact yet holistic formulation via perverse intersection complexes of P. Deligne. This algebraico-geometric perspective paired with a synthetic differential-geometric perspective, namely the Differential Cohesion of B. Lawvere and U. Schreiber, subsumes infinitesimal thickenings, crystalline cohomology of De Rham stacks, the "Modalities of Structured Geometries" and the unification of their cohomologies of the underlying concrete topological etale algebraic space. The second part uses this rewriting of positive Schubert geometry and "The Cohomology of Brauer-Grothendieck Spaces" of B. Toën and B. Antieau, to show that, instead of the Grassmannian spectral Deligne-Mumford stack which is autodual in the infinity-category of prestable infinity-categories of modules on E\infty-ring spectra, the Amplituhedron, categorified in a functor between infinity topoï, possesses a concrete non-trivial dual, and has a De Rham volume, facts of interest for the expected Duality between the Standard Model of particles and String Theory. This new construction yields the Dual Amplituhedron.

Daisy cubes are finite partial cubes that admit an isometric hypercube embedding whose labels form a Boolean down-set. Call a vertex a root if it can receive the all-zero label in such an embedding. Using the peripheral $\Theta$-class characterization implicit in earlier work of Taranenko and of Xie–Xu, and Vesel's description of possible zero vertices, we prove the following intrinsic refinement. If exactly $b$ classes are peripheral on both sides, then $G\cong G_0\square Q_b$, where $G_0$ has a unique root and the roots of $G$ induce the displayed convex $b$-cube. Our main results concern the daisy grids $B_{r,s}=P_3^{\square r}\square Q_s$. We classify every nonempty graph $B_{r,s}-\{x,y\}$ that is a partial cube, a daisy cube, or a minimal forbidden partial-cube minor for daisy cubes. The ambient-isometric cases admit a uniform coordinate description. A local four-cycle argument reduces every non-isometric noncorner partial-cube deletion to $r+s\leq3$, and an exact orbit analysis leaves precisely eleven sporadic orbits. None is daisy or pc-minor-minimal. Consequently, a deletion is pc-minor-minimal non-daisy exactly when the deleted vertices are opposite corners with $s\geq1$ and $2r+s\geq3$, or when a boundary $P_3$-edge is deleted from $B_{1,1}$. This recovers the known hypercube and one-$P_3$ examples and produces a new infinite family with at least two $P_3$-factors. A dependency-free program provides exact certificates for the finite orbit analysis.

For an integer-valued sequence $\{a(n)\}_{n\geq 0}$ and a prime $\ell$, a Ramanujan-type congruence is a relation of the form $a(\ell n-\delta_{\ell})\equiv 0\pmod\ell$, where $\delta_{\ell}$ is a specific shift. In this paper, we present explicit constructions of modular forms to establish Ramanujan-type congruences for a broad class of generating functions, including eta-quotients, weakly holomorphic modular forms, and mock modular forms. As applications, our explicit approach provides a unified framework to not only recover known congruences but also establish new non-congruence results and explicit congruences for various combinatorial and arithmetic functions.

This note addresses the resonance of monomial subspaces. In the first part, we completely characterize the cases where the Fitting scheme structure of the resonance associated with a monomial subspace is reduced, and we further investigate the primary decomposition of the corresponding Fitting ideal. The second part focuses on non-monomial subspaces having the resonance of a monomial subspace.

In a previous note, a two-player game between a random player and a deterministic player was introduced, and it was shown analytically that the winning probability of the deterministic player is the derangement probability dn/n!. The natural question left open was to explain this coincidence combinatorially. This paper gives such an explanation and extends it to a larger family of games. In the generalized game, the deterministic player removes q elements per turn, or all remaining elements if fewer than q remain. We couple the game exactly to the cycle decomposition of a uniformly random permutation. Under this coupling, the random player wins precisely when the first cycle of length at most q, read in canonical cycle order, is a fixed point. The case q = 1 recovers derangements, while the general case is governed by the first short cycle of the permutation.

We study monadic dependence of binary relational structures including at least one antisymmetric relation. Our cornerstone result gives sufficient conditions for proving that a structure is monadically dependent by only considering some of its reducts, assuming they are structurally well-behaved and compatible enough. As an application, we consider some reorientation rules preserving monadic dependence of binary structures, as well as replacement of one antisymmetric relation with bounded independence number by another. Then, we apply our main (technical) result to the study of twin-width in two ways. First, generalizing the fact that twin-width boundedness is equivalent to being expandable by a linear order into a monadically dependent class, we prove that it is also equivalent to being expandable by an oriented graph with bounded independence number (for instance by a poset with bounded width or by a tournament), and that FO-model checking is fixed-parameter tractable on such an expansion. Second, we show delineation by twin-width for some new classes of oriented graphs, including oriented split graphs and local tournaments. In all these cases, we also obtain fixed-parameter tractability of FO-model checking.

Inspired by research on the Cartesian product of two lattice polytopes, this paper investigates the Ehrhart theory of the join of two lattice polytopes. This is also a well-known open problem listed on the website of the American Institute of Mathematics. This paper resolves this open problem. We first construct counterexamples showing that the join of two Ehrhart positive polytopes is not necessarily Ehrhart positive. Then we prove that if two lattice polytopes have the integer decomposition property and the spanning property, then their join also has these two properties. However, the very ample property is not inherited under joins. Finally, we show that unimodular triangulations, regular triangulations, and quadratic triangulations are preserved under the join operation. As a byproduct, we state the necessary and sufficient condition for the Cartesian product of two Gorenstein lattice polytopes to remain Gorenstein.

A Dyck path of semilength $n$ is a lattice path from $(0,0)$ to $(n,n)$ consisting of $n$ right-steps $(1,0)$ and $n$ up-steps $(0,1)$ that never rises above the line $y=x$. These paths are enumerated by the Catalan numbers and play a central role in enumerative combinatorics. We color the cells of the integer grid in black and white according to two natural patterns, namely chessboard and column-alternating, and enumerate the Dyck paths having equal numbers of black and white cells beneath them.

The Moving-Target Traveling Salesman Problem (MT-TSP) seeks a minimum cost trajectory for an agent that departs from a static depot, visits a set of moving targets, each within one of their assigned time windows, and returns to the depot. In this article, we study the Moving-Target Traveling Salesman Problem with Moving Obstacles (MT-TSP-MO), a generalization of the MT-TSP where the agent trajectory must avoid moving obstacles. We present a Mixed-Integer Conic Programming (MICP) formulation that can be solved using off-the-shelf solvers, as well as a fast and scalable Two-Phase Bilevel Search (TPBS) algorithm that computes high-quality feasible solutions for the problem. We evaluate our approaches against an existing baseline algorithm on a broad range of problem instances with up to 40 targets and 40 obstacles. The results demonstrate that both the proposed methods significantly outperform the baseline with respect to success rates, solution costs, and computation time.

In this short article we consider a preferential attachment random graph model with edge steps, studied by Alves, Ribeiro and Sanchis. Starting with an initial graph $\mathbb{G}_1$ formed by a vertex with a self-loop attached to it, the model evolves as follows. At every subsequent (discrete) time step, either with probability $p$ we add a vertex to the graph and connect it to exactly one of the older vertices selected with probability proportional to its degree, or with probability $1-p$ we add one edge between two existing vertices, both selected (independently) with probability proportional to their degrees. Let $\omega(\mathbb{G})$ be the clique number of a graph $\mathbb{G}$, i.e.\ the number of vertices in a largest complete subgraph of $\mathbb{G}_{}$. Alves, Ribeiro and Sanchis showed that, for any given $\varepsilon>0$, we have $\omega(\mathbb{G}_{2t})\geq t^{\frac{1-p}{2-p}(1-\varepsilon)}$ with high probability (i.e.\ with probability tending to $1$ as $t\rightarrow \infty$). Here we strengthen this bound by showing that, for any function $f:\mathbb{N}\mapsto \mathbb{N}$ that satisfies $f(t)\rightarrow \infty$ as $t\rightarrow \infty$, with high probability \[\omega(\mathbb{G}_{2t}) = \Omega\left(t^{\frac{1-p}{2-p}}\Big(\log^{\frac{1}{2-p}}(t)f(t)\Big)^{-1}\right).\]

Perfect sphere packing in the Boolean space is a fundamental and complex problem with significant implications for coding theory, cryptography, and discrete mathematics. The classical solution to the perfect sphere packing problem was provided by Hamming via his well-known perfect codes. However, a major limitation of the traditional Hamming metric is its strict applicability, as it allows perfect partitioning only for spaces with specific, highly constrained dimensions. To address this structural limitation, this article introduces a novel distance metric specifically designed for Boolean hypercubes. The proposed metric modifies the topological properties of the space, making it mathematically viable to partition a Boolean space of any arbitrary dimension into disjoint, perfect spheres. We rigorously define the algebraic properties of this new distance function and demonstrate its consistency across various dimensions. Furthermore, we explore the structural characteristics of the resulting packings. This approach bypasses the classical dimensional constraints of Hamming codes, potentially opening new avenues for designing error-correcting codes and cryptographic primitives in non-traditional dimensions.

We introduce a closure operator for valuated matroids and prove that it yields a cryptomorphic definition of valuated matroids. As an application, we introduce a class of modules over the tropical semifield (geometric modules) and prove that there is one-to-one correspondence between projective equivalence classes of simple valuated matroids and isomorphism classes of finitely generated geometric modules. We further illustrate how this correspondence can be lifted to simple infinite valuated matroids and geometric modules.

In this paper we introduce "graph linear notation" – a complete graph invariant – which is positioned as an alternative definition for the finite graphs. This invariant is constructed using an algorithm similar to the algorithm of finding canonical forms of graphs. Storing graph linear notation instead of a regular graph allows us to greatly simplify two major problems: the construction of illustrations for graphs with regards to possible graph symmetries, and the comparison of two graphs for isomorphism. We also demonstrate the transferability to the graph linear notations such classical graph theory concepts as colourings and graph paths.

In 1921, Kuratowski gave the now-standard definition of ordered pair in the context of set theory. This paper studies the problem of defining ordered tuples as sets in the hierarchy of simple types, of which Kuratowski's construction is a special case.

Dirac asked in 1970 whether for every k >= 4 there is a k-vertex-critical graph without critical edges; Jensen settled all k >= 5, and only k=4 remains open. Following Skottova and Steiner, call a graph G a (4,1)-graph if chi(G)=4, chi(G-v)=3 for every vertex v, and chi(G-e)=4 for every edge e; they proved delta(G) >= 6 and lambda(G) >= 6 for every (4,1)-graph and asked whether a 6-regular (4,1)-graph exists. We prove three results about this 6-regular case. Theorem A (computational): there is no 6-regular 4-vertex-critical graph on n <= 15 vertices, except for a unique graph (up to isomorphism) on n=13, whose 13 critical edges form a Hamilton cycle; hence any 6-regular (4,1)-graph has at least 16 vertices. Theorem B: in a 6-regular (4,1)-graph every 6-edge-cut is either the edge star of a vertex or has both shores of size at least 15; consequently every 6-regular (4,1)-graph on at most 29 vertices is super-6-edge-connected. Theorem C (all sizes): no shore of a nontrivial 6-edge-cut in a 6-regular (4,1)-graph induces a bipartite graph; more generally, a shore whose deficiency is concentrated on two vertices forces them to receive equal colours in every proper 3-colouring. The proof of Theorem B rests on an exact classification of the 3x3 cut matrices of 6-edge-cuts in (4,1)-graphs (exactly 21 matrices, five types up to row/column permutations) together with a boundary-shortfall lemma; the unique near-miss is K_{3,3,3} minus a rainbow 3-matching. Several supporting lemmas are machine-checked in Lean 4/Mathlib.

For a hypergraph $\mathbb{H}$ on $[n]$, the hypergraphic polytope $\triangle_{\mathbb{H}}$ is the Minkowski sum of the standard simplices $\triangle_H$ for all $H \in \mathbb{H}$. We focus here on interval hypergraphs, where all hyperedges are intervals of $[n]$. They are precisely the deformations of Loday's associahedron. Their vertex posets are Tamari interval posets, and we describe which Tamari interval poset appears as a vertex poset in which interval hypergraphic polytope. We also characterize the interval hypergraphs $\mathbb{I}$ for which the hypergraphic polytope $\triangle_\mathbb{I}$ is simple, and we study their vertex posets, which we call weeping willows.

All graphs considered are finite with no isolated vertices. Let $N(m,H)$ be the maximum number of subgraphs of a graph $G$ isomorphic to $H$, taken over all graphs $G$ with $m$ edges. Alon proved that $N(m,H)=\Theta_H(m^{\gamma(H)})$, where $\gamma(H)=(|V(H)|+D(H))/2$ and $D(H)=\max_{S\subseteq V(H)}(|S|-|N_H(S)|)$, and conjectured [Conjecture 1, Isr. J. Math., 1986] that limit of $N(m,H)/m^{\gamma(H)}$ exists as $m\to\infty$. We prove this conjecture and identify the limit as $\lambda(H)=\Lambda(H)/|\operatorname{Aut}(H)|$, where $\Lambda(H)$ is characterized by a variational problem over finite cores. We also resolve another conjecture of Alon [Conjecture 2, Isr. J. Math., 1986], which stated that if $H$ is a disjoint union of stars, then for every $m$ an extremal graph attaining $N(m,H)$ may be chosen to be a disjoint union of stars.

Given a positive integer $n$, define a function on the symmetric group $S_n$ by $$F(\tau) = \sum_{k=1}^{n}k^2\tau(k)^2.$$ Motivated by a conjecture of Zhi-Wei Sun, we investigate the residue classes attained by $F(\tau)$ modulo $2n+1$. We prove that for every integer $n>4$, the set $\{F(\tau):\tau\in S_n\}$ contains a complete residue system modulo $2n+1$. The proof is based on a family of involutions whose values are controlled by subset sums of squares.

In this paper, we investigate zero-sum problems of new types. For example, given $2n-1$ integers $a_1,\ldots,a_{2n-1}$ not divisible by an integer $n>1$, we prove that for some nonempty $I\subseteq\{1,\ldots,2n-1\}$ with $|I|\leqslant n$, the sum $\sum_{i\in I}a_i$ is divisible by $n$ but not divisible by $n^2$. We also pose several conjectures for further research.

This paper studies the probability of substructures occurring in random Latin squares. Our main result states that if $\alpha,\beta>0$ are such that $2\alpha+\beta<1$, then there are positive constants $\delta = \delta(\alpha, \beta)$ and $\Delta = \Delta(\alpha, \beta)$ such that if $P$ is a partial Latin square of order $n$ with $k = k(n)$ non-empty cells occupying at most $\alpha n$ rows and $\beta n$ columns, the probability that a random Latin square of order $n$ contains $P$ lies between $(\delta/n)^k$ and $(\Delta/n)^k$. We apply this result to subsquares in random Latin squares to obtain the first proof of the fact that the expected number of subsquares of order $3$ in a random Latin square of order $n$ is non-vanishing as $n \to \infty$. We are also able to provide the best known asymptotics for the expected number of subsquares of order $a$ in a random Latin square of order $n$ when $2<a=o(n^{1/2})$. Finally, we discuss the implications of our result on other configurations in random Latin squares as well as on completions of partial Latin squares.

We consider the relationships between the domination number of graph, denoted $\gamma$, and the distance-$2$ domination number, denoted $\gamma_2$, and three parameters that lie between them: the packing number, denoted $\rho$, the lower packing number, denoted $\rho_L$, and the isolation number, denoted $\iota$. There has been recent attention on the question of whether $\gamma/\rho$ is bounded or unbounded for various families of graphs. We consider similar questions for the ratios of the five parameters. In particular we show that, while $\gamma/\rho_L$ is unbounded in trees, it holds that $\iota/\gamma_2$ is less than $2$ for all trees. Further, $\gamma/\rho_L$ is at most $3$ in interval graphs, at most~$4$ in permutation graphs, and at most $5$ in general asteroidal-triple-free graphs. We also show that every tree has a set of vertices that is both isolating and a packing, and characterize trees where $\rho=\rho_L$.

We prove an average-degree lower bound on the independence number of uncrowded uniform hypergraphs. For every fixed $r\geq 2$ and every $\eta>0$, there exists $d_*=d_*(r,\eta)$ such that any uncrowded $(r+1)$-uniform hypergraph $G$ with $n$ vertices and average degree $d\geq d_*$ satisfies \[ \alpha(G)\geq (1-\eta)r^{-1/r}\left(\frac{\log d}{d}\right)^{1/r}n. \] The proof combines a cleaning procedure, which reduces the maximum top-layer degree to the average scale, with a random nibble procedure that repeatedly extracts independent vertices while controlling all lower-order degrees created by the process. After an initial top-layer cleaning, we run a trace nibble. Since the residual hypergraph contains traces of all sizes $2,\ldots,r+1$, we track the maximum degrees in every layer. A binomial-type recurrence for this degree profile yields the stated leading constant.

Let $G$ be a finite connected weighted graph and let $R$ be its effective-resistance matrix. For every nonempty vertex set $S$, we factor the cofactor sum and determinant of the principal resistance submatrix $R[S]$ into an enumerative term and a boundary potential-theoretic term. If $\tau(G)$ is the weighted spanning tree enumerator and $\kappa_G(S)$ is the weighted enumerator of $S$-rooted spanning forests, then \[ \cof R[S]=(-2)^{|S|-1}\kappa_G(S)/\tau(G). \] After Kron reduction to $S$, with reduced Laplacian $K=L^S$, $Q=K^+$, and $q=\diag(Q)$, the remaining normalized factor is \[ \det R[S]/\cof R[S] =\frac{2}{|S|}\tr Q+\frac12 q^{\mathsf T}Kq. \] The cofactor factor is a principal specialization of known resistance-minor identities; the contribution here is the boundary/Kron-reduction factorization and local radius calculus. Equivalently, the normalized factor is the maximum of $u^{\mathsf T}R[S]u$ over all $u\in\R^S$ satisfying $\one^{\mathsf T}u=1$. This optimization viewpoint yields monotonicity under enlargement of $S$, an exact one-point update formula, and a support criterion for equality. Small star examples show that the resulting set function is neither submodular nor supermodular in general.

Improving an earlier bound of Frieze and Mubayi, Iliopoulos showed that any $k$-uniform uncrowded hypergraph of maximum degree $\Delta$ has list chromatic number at most $(1+o(1))(k-1)\Big(\frac{\Delta}{\log\Delta}\Big)^{\frac{1}{k-1}}$. Determining the optimal leading constant in this bound remains a major open problem. A natural target for the constant, suggested by the coupon-collector heuristic, is $(k-1)^{\frac{1}{k-1}}$, which also arises independently as the shattering threshold for coloring and finding large independent sets in sparse random hypergraphs. We show that uncrowded hypergraphs attain this threshold: for $k \ge 2$, every $k$-uniform uncrowded hypergraph $\mathcal{H}$ of maximum degree at most $\Delta$ satisfies $$\chi_\ell(\mathcal{H})\le(1+o(1))\Big((k-1)\frac{\Delta}{\log\Delta}\Big)^{\frac{1}{k-1}}.$$ This matches the coupon-collector heuristic, and establishes a 2019 conjecture of Molloy for uncrowded hypergraphs. As a consequence, we show that every $k$-uniform linear hypergraph of maximum degree at most $\Delta$ has chromatic number at most $c_k\Big(\frac{\Delta}{\log \Delta}\Big)^{\frac{1}{k-1}}$ with $c_k=1-o_k(1)$, resolving, in a stronger form, a recent conjecture of Verstraëte and Wilson on the independence number of linear hypergraphs. Our techniques yield the first palette sparsification result for hypergraph coloring using $o(\Delta^{\frac{1}{k-1}})$ colors per vertex. Specifically, for an uncrowded $k$-graph $\mathcal{H}$ and $q=\Theta\Big({\Big(\frac{\Delta}{\gamma\log\Delta}\Big)^{\frac{1}{k-1}}}\Big)$, sampling $\Theta(\Delta^{\frac{\gamma}{k-1}})$ colors per vertex suffices to obtain a proper $q$-coloring of $\mathcal{H}$ w.h.p. As an algorithmic consequence, we obtain a single-pass streaming algorithm using $O\big(n^{1+o(1)}\big)$ space for uncrowded $k$-graphs, and, via hypergraph partitioning, for linear hypergraphs as well.