Papers

We consider the integer version of Alkan–Gale's model on stability in a two-sided market, called the stable generalized allocation one. It is given by a triple $(G,b,C)$, where $G=(V,E)$ is a finite bipartite graph with nonnegative integer capacities $b(e)\in{\mathbb Z}_+$ of edges $e\in E$, and for each vertex (“agent”) $v\in V$, the preferences on the set $E_v$ of its incident edges depend on a choice function $C_v$. The latter acts on the set of vectors in ${\mathbb Z}_+^{E_v}$ bounded by the capacities and obeys the standard axioms of substitutability and size monotonicity. Alkan–Gale's prominent theorem implies that the stability problem in this case always has a stable solution $x\in{\mathbb Z}_+^E$ and, moreover, the set ${\cal S}_{G,b,C}$ of these solutions (“stable generalized allocations”) forms a distributive lattice. However, this lattice is rather intricate to construct and work with, and we wonder whether it can be represented via a “simpler” stability model. Answering this issue, we arrange a sort of splitting techniques to embed ${\cal S}_{G,b,C}$, as a sublattice, in the lattice of stable matchings and, more compactly, in the lattice of stable allocations (as in Baiou–Balinski's stability model). This generalizes Fleiner's result on a detachment in the special case with all-unit capacities. Keywords: stable marriage, stable allocation, choice function, rotation, distributive lattice, poset representation

We prove coefficientwise positivity of Chapoton's $q$-Zeta numerator for the positive-root poset of every finite reduced irreducible crystallographic root system, using root height minus one as the rank function and Chapoton's fixed denominator. Adjoining a minimum gives a lower-semimodular lattice, and a classical labelling of its dual yields a weighted descent formula. The same argument proves positivity on every interval of the augmented root poset. Signed EL-labellings give explicit path formulas for Ferrers-cell posets with arbitrary admissible nonincreasing boundaries, including the root posets of types $A$, $B$, and $C$, and for their intervals. A coloured lift gives a root-height-weighted formula in type $D$. For trapezoidal boundaries, we obtain Gaussian-binomial formulas and sharp coefficient bounds. At $q=1$, a Jacobi-polynomial representation gives simple negative zeros, strict interlacing along fixed-offset sequences, and a limiting zero distribution. The main results of this paper were obtained through a generative-AI workflow using OpenAI GPT-5.6 Sol, Anthropic Claude Fable 5, Grok 4.6, OpenAI GPT-6 Astra, OpenAI GPT-6.1 Sol, and Anthropic Claude Fable 5.1. Further details appear in the disclosure at the end of the paper.

We show that for $n \geq 6$ each element of the commutator subgroup in the symmetric group $\mathfrak{S}_n$ resp. in the signed symmetric group $(\mathbb{Z}/2\mathbb{Z})^n\rtimes\mathfrak{S}_n$ is the commutator of two $n$-cycles resp. the commutator of two $n$-cycles with a negative sign product; with one exception. If $n \equiv 2$ $\mathrm{mod}~4$, the element $-\mathrm{id}$ of $(\mathbb{Z}/2\mathbb{Z})^n\rtimes\mathfrak{S}_n$ is not such a commutator. In the language of Coxeter groups, this yields a description of commutators of Coxeter elements in types $A$ and $B$.

Garamvölgyi, Jordán, Király and Villányi [{Forum Math. Pi 13 (2025), Paper No.~e11}] posed two sharp connectivity conjectures for packing rigid spanning subgraphs: one for the equal-dimensional case and the other for the packing of a $d$-rigid spanning subgraph with a spanning tree. We prove a unified theorem: for arbitrary positive integers $d_1,\ldots,d_s$, every $\sum_{i=1}^{s}d_i(d_i+1)$-connected graph contains pairwise edge-disjoint spanning subgraphs $H_1,\ldots,H_s$ such that $H_i$ is $d_i$-rigid for every $i$. The connectivity bound is sharp whenever $\sum_{i=1}^{s}d_i(d_i+1)\ge4$. As special cases, the theorem settles both conjectures, confirms the conjecture of Garamvölgyi, Jordán and Király [J. Combin. Theory Ser. B 166 (2024), 1–29] that every $tk(k+1)$-connected graph contains $t$ pairwise edge-disjoint $k$-connected spanning subgraphs, and gives the sharp threshold $d(d+1)+2r$ for packing one $d$-rigid spanning subgraph together with $r$ pairwise edge-disjoint spanning trees. We also obtain two upper bounds related to Thomassen's conjecture on highly connected orientations of graphs. If $f(q)$ is the least integer such that every $f(q)$-connected graph has a $q$-connected orientation, then $f(q)\le(25q^2+41q-16)/2$ for every $q\ge3$ and $f(q)\le8q^2+212q+1404=(8+o(1))q^2$ for all sufficiently large $q$; these two results reduce the leading coefficient in the previous quadratic bound from $320$ to $25/2$ for every $q\ge3$ and $8$ for all sufficiently large $q$. Compared to the bound for $f(q)$ obtained by Garamvölgyi et al. we obtain the better bounds, not only through our tight rigidity result but also by exploiting the leftover edges when we remove two edge-disjoint spanning (sufficiently) rigid graphs.

Heffter arrays, introduced by Archdeacon in 2015, are combinatorial structures with applications to cyclic cycle systems and biembeddings of graphs on surfaces. Costa, Morini, Pasotti and Pellegrini proposed in 2020 the notion of relative Heffter arrays as a generalization of classical Heffter arrays, inspired by the concept of relative difference families. In their work, the existence problem of integer relative Heffter arrays $\mathrm{H}_k(n;k)$ was solved for all $k\neq 5$, while the case $k=5$ and $n \equiv 0 \pmod{4}$ remained open, apart from two sporadic examples with $n=8,16$. In this article, we consider this open problem and we construct an $\mathrm{H}_5(n;5)$ for every $n\equiv 0 \pmod{4}$, $n\geq 12$. As a consequence, the existence problem of integer relative $\mathrm{H}_k(n;k)$ is completely settled.

Given two positive integers height $h$ and order $n$, the barrycade construction problem asks for a set of $h$ permutations of the integers from $1$ to $n$ such that all the proper partial sums given by these permutations are pairwise distinct. The name barrycade was coined by Richard K. Guy and refers to Barry Cipra, who introduced this kind of arrangement problem. A simple calculation shows that a solution can only exist for $n \ge 2h-2$ and it is conjectured that there always exists a solution for every height $h \ge 2$ and order $n \ge 2h-2$. In this work, for every height $h \ge 1$, we present a construction of a barrycade of height $h$ and order $n = 2h+3$. We also present a randomized heuristic that allows us to find a barrycade of height $h$ and conjectured optimal order $n=2h-2$, for every height $2 \leq h \leq 50$. Thus, we confirm the conjectured optimal order for all heights up to $50$. We also consider a related corral construction problem, where the permutations define a cyclic arrangement. In this setting, for every height $h \ge 1$, we present a construction of a corral of height $h$ and order $n=2h$. A heuristic approach, similar to the one used for barrycades, allows us to find a corral of height $h$ and conjectured optimal order $n=2h-1$, for every height $1 \leq h \leq 50$. We confirm Tomoki Nakamigawa's conjecture on well-dispersed partitions of cyclic groups for the number of parts up to $20$.

For a family $\mathcal{F}$ of $k$-graphs, $ex_k(n,\mathcal{F})$ denotes the maximum number of edges in an $n$-vertex $\mathcal{F}$-free $k$-graph. Let $M_{s+1}^k$ denote a matching of size $s+1$ in $k$-uniform hypergraphs. Recently, Alon and Frankl (JCTB, 2024) determined $ex_2(n,\{M_{s+1}^2,K_{\ell+1}\})$ for all $n\geq 2s+1$ and $\ell\geq 2$. For every non-bipartite graph $F$, Gerbner (JGT, 2024) determined $ex_2(n,\{M_{s+1}^2,F\})$ for sufficiently large $n$. In this paper, we investigate this problem for different ranges of the matching parameter. First we prove that for every graph $F$ with $\chi(F)>3$, there exist constants $\beta>0$ and $s_0$ such that $ex_2(n,\{M^2_{s+1}, F\})=ex_2(2s+1,F)$ for $\max\{s_0,n/2-\beta n\}<s<n/2$. For integers $\ell\ge k\ge3$, let $\mathcal{K}_{\ell+1}^k$ be the family of all $k$-graphs $F$ with at most $\binom{\ell+1}{2}$ edges for which there is an $(\ell+1)$-set $L$ such that every pair of vertices of $L$ is covered by an edge of $F$, and let $H_{\ell+1}^k$ be the $k$-uniform hypergraph obtained from the complete graph $K_{\ell+1}$ by enlarging each edge with a set of $k-2$ new vertices, which is a member of $\mathcal{K}_{\ell+1}^k$. We determine $ex_k\bigl(n,\mathcal{K}_{\ell+1}^k\cup\{M_{s+1}^k\}\bigr)$ for $s< \frac{n}{8(k-1)^{k-2}(\ell-1)^3}$. For sufficiently large $s$, we also determine $ex_k\bigl(n,\{M_{s+1}^k,H_{\ell+1}^k\}\bigr)$ for $\frac{n}{k}-\beta n<s\leq \frac{n-k}{k}$ and $s< \frac{n}{8(k-1)^{k-2}(\ell-1)^3}$.

We prove the Courtade-Kumar conjecture: among all Boolean functions $f\colon \{-1,1\}^n\to\{-1,1\}$, a dictator retains the most information about a uniformly random input observed through independent binary noise.

We prove that every triangle-free graph with minimum degree at least $\frac{n}{3}$ is $4$-colorable and thereby settle a problem of Brandt and Thomassé (2005) at the threshold $\frac{n}{3}$. The number four is best possible. For a positive integer-valued function $f(n)=o(n)$, we relate the chromatic number of $f(n)$-vertex subgraphs of the Kneser graph $KG(n,f(n))$ to that of triangle-free graphs with minimum degree at least $\frac{n}{3}-f(n)$. Consequently, for every $0<\delta<1$ and $\varepsilon>0$, and for all sufficiently large $n$, every $n$-vertex triangle-free graph with minimum degree at least $\frac{n}{3}-n^{1-\delta}$ has chromatic number at most $10^{391}+1+\left\lceil{(1+\varepsilon)(1-\delta)}/{\delta}\right\rceil$. We also show that every sufficiently large $n$-vertex maximal triangle-free graph with minimum degree at least $\frac{n}{3}-f(n)$ and chromatic number at least $10^{391}$ contains a bipartite subgraph with parts of orders $\frac{n}{3}-O(f(n))$ and $\frac{2n}{3}-O(f(n))$; the remaining induced subgraph admits a homomorphism to $KG(\frac{n}{3}-O(f(n)),O(f(n)))$. Finally, we connect maximal $K_r$-free graphs with minimum degree at least $\frac{2r-5}{2r-3}n-f(n)$ to $K_{r-1}$-free graphs and extend these results to $K_r$-free graphs. Our proofs employ the recent strong Brandt–Thomassé theorem of Łuczak, Polcyn, and Reiher.

Koornwinder moments generalize the Askey–Wilson moments arising in the asymmetric simple exclusion process. Rains conjectured that, under the specialization $t=q$, the minimal numerators of Koornwinder moments have nonnegative integer coefficients. While the one-row case of this conjecture was previously proved by Corteel, Mandelshtam, and Williams using rhombic staircase tableaux, its dual counterpart, the one-column case, has remained open. In this paper, we derive a closed, manifestly positive combinatorial formula for the normalized numerators of the coefficients of the rescaled Askey–Wilson polynomials. This proves Rains' conjecture for one-column partitions, thereby providing the exact dual counterpart to the previous result.

Given two weighted directed graphs of order \(n\), we study how much their overlap can deviate from its random average under relabelling, and how concentrated the distribution of their intersection is when they are placed at random. Bollobás and Scott studied these problems on weighted $k$-uniform hypergraphs and raised the corresponding questions for directed graphs. In this paper, we study these problems for weighted directed graphs and obtain results analogous to those in the weighted hypergraph setting.

A graph $G$ is $F$-free if it does not contain $F$ as a subgraph. Let $\mathrm{spex}(n,F)$ be the maximum spectral radius over all $n$-vertex $F$-free outerplanar graphs. For integers $t\geq1$ and $l\geq2$, let $P_{t\cdot l}$ be the starlike tree with $t$ branches of length $l-1$. For sufficiently large $n$, Yin, Li, and Meng [arXiv:2504.04364v1] characterized the unique extremal graph for $\mathrm{spex}(n,P_{t\cdot l})$ when $t=1$, $t=2$, or $t\geq4$. They left the case $t=3$ open and proposed a natural candidate for the extremal graph. We show that this candidate is not extremal and determine the unique extremal graph for $\mathrm{spex}(n,P_{3\cdot l})$. For every $l\geq3$ and all sufficiently large $n$, this unique extremal graph is $K_1\vee\bigl(2P_{2l-3}\cup qP_{l-2}\cup P_r\bigr),$ where $q$ and $r$ are integers satisfying $n=2(2l-3)+q(l-2)+r+1,$ $q\geq0,$ $0\leq r<l-2.$

Let $k\geq 3$ and $\alpha\in[0,1)$, and let $\lambda_k(\alpha)$ denote the $\alpha$-spectral radius of a $k$-uniform loose cycle. Lu and Man classified all connected $k$-uniform hypergraphs with adjacency spectral radius at most $\lambda_k(0)$. In this paper, we extend their classification to the $\alpha$-spectral setting. In particular, for every $k\geq 3$ and $0<\alpha<1$, we prove that $\lambda_k(\alpha)$ is the smallest limit point of the $\alpha$-spectral radii of connected $k$-uniform hypergraphs. Moreover, we give a complete comparison between the $\alpha$-spectral radius of an arbitrary finite connected $k$-uniform hypergraph $H$ and that of a loose cycle by determining the sign of $\rho_\alpha(H)-\lambda_k(\alpha)$. As a consequence, for each fixed $0<\alpha<1$, we classify all finite connected $k$-uniform hypergraphs with $\alpha$-spectral radius at most $\lambda_k(\alpha)$.

In this article, we first introduce quasi-overlap and quasi-grouping functions on bounded pseudo-ordered sets, respectively, and give their respective preliminary constructions and the induced quasi-overlap functions on quotient posets.. We then explore the invariant properties under weighting and automorphisms. We also introduce the migrativity, the homogeneity, the idempotency, the cancellation law, the Archimedean and limiting properties of quasi-overlap functions and discuss their relations. We finally present two constructing methods of quasi-overlap functions, which are based on boundary-faithful mappings and adjunctions on bounded psosets and the transitive-endpoints of a bounded trellis, respectively. The corresponding statements are valid for quasi-grouping functions as well.

Motivated by higher-dimensional generalizations of Sudoku, we study exact block-structured decompositions, algebraic characterizations, and orthogonality for Sudoku hypercubes. Let $n=\prod_{i=1}^d a_i$, let $b_i=n/a_i$, and consider the $\lambda$-fold complete $d$-uniform $d$-partite hypergraph with $d$ vertex classes of size $n$, where the $i$th class is partitioned into $a_i$ groups of size $b_i$. Given positive integers $m_1,\dots,m_k$ with $\sum_{j=1}^k m_j=\lambda n^d$, we partition the edges into color classes of sizes $m_1,\dots,m_k$ so that, in color $j$, vertex degrees and block counts are each either $\lfloor m_j/n\rfloor$ or $\lceil m_j/n\rceil$, while the multiplicity of an underlying edge is either $\lfloor m_j/n^d\rfloor$ or $\lceil m_j/n^d\rceil$. When $m_j=nr_j$, the vertex and block balances are exact, yielding block factorizations and higher-dimensional Sudoku analogues of Baranyai's theorem. Within the same block framework, we give a Delsarte characterization of the Sudoku condition using association schemes and study mutually orthogonal Sudoku hypercubes of order $q^3$ for prime powers $q$. For block sizes $(q^3,q^2,q)$ and $(q^3,q^3,1)$, the resulting families attain a general upper bound and are best possible. For block size $(q^2,q^2,q^2)$, we construct $q^2(q^2-1)(q^2-q)$ mutually orthogonal hypercubes; this construction is asymptotically best possible as $q\to\infty$.

We report certified computations on four no-three-in-line questions, two in the cube and two in the plane, by one method: exact decision procedures inside symmetry strata, every witness re-verified by a second program sharing no code, every number traced to a public journal. (I) Let a(n) be the largest number of points of {0,...,n-1}^3 with no three collinear (A399138). We determine a(1),...,a(6) = 1, 8, 16, 28, 40, 64 with DRAT-certified unsatisfiability proofs, give certified lower bounds a(7) >= 73, a(8) >= 94, a(9) >= 116, a(10) >= 138, a(11) >= 164, and prove a(p) >= p^2 for every prime p. The optima share a layer structure 2n^2 - 2n + 4 that provably fails at n = 5 and n = 7. (II) For b(n), the largest number with no four coplanar (A280537), nineteen public configurations give lower bounds for 9 <= n <= 29, four of which improve the known bounds and their monotone closure (b(12) >= 31, b(21) >= 47, b(22) >= 49, b(27) >= 56); the cyclically invariant subspace has maximum 23 at n = 9 and 26 at n = 10; four kinds of symmetry are incompatible with the problem; no upper bound beyond 3n is known. (III) The Guy-Kelly first-moment heuristic for the plane is audited against exact counts (A000755 to n = 20): its corrected constant comes out in closed form, pi/sqrt(3), the threshold crossing n = 493 is reproduced, and its error is shown to depend on the shape of the question rather than on n alone, with an unbounded multiplier; whether the residual error is Theta(n) or Theta(n ln n), which decides whether the constant survives, cannot be told by counting, and we measure how far from telling we are. (IV) The direction spectrum of the 2n-point solutions is measured, and a line model with no fitted parameter reproduces its shape (fifteen constants within 12%, seven predicted blind) but not its scale. Withdrawn claims are kept in the text; each part states what it does not establish.

We introduce several Ramsey-theoretic properties of 0-dimensional ambits and obtain their dynamical characterizations. In consequence, we obtain Ramsey-theoretic criteria for triviality and for profiniteness of some important invariants (in particular, of the Ellis groups) of the ambits in question. This yields a criterion for the structural property that each distal minimal factor of the given ambit is a profinite flow. Another result is a criterion for metrizability of the minimal left ideals in the Ellis semigroup. Then we study three specializations of the above abstract context: to first order theories, to definable groups, and to the classical Kechris-Pestov-Todorčević theory, recovering known and obtaining new results in each of these contexts.

A sub-quorum coloring is a partial vertex coloring in which every colored vertex sees at least half of its colored closed neighborhood in its own color. We study the maximum number of colors $\psq(G)$ from structural, algorithmic and extremal viewpoints. Every $2$-independent set yields a sub-quorum coloring, so $\psq(G)\ge\beta_2(G)$. We prove the degree bound $\psq(G)\le \Delta(G)|V(G)|/(\Delta(G)+\delta(G)-1)$ for $\delta(G)\ge2$, and obtain an exact matching characterization for graphs of maximum degree at most three. Consequently every cubic graph of order $n$ satisfies $n/2\le\psq(G)\le3n/5$, with a stability identity at the upper endpoint. For trees we give an edge representation and a linear-time dynamic program that computes both $\psq(T)$ and an optimal coloring; we also show on the double star $S_{2,2}$ that $\psq$ can exceed the dissociation number even on trees. We prove NP-completeness even for bipartite graphs and determine exact values for several classical families. For rectangular grids, we formulate the conjecture $\psq(G_{m,n})=\beta_2(G_{m,n})=F(m,n)$, recover the dissociation-number formula from known $3$-path vertex-cover results, prove the ladder case directly, and verify the conjecture for every fixed width $2\le m\le11$; widths $3$ through $11$ use exact transfer certificates. For hypercubes we prove $\psq(Q_n)=\beta_2(Q_n)=2^{n-1}$ for every $n\ge2$. Finally, a Nordhaus–Gaddum argument gives $\psq(G)+\psq(\overline G)>\log_2 |V(G)|$ and leads to a complementary upper-bound problem.

In this paper, we determine the precise asymptotics of the number of parts of stable regularity equipartitions in terms of the Littlestone dimension: every graph $G$ of Littlestone dimension $\operatorname{Lit}(G)\leq\ell$ has a regular equipartition into excellent sets with $(1 + o_{\epsilon\to 0,\ell}(1))\cdot\epsilon^{-\ell-1}$ parts and in the other direction, for every $\ell\in\mathbb{N}_+$, there is an infinite family of graphs, all of Littlestone dimension $\ell$, whose equipartitions into good sets must have size at least $(1 + o_{\epsilon\to 0,\ell}(1))\cdot\epsilon^{-\ell-1}$. Dropping the equitability condition, we determine the asymptotics of non-equitable partitions up to a multiplicative $\log(1/\epsilon)$: every graph $G$ with $\operatorname{Lit}(G)\leq\ell$ has a regular partition into excellent sets with $(1 + o_{\epsilon\to 0,\ell}(1))\cdot\epsilon^{-\ell}\cdot\ln(1/\epsilon)$ parts and in the other direction, for every $\ell\in\mathbb{N}_+$, there is an infinite family of graphs, all of Littlestone dimension $\ell$, whose partitions into good sets must have size at least $(1 + o_{\epsilon\to 0,\ell}(1))\cdot\epsilon^{-\ell}$. We also show that such partition can be obtained algorithmically efficiently in an approximation scheme fashion: replacing the $o_{\epsilon\to 0,\ell}(1)$ term above by a constant $c > 0$, we obtain randomized $O_{c,\epsilon,\ell}(n\cdot\log(n))$-time algorithms for partitions/equipartitions into good sets, a deterministic $O_{c,\epsilon,\ell}(n^2)$-time algorithm for partitions into good sets, a deterministic $O_{c,\epsilon,\ell}(n^6)$-time algorithm for equipartitions into good sets, a deterministic $O_{c,\ell,\epsilon}(1)\cdot n^{O(\ell\cdot 2^{2\cdot\ell+4})}$-time algorithm for partitions/equipartitions into excellent sets, and $O_{c,\epsilon,\ell}(\log(n+1))$-space algorithms for partitions/equipartitions into good/excellent sets.

Generalized covering radii measure how many columns of a parity-check matrix are needed to generate several syndromes simultaneously. Their finite-geometric counterparts are $(\rho,t)$-saturating sets, for which every $t$-dimensional subspace is contained in a subspace generated by at most $\rho$ prescribed vectors. We investigate this covering problem for the norm-one configurations associated with generalized Zetterberg codes. We establish the upper bound $2t+1$ over every nonbinary finite field and in an explicit binary range, together with complementary lower bounds obtained by counting subspaces and constructing subfield obstructions. For an explicit range of large $t$, these configurations are $t$-strong blocking sets, and the $t^{\rm th}$ generalized covering radius attains its minimum possible value $t$. For binary Zetterberg codes, we determine the second generalized covering radius in every extension degree and prove that the third radius is seven for an infinite subfamily.

We establish graph-theoretic analogues of the Brauer-Kuroda relations for ramified Galois covers of finite graphs with arbitrary finite Galois groups. These formulas relate the numbers of spanning trees of intermediate quotient graphs and recover the corresponding formulas for unramified covers. Our proofs use $h$-functions defined on multiplicity spaces of complex representations of the Galois group.

We prove that the pairs of integers $0\le m<n$ for which a nondecreasing integer sequence can remain complete after every deletion of $m$ terms and become incomplete after every deletion of $n$ terms are exactly those with $m\le1$. Here a sequence is complete if every sufficiently large integer is a finite sum of terms with distinct indices. This answers Erdős Problem 348, posed by Graham and later included in the book of Erdős and Graham. The proof uses a central-interval theorem: if a complete nondecreasing positive integer sequence $(a_i)$ has prefix sums $S_j$ with $S_j-a_{j+1}\to\infty$, then each sufficiently long prefix represents every integer from any fixed completeness threshold $T$ to $S_j-T$. We also refute Graham's conjecture, later repeated by Erdős and Graham, that $(\lfloor t\gamma^n\rfloor)_{n\ge1}$ is complete for every $t>0$ and $1<\gamma<(1+\sqrt5)/2$. We obtain the counterexample by combining Dubickas's fractional-part theorem with an elementary sign adjustment. For a common base in this range, we further construct two such sequences whose interleaving is incomplete and whose coefficient ratio is not a rational multiple of any integer power of the base.

The shifted lonely runner conjecture was recently disproved by Blanco, Criado and Santos. We give quantitative bounds on its failure as the number of runners grows. The loneliness of a configuration is the maximum, over time, of the distance from the origin to the nearest runner. We write $1/(n+1+E_n)$ for the infimum of loneliness over configurations of $n$ runners on the unit circle with distinct positive integer velocities and arbitrary initial shifts. We prove $E_n\ge\lfloor n/287\rfloor$, which together with the elementary bound $E_n\leq n-1$ implies that $E_n$ grows linearly in $n$. We also show that $E_n\geq1$ for every $n\geq95$.

A set $B$ in an abelian group is a $B_h$ set if every $h$-term sum has a unique representation up to permutation; for $h=2$ these are the Sidon sets. We study a weighted removal problem for this collision-free property: if the $h$-fold sum map has small Rényi entropy loss, how much probability mass must be deleted so that the remaining support is a $B_h$ set? Two Rényi orders arise: $\alpha$ is the order at which the coarsening loss is measured, whereas $\beta$ is the order of the entropy constraint. The diagonal specialization $\beta=\alpha$ ties the two roles together. We determine the resulting stability problem on the positive $(\alpha,\beta)$-quadrant. Stability holds exactly when $\beta\le1$ and $\alpha\ge\beta$. Inside this region the optimal deletion rate is polynomial for $\beta<1$ and logarithmic on the boundary $\beta=1$, where the leading constant is exact; outside it, stability fails through two distinct mechanisms: a supercritical budget and dilution by light atoms. In both unstable regimes the limiting defect is computed exactly. The upper bounds follow from a coarsening inequality with best possible constant, which also yields an entropy-free removal theorem, a finite combinatorial consequence for moments of the representation function, and extensions to $B_h[g]$ sets. Matching constructions show that the phase boundaries and rates are sharp.

We show that the fractional illumination number of every convex body in $\mathbb{R}^d$ is at most $2^d$, with equality exactly for parallelotopes. We also prove that every such body can be covered by at most $2^d(d\log d+d\log\log d+O(d))$ smaller positive homothetic copies as $d\to\infty$, establishing the optimal exponential rate in Hadwiger's covering conjecture. The proofs use a covering measure obtained by minimizing an overlap energy and a greedy covering argument on a finite net.

A set pair system $\{(A_i,B_i)\}_{i=1}^m$ is $1$-cross intersecting if $|A_i \cap B_i|=0$ for all $i$ and $|A_i \cap B_j| = 1$ whenever $i \neq j$. Let $m(a,b,1)$ denote the maximum size $m$ of a $1$-cross intersecting set pair system $\{(A_i,B_i)\}_{i=1}^m$ where $|A_i| \leq a$ and $|B_i| \leq b$ for all $i$. We prove a conjecture of Füredi, Gyárfás, and Király [Combin. Probab. Comput. 32 (2023)] that asserts $m(n,n,1)/\binom{2n}{n} \to 0$ as $n \to \infty$.

Deriving upper bounds on code size from existing bounds is a classical approach in coding theory, dating back to the seminal results of Elias, Bassalygo, and Levenshtein. We study a framework encompassing the Bassalygo–Elias and Levenshtein inequalities for binary and nonbinary (constant-weight) codes and provides certain generalizations. The asymptotic cost of transferring a bound between different symbol compositions is expressed in terms of mutual information, yielding an information-theoretic optimal transport formulation. We determine the optimal permutation-transport cost between arbitrary compositions in terms of their least common majorant in the majorization order. Specializing to symmetric constant-weight compositions yields explicit transport profiles. As a byproduct, we establish unimodality of the asymptotic constant-weight rate as a function of the relative weight. We prove that the resulting closure operators are idempotent and that applying transport before outer Bassalygo–Elias averaging leaves the unrestricted bound obtained from the same input unchanged. We also establish necessary and sufficient conditions for an upper bound to be a fixed point of the closure operator. Since the asymptotic rate function is an upper bound for itself and it is a fixed point, we conclude the Schur concavity of the constant-composition rate function. Finally, we survey existing upper bounds for binary and nonbinary constant-weight and constant-composition codes, combine them into optimized envelopes within the transport framework, and obtain improved theoretical and numerical bounds.

We prove two main algorithmic results in spectral discrepancy. First, we give a deterministic polynomial-time rounding theorem for rational positive semidefinite matrices of arbitrary rank. The algorithm starts from any rational fractional signing and assigns one sign per original matrix. Its discrepancy is less than $3.37\,\|\sum_i \mathrm{Tr}(A_i)A_i\|^{1/2}$. This yields Kadison–Singer half-partitions with error below $1.69\sqrt{\varepsilon}$, as well as deterministic graph signings that control signed adjacency and signed degrees simultaneously. The proof builds on the spectral-potential method of Ezeunala and Jiang (2026) and introduces a new way to choose rounding directions. We prove polynomial bit complexity for the rounding procedure. Second, we give a Las Vegas algorithm for the Bilu–Linial signing problem on an arbitrary prescribed graph. If $G$ has $n$ vertices and maximum degree $\Delta\ge3$, the algorithm terminates almost surely. It uses fewer than $100n^3$ insertion attempts in expectation and returns a signing with $\|A_s\|<2\sqrt{2(\Delta-1)}$. For bipartite graphs its one-sided form gives the sharp universal bound $\|A_s\|<2\sqrt{\Delta-1}$. The algorithm builds the signing by inserting vertices and recursively deleting and restoring neighbors after rejected insertions. In the analysis, the $\sqrt2$ gap to the Bilu–Linial conjecture comes from a factor of two in the bound for vertex deletions in the two-sided case. On a $d$-regular bipartite Ramanujan base the same signing produces a Ramanujan $2$-lift of that prescribed base.

The edge complexity of a weighted graph is the smallest ratio of the Fourier $\ell^1$ and $\ell^2$ norms of its adjacency matrix over all vertex labelings. We study the difficulty of finding this minimum by relating it to a graph symmetry. Adding a universal vertex with sufficiently large incident weight produces an explicit Fourier $\ell^1$ lower bound. We show that equality holds exactly when the source graph has a fixed-point-free involutory automorphism. Two-sided estimates compare the excess above this bound with the squared Frobenius distance to the nearest weighted graph having such a symmetry. For sources of constant weighted degree, these estimates determine the exact leading term as the added weight tends to infinity. A stronger separation for simple source graphs proves that additive $\frac{1}{256N^{\frac{7}{2}}}$ approximation of weighted edge complexity is NP-hard, even on connected graphs of odd order $N$ with at most two distinct positive integer weights, each at most $N^2$. We also prove that recognizing a simple graph with a real Fourier labeling is NP-complete. A seven-vertex example shows that every minimizing labeling can have nonreal Fourier coefficients even when real Fourier labelings exist. An exact rational certificate for this example is included in the appendix.

A majority coloring of a graph $G$ is a vertex coloring of $G$ in which no vertex has more than half of its neighbors colored with its own color. The least number of colors required for a majority coloring of $G$ is the majority chromatic number $\mu(G)$. The majority coloring game, introduced by Bosek et al. (2019), is a two-player Maker-Breaker-type game where the players alternately color vertices while maintaining the majority condition at each vertex; the least number of colors required for the first player to have a winning strategy on $G$ is the majority game chromatic number $\mu_g(G)$. In contrast with the static case, Bosek et al. show that $\mu_g(G)$ is unbounded in general, while $\mu_g(G)\le col_g(G)$, where $col_g(G)$ is the game coloring number of $G$. It is known (cf. Faigle et al. (1993)) that, for any acyclic graph $G$, $col_g(G) \leq 4$, so $\mu_g(G) \leq 4$ as well. We improve this bound by showing that $\mu_g(G) \leq 3$ for any acyclic graph $G$ of maximum degree at most $4$. We also show that $\mu_g(G) = 2$ if $G$ is a nonempty path, star, or complete graph, or a disjoint union of such graphs. These improve the results of Bosek et al. We also initiate the study of the computational complexity of the pre-coloring extension problem for the static and game versions of majority coloring. We show that the Majority $k$-precoloring Extension problem is NP-complete for each $k \geq 2$. When $k = 2$, it remains NP-complete on the class of bipartite graphs where maximum degrees of each part are $5$ and $6$, and when $k = 3$ it remains NP-complete on the class of $12$-regular planar graphs. We show that the game version is PSPACE-complete, even when the number of colors $k=\chi(G)$, and even when $k=2$ and $G$ is a bipartite graph in which one part has maximum degree equal to $9$. The results on the game versions also hold for the variation where Bob starts the game.