Papers

We establish an entropy bridge, and then use it to prove that for any color-critical graph $F$ with chromatic number $\chi(F)=r+1\ge 3$, there exists a constant $\lambda_0=\lambda_0(F)$ such that if $G$ is an $F$-free graph with $\lambda (G)\ge \lambda_0$, then for every $\ell\ge 1$ with $(r,\ell )\neq (2,2)$, \[ \lambda^\ell (G) \le \Big(1-\frac1r\Big)w_\ell(G), \] with equality if and only if $G$ is a regular complete $r$-partite graph; in the case $r=2$ with $\ell$ even, equality holds for every complete bipartite graph. The pair $(r,\ell )=(2,2)$ must be excluded, since the bound fails for several forbidden graphs, e.g., $C_{2t+1}$ with $t\ge 2$. Moreover, walks counts may also be replaced by the homomorphism counts of unbalanced trees. As further applications, we extend a spectral supersaturation result of Bollobás and Nikiforov [J. Combin. Theory Ser. B (2007)], and we also extend the entropic Turán theorem of Chao and Yu [J. London Math. Soc. (2026)] from $K_{r+1}$-free graphs to $F$-free graphs with $F$ color-critical. We provide a framework by passing through weighted Turá theorems of independent interest. If $G$ is $F$-free and $\mathbf{p}$ is a probability vector on $V(G)$ with $\lVert \mathbf{p}\rVert_\infty$ sufficiently small, then \[ 2\sum_{uv\in E(G)}p_up_v \le 1-\frac1r + o(1), \] and the error term $o(1)$ can be removed if and only if $F$ is color-critical. This is a Motzkin-Straus-type inequality in which the clique number of $G$ is replaced by $\chi (F)-1$. The proof of this weighted result combines a blow-up argument, the graph removal lemma, the Erdős-Simonovits stability theorem, a probabilistic sampling argument, and an exact estimate near a complete $r$-partite graph. The bridge linking spectral inequalities to weighted inequalities is based on the entropy method for the Markov chain attached to the Perron vector.

We consider $k$-graphs, $\mathcal{F}\subset \binom{[n]}{k}$, $k\geq 3$. A $k$-graph is called intersecting if any two of its edges have non-empty intersection. It is called a star if all its edges share a common vertex. The $k$-graph $\mathcal{F}$ is called Helly if all its intersecting subfamilies are stars. If the same is required only for subfamilies consisting of three edges, it is called triangle-free. It is well known that for $n\geq 3k/2$, the full star is the unique largest triangle-free family whence the largest Helly family as well. In 1984 Tuza proved the best possible bound $|\mathcal{F}|\leq \binom{n-k-1}{k-1}+\binom{n-2}{k-2}+1$ for Helly families that are not stars, albeit only for some unspecified $n>n_0(k)$. The aim of this paper is twofold. First we establish the same bound for $n>2k$. Second we show that for $n>12k^2$ the same upper bound holds for triangle-free families. It is shown as well that it is not true for $2k<n\leq 3k-4$.

Metric bases of graphs have been widely studied since their introduction in the 1970's by Slater and, independently, by Harary and Melter. In this paper, we concentrate on the existence of vertices in a graph $G$ that belong to all metric bases of $G$. We call these basis forced vertices, and denote the number of them by $\mathrm{bf}(G)$. We show that $\mathrm{bf}(G)\le 2/3(n-k-1)$ for any connected nontrivial graph $G$ of order $n$ having $k$ vertices in each metric basis. In addition, we show that this bound can be attained. Furthermore, the previous result implies the bound $\mathrm{bf}(G)\le 2/5(n-1)$ formulated in terms of the order $n$ of the graph for any nontrivial connected graph $G$. This result answers a question posed by Bagheri et al. in 2016. Moreover, we provide a complete realization of the parameters $n$, $\dim(G)$ and $\mathrm{bf}(G) \ge 1$ within the previous bounds. We consider some extremal cases related to basis forced vertices in a graph, in particular, we give a full characterization of the graphs with $\mathrm{bf}(G) = 2$ and $\dim(G) = n-4$.

A $d$-dimensional $0$-$1$ matrix $M$ of size $n_1\times n_2\times \dots \times n_d$ can be considered as a Boolean function $M: B(n_1\times n_2\times \dots \times n_d) \to \{ 0,1\}$, where $B$ is the $d$-dimensional box of lattice points $(x_1, \dots, , x_d)\in Z^d$ with $0\leq x_i \leq n_i-1$, $1\leq i\leq d$. The $0$-$1$ matrix $M$ can also be described as a subset $P:=P(M)$ of $B$ such that $x\in P$ if and only if $M(x)=1$. A $k$-star with center $p$ in $M$ corresponds to a $(k+1)$-element subset $\{ p, p_1, \dots , p_k\} \subset B$ such that $p$ and $p_i$ differ only in one coordinate (for all $1\leq i\leq k$) and these $k$ coordinates are distinct. Here we consider the problem of determining the maximum number of $1$-entries of a $0$-$1$ matrix $M$ of dimension $d$ and size $n\times n \times \dots \times n$ that avoids all $k$-stars. Our main results are the asymptotical solution of the problem for every $d$ and $k$ (as $n\to \infty$), very close bounds for $k=d$, and the exact solution of the $d=k=3$ case. This problem has connections to several other areas of discrete mathematics, including $k$-partite hypergraphs, independent set problems, dominating set problems and covering codes. One of our tools (concerning maximal packings of induced copies of a given hypergraph) might have independent interest.

A graph $G$ is \emph{$H$-induced-saturated} if $G$ has no induced subgraph isomorphic to $H$ but changing the adjacency of an arbitrary pair of vertices in $G$ creates an induced copy of $H$. The existence problem for $H$-induced-saturated graphs had previously been settled when $H$ is a complete graph, a path, an odd cycle, or an even cycle of length at most $10$. In this paper, for every integer $q\ge3$, we construct a $C_{2q+2}$-induced-saturated graph. Hence, induced-saturated graphs exist for all cycles, except for the cycle of length 3.

We study how irreducible factors associated with main eigenvalues constrain the connected components of generalized cospectral mates. Let $M_G(x)$ be the main polynomial of a graph $G$, and let $\kappa_{\mathrm m}(G)$ denote the sum of the multiplicities in $\phi_G(x)$ of the irreducible factors dividing $M_G(x)$. We prove that every graph $H$ with the same characteristic polynomial and main polynomial as $G$ satisfies $c(H)\leq \kappa_{\mathrm m}(G)$. Consequently, if $T$ is a tree and $H$ is generalized cospectral with $T$, then $\beta(H)=c(H)-1\leq \kappa_{\mathrm m}(T)-1$. We develop the case $\kappa_{\mathrm m}(T)=2$ in detail. Any disconnected generalized cospectral mate is the union of a tree and a connected bipartite unicyclic graph, and the coronals of its two components are uniquely prescribed by the canonical decomposition of the coronal of $T$ with respect to the two irreducible main factors. This turns the existence of a disconnected mate into a component-realizability problem. Factor moments yield realizability and tree-forcing obstructions, while matching data provide complementary characteristic-polynomial information. In particular, the unique cycle of any disconnected mate has length at least $6$, and finitely many matching identities, together with component-coronal realizability, certify generalized cospectrality under an explicit degree bound. As an application, we show that the double star $D(2m,m+1)$ is DGS but not DS whenever $m\geq2$ and neither $m$ nor $2m+2$ is a perfect square. In particular, $D(8t+4,4t+3)$, $t\geq0$, gives an explicit infinite family of such graphs.

Let $G$ be a simple graph of order $n$ satisfying the following Ore-type condition: For any two nonadjacent vertices $x$ and $y$ of $G$, $d_G(x)+d_G(y)\geq n+k-2$, where $1\leq k\leq n-1$, $kn$ is even and $d_G(x)$ is the degree of $x$ in $G$. It is well known that $G$ has a $k$-factor for $k=1$ or $2$. Lu and Ning (J. Graph Theory, 94(2020), 307-319) proved that if $k\geq n/2$, then $G$ has a $k$-factor. In this paper, we show that $G$ has a $k$-factor for any $1\leq k\leq n-1$.

Fix an integer $d\ge1$. We prove that, for all sufficiently large $m$, every digraph $D$ with $m$ arcs and minimum semidegree at least $d$ admits a bisection $V(D)=V_1\cup V_2$ with $\bigl||V_1|-|V_2|\bigr|\le1$ such that \[ \min\{e(V_1,V_2),e(V_2,V_1)\} \ge \frac{d(m+d+1)}{2(2d+1)}. \] Here, for disjoint vertex sets $A,B\subseteq V(D)$, $e(A,B)$ denotes the number of arcs directed from $A$ to $B$. For each $d$, equality holds for infinitely many values of $m$, showing that the additive term $d+1$ is best possible. This answers a question of Liu, Ma and Zu by removing the asymptotic error in the minimum-semidegree bound, strengthens the result to the bisection setting, and determines the optimal additive correction. We also prove that every $n$-vertex digraph with $m$ arcs admits a bisection in which both directed cuts have size at least $(m-n+1)/4$, and that this universal bound is sharp for out-stars.

In this paper, after reviewing recent progress on the cohomology of $\overline{{\cal M}}_{0,n}$, we further our investigation on the cohomology of moduli spaces of pointed curves in continuation of [2,4,5,6,7,8]. In particular, we prove that the Betti number distribution of the Fulton-MacPherson compactification $C[n]$ of the space of $n$ ordered distinct points on any smooth projective curve $C$ is asymptotically Gaussian as $n$ goes to infinity.

A graph is called 10-tough and $(2P_2 \cup P_1)$-free if every vertex set whose deletion leaves at least two components has cardinality at least ten times the number of those components and if the graph has no induced subgraph consisting of two disjoint edges and an isolated vertex. We prove that every finite simple 10-tough $(2P_2 \cup P_1)$-free graph on at least three vertices is Hamiltonian. The proof splits according to whether some edge has joint neighbourhood of order at most $4n/11$. In the small-neighbourhood case, a matched path-cover is compressed to a prescribed matching. In the large-neighbourhood case, an asymmetric analysis of the two components left by a putative small cut yields the required connectivity bound. A Hamilton cycle through the prescribed edges is then expanded, and a cycle-extension lemma inserts the remaining vertices.

Immanants are a class of generalized matrix functions associated with the irreducible characters of the symmetric group. Bürgisser [SIAM J. Comput., 30 (2000), pp. 1023–1040] proved that the computation of hook immanants and immanants corresponding to rectangular Young diagrams of polynomially growing width is VNP-complete under $p$-projections. And he posed an open problem: whether the family of immanants corresponding to rectangular Young diagrams of width $2$ is VNP-complete under $p$-projections. This paper gives a solution to this problem. We prove that, over any field of characteristic zero, the immanant families associated with rectangular Young diagrams of width $2$ and of length $2$ are both VNP-complete under $p$-projections.

For two digraph properties $P_1$ and $P_2$, a $(P_1,P_2)$-arc-decomposition of a digraph $D$ is a partition $A(D)=A_1\mathbin{\dot\cup}A_2$ such that the spanning subdigraphs $D[A_1]$ and $D[A_2]$ have properties $P_1$ and $P_2$, respectively. For example, a (strong,strong)-arc-decomposition of a digraph $D=(V,A)$ is a partitioning $A=A_1\cup{}A_2$ of $A$ so that each of the spanning digraphs $D_i=(V,A_i)$, $i=1,2$ are strongly connected. We prove that it is NP-complete to decide whether a digraph admits an arc-decomposition with properties $(P_1,P_2)$ where $(P_1,P_2)\in \{$(is a perfect matching, having no odd directed cycle), (perfect matching, strong), (perfect matching, having an out-branching), (is a cycle factor, having no odd directed cycle)$\}$. These results settle some open problems posed by Bang-Jensen, Bessy, Gonçalves, and Picasarri-Arrieta [Theoret. Comput. Sci. 928 (2022), 167–182].

We show that various partitions of the canonical basis of quantum groups constructed by Lusztig and by Kashiwara coincide. Using this partition, we show that the subset corresponding to open Richardson varieties equals to the intersection of the subsets corresponding to the Schubert cells. We also show that in type $A$, the weights from open Richardson varieties are saturated in the corresponding Bruhat interval polytope.

For positive integers $n\ge s>r$, let $T(n,s,r)$ denote the minimum number of edges in an $r$-uniform hypergraph on $n$ vertices such that every $s$-set of vertices contains at least one edge. A simple averaging argument shows that the ratio $T(n,s,r)/\binom nr$ is non-decreasing in $n$ and we denote its limit as $n\to\infty$ by $t(s,r)$. The case $s=r+1$ has a rich history, with the previously best known asymptotic bounds for $r\to\infty$ being $1\le r\cdot t(r+1,r)\le 4.91...$ . In this paper, we present a simple probabilistic construction which shows that $(r+2)\cdot t(r+1,r)\le 4$ for every $r\ge1$. We also derandomise it and discuss applications to covering codes.

We prove that every triangle-divisible balanced tripartite graph whose vertex classes have size $n$ and whose partite minimum degree is at least $4n/5$ admits a fractional triangle decomposition. Combined with the multipartite decomposition theorem of Barber, Kühn, Lo, Osthus, and Taylor, this implies that, for every fixed $\varepsilon<1/5$ and all sufficiently large $n$, every $\varepsilon$-dense partial Latin square of order $n$ is completable, improving the previous asymptotic bound of $2/25$. The fractional decomposition theorem is finite and exact. Its proof uses a minimum-weight perfect matching to normalize an arbitrary Farkas dual weighting, followed by an explicit direct-and-two-step routing scheme whose aggregate congestion on every off-matching edge is at most one.

Let the vertices of a graph be revealed one at a time in a uniformly random order, and let the last-isolation time be the last time at which the induced graph on the revealed vertices contains an isolated vertex. For the cycle C_n, write K_n for the number of vertices still unrevealed at this time. We obtain an exact finite-n tail formula for K_n in terms of Stirling numbers of the second kind, together with a compact bivariate generating function. The enumeration comes from reversing the process. An isolated revealed vertex then corresponds to the cyclic pattern 101, but the tail event requires this pattern to be absent from every earlier prefix, not merely from the final set. This prefix condition forces the final one-blocks to be separated by zero-gaps of length at least two and forces the reveal order inside each one-block to be peakless. Since a block of size m has 2^{m-1} peakless orders, summing over block sizes produces the Stirling numbers. We also prove K_n/sqrt(n) -> R, with P(R>x)=e^{-x^2}, and, for every fixed d>=1, K_{n,d}/n^{1-1/(2d)} -> W_d, with P(W_d>x)=e^{-x^{2d}}. Uniform stretched-exponential tail bounds imply convergence of all fixed positive moments. Thus the ordinary cycle has a Rayleigh limit, while its fixed powers give a Weibull family with shape parameter 2d.

Let $G$ denote a finite, connected, simple graph, and let $D$ denote its diameter, and let $d_{G}(u, v)$ denote the distance between vertices $u$ and $v$ in $V(G)$. An antipodal labeling of $G$ is a mapping $f\colon V(G) \to \mathbb{N}_{0}$ such that, for each pair $(u, v)$ consisting of distinct vertices in $V(G)$, the relation $ |f(u) - f(v)| \geq D - d_{G}(u, v) $ holds. The span of $f$ is then defined so that $\operatorname{sp}(f) = \max\{ f(u) - f(v) : u, v \in V(G) \}$. The antipodal number of $G$, denoted with $\operatorname{an}(G)$, may then be defined as the minimum possible span among all antipodal labelings of $G$. Juan and Liu [Ars Combin., 2012] proved the upper bound $\operatorname{an}(C_{4k}) \leq 2k^2 - 1$, and conjectured that $\operatorname{an}(C_{4k}) = 2k^2 - 1$ for each positive integer $k$, and Juan and Liu verified this conjecture for $k \leq 5$. We succeed in proving Juan and Liu's conjecture, which seems to have remained open. The openness of Juan and Liu's conjecture has been noted, over the years, by many authors, including Rao et al. [Contrib. Discrete Math., 2015] and Saha et al. [Theory Comput. Syst., 2022].

Christoph, Müyesser and Wigderson recently asked whether an approximate form of the Erdős-Sós conjecture is robust under random edge deletions. We establish a density-sensitive transference theorem that converts global resilience for bounded-degree trees in sparse random graphs into resilient forest universality in arbitrary dense host graphs. More precisely, if $F$ is an $N$-vertex graph of edge density $\lambda$ bounded away from zero and $p\in[K/N,1]$, then, with probability $1-o(1)$ uniformly over the host and the percolation parameter, every subgraph obtained from $F_p$ by deleting at most an $\alpha$-fraction of its edges contains every bounded-degree forest on at most $((1-\alpha)\lambda-\xi)N$ vertices. Consequently, for every $c>0$, $L\ge1$, fixed $D$ and $\alpha<c$, every graph $F$ on at most $Ld$ vertices with average degree at least $d$ has the property that, after percolation at any rate $p\in[K/d,1]$ and any subsequent deletion of at most an $\alpha$-fraction of the surviving edges, the remaining graph is universal for all forests on at most $(1-c)d$ vertices and maximum degree at most $D$. This includes vertex-disjoint packings of any prescribed collection of bounded-degree trees of that total order. We further obtain forest-universality results for graphs whose connected components have vertex-cover number at most $Cd$, and for graphs that can be brought into this form by deleting sufficiently few edges on the $dn$-scale.

For n points in the unit square, the Heilbronn triangle problem asks for the largest possible minimum triangle area. We develop a variational stress theory for this max-min problem. At every positive-area local optimum, normalized Karush-Kuhn-Tucker multipliers assemble into a skew matrix B satisfying Bz = 2ib, where b is the outward square reaction. This equilibrium has the isotropic affine moment sum_i p_i b_i^T = Delta I_2; the identity also holds for every tight subfamily carrying weights inherited from the same multiplier, with Delta scaled by its multiplier mass. It follows that every positive stress component meets all four sides and that there are at most two such components. To handle nonunique multipliers, we introduce the intersection of the stress kernels over the whole KKT face and a canonical hybrid operator incorporating all tight determinant and boundary derivatives. A strictly convex selector removes every decomposable invisible motion, leaving a rank-one-free residual with a sharp dimension bound; the literal maximal two-dimensional residual is excluded. Two-terminal substresses satisfy an exact interface-flux law, and a five-internal-vertex rank-four block has a Pfaffian cofactor carrier. Finally, an analytic reduction followed by exact symbolic enumeration excludes every one-external completion of a specified one-silent five-cycle residual, for all orientation words. These results isolate the remaining degeneracy but do not solve the problem for arbitrary n.

Let $s(n)$ denote the number of ones in the binary expansion of an integer $n\in\mathbb{N}$, and let $\mu_t$ be the probability measure on $\mathbb{Z}$ defined by the asymptotic densities of the level sets of the function $\mathbb{N}\ni n\mapsto s(n+t)-s(n)\in\mathbb{Z}$. Let $P_t$ be the family of finitely supported measures defined by the convolution $\mu_t=\mu_1*P_t$. Recently, Tarlowski (2026) has shown that the family $P_t$ may be represented as a recursively grown binary tree $T_t$, and that the Cusick's conjecture - $\mu_t(\mathbb{N})>\frac12$, $t\in\mathbb{N}$, - follows from the asymmetry property of the family $T_t$, which was posed there as an open problem. Next, Cheng (2026) has provided the combinatorial description of the family $T_t$ in the language of principal subsequence ideals, and proved both conjectures. Both of these problems are directly related to the problem of determining the zeros of the function $\mathbb{N}\ni t \mapsto P_t(\mathbb{N})-\frac12\in[0,\tfrac12]$, a problem left open by Cheng (2026) as a saturation problem, and previously analyzed only numerically. In this paper we solve this problem completely. Writing an odd integer $t\ge3$ as $t=(1\,w\,1)_2$ with $w\in\{0,1\}^{\star}$, we show that $P_t(\mathbb{N})=\frac12$ if and only if $w$ is saturated in the following sense: in the block decomposition $w=1^{a_0}\,0\,1^{a_1}\,0\cdots0\,1^{a_k}$ with exactly $k$ zeros, every block of "1" satisfies $a_i\ge k$. Additionally, we show that the lower bound for $P_t(\mathbb{N})$ established by Cheng for $0$-initial words holds true for all non-saturated words.

We say an $(n,n)$-function $F \colon \mathbb{F}_2^n \to \mathbb{F}_2^n$ is a crooked function if for any nonzero $a \in \mathbb{F}_2^n$, the image of $D_aF(x)=F(x)+F(x+a)$ is an affine hyperplane. The only known examples of crooked functions are all quadratic almost perfect nonlinear (APN), or equivalently, for every known crooked function, $D_aF$ is affine for all $a \in \mathbb{F}_2^n$. The ortho-derivative $\pi_F \colon\mathbb{F}_2^n \to \mathbb{F}_2^n$ of a crooked function $F$ is the function such that $\pi_F(0)=0$, and for any nonzero $a$, the set $\{0,\pi_F(a)\}^\perp$ is the underlying vector space of $\mathrm{Im}(D_aF)$. We prove that for $n \geq 4$ and a crooked function $F$, if $k$ is a non-negative integer such that $F$ has $2^k-1$ quadratic component functions, $\pi_F$ has at least $2^n-2^{n-k}$ component functions of algebraic degree $n-2$. In particular, we resolve Gorodilova's conjecture that every component function of $\pi_F$ has algebraic degree $n-2$ when $F$ is quadratic APN. As a second main result, for $n \geq 4$, we associate to a crooked function $F$ a quadratic function $\varepsilon_F \colon \mathbb{F}_2^n \to \mathbb{F}_2^n$ that satisfies a strong geometric-combinatorial condition regarding the sums of $F$ over $2$-dimensional linear subspaces. As a corollary to both of our main results, we prove that for any even $n \geq 4$, any quadratic APN $(n,n)$-function has at least $n$ semi-bent components. Furthermore, we obtain a congruence result on a problem on $m$-sequences introduced by Johansen, Helleseth, and Kholosha, and we determine the exact algebraic degrees of some Boolean functions associated to the bent and near-bent components of particular classes of plateaued vectorial functions.

A graph G with q edges and p vertices is edge-graceful if some bijection f from E(G) onto {1,...,q} makes the induced vertex sums f^+(v), the sum of f(e) over the edges e incident to v, distinct modulo p. Lee conjectured in 1989 that every tree of odd order is edge-graceful; the broadest general result we have located, due in equivalent form to Kaplan, Lev and Roditty, covers trees of odd order with at most one vertex of degree two. We prove that every tree of odd order with at most two vertices of degree two is edge-graceful. The proof combines zero-sum block partitions of Z_n with perfect and hooked Langford sequences; the residual case analysis is verified symbolically for all odd n <= 5001 and holds uniformly beyond, and the construction was executed and independently re-checked on all 2,245,070 trees of odd order at most 25 with exactly two vertices of degree two. Since an edge-graceful graph is antimagic, the theorem also enlarges the family of trees known to be antimagic.

This comment gives dimension-independent analytic proofs of the local inequalities arising in the odd- and even-dimensional constructions of higher-dimensional partition charge functions. The prior works established these inequalities by exhaustive computation in low dimensions and tested them numerically in selected higher dimensions.

A \(\mathbb{T}\)-gain digraph is a directed graph with complex unit gains on its arcs, allowing for no restrictions on oppositely directed arcs. This framework unifies various graph types, such as signed graphs, mixed graphs, complex unit gain graphs, digraphs, and signed digraphs. The gain adjacency, Laplacian, and signless Laplacian matrices are generally non-Hermitian with complex spectra. We develop the spectral theory of these matrices, extending classical results from signed digraphs and complex unit-gain graphs. For the gain adjacency matrix, we establish determinant and characteristic polynomial formulas, characterize cycle balance through switching equivalence and cospectrality with the underlying digraph. We further bound the spectral radius in terms of the underlying digraph and its maximum out-degree, with equality characterized by $\mu$-balance. As a consequence, we determine the spectra of $\mathbb{T}$-gain unicyclic digraphs. Moreover, we characterize cycle balance and antibalance for the Laplacian and signless Laplacian matrices, respectively, through the presence of a zero eigenvalue.

For integers $k,g \ge 3$ let $n_g(k)$ denote the minimum order of a graph with chromatic number $k$ and girth at least $g$. Exoo and Goedgebeur (DMTCS 2019) proved $26 \le n_6(4) \le 66$; their 66-vertex witness has remained the smallest known 4-chromatic graph of girth 6. We improve both bounds to $29 \le n_6(4) \le 64$. The upper bound is witnessed by an explicit 4-chromatic graph of girth 6 on 64 vertices with 152 edges; it is vertex- and edge-critical, and its automorphism group is cyclic of order 8 and acts semiregularly. The lower bound is an exhaustive isomorph-free computation in the SAT modulo symmetries framework with co-certificate learning, driven by the Liu-Postle edge-density bound for 4-critical graphs of girth five; it re-derives $n_6(4) \ge 26$ by a disjoint method and is validated on the known values $n_4(4)=11$ and $n_5(4)=21$. We complement the bounds with structural obstructions: no smaller witness arises from either known witness by local modifications; no 4-chromatic Cayley graph of girth 6 exists on 54-63 vertices (for orders 59 and 61 no vertex-transitive witness exists at all); and no witness on at most 63 vertices admits a semiregular automorphism group with two or three vertex orbits, for any finite group. Since every known witness of an $n_g(4)$ record with $g \ge 6$ is a lift of a small base graph along a semiregular action, these results close the most symmetric part of that regime below 64 vertices. All properties of the new graph are verified by independent programs and formally certified in the Lean 4 proof assistant: the non-3-colourability is established inside Lean by a formally verified checker that re-validates a 219,532-node refutation certificate, with a machine-checked soundness theorem.

Let $q=p^k$, and let $A_1,\ldots,A_{r-1}$ be invertible $n\times n$ matrices over ${\mathbb F}_q$. We prove that, if $k\ge r$, there is a vector $x$ for which \[ x,A_1x,\ldots,A_{r-1}x \] are all nowhere zero. For $r=2$ this recovers the theorem of Alon and Tarsi over nonprime finite fields. The proof tracks one monomial in the product of the coordinate forms. Frobenius powers keep every exponent below $p^r$, and finite-field polynomial nonvanishing supplies the required vector. The same method treats rectangular matrices with independent rows and prescribed forbidden values. The method also gives an extension-degree criterion for representable matroids and clarifies an unpublished prime-field conjecture of M. J. Moghaddamzadeh. Projective-geometric examples explain why the analogous field-size statement fails over proper extensions and, translated back to matrices, give lower bounds for the large-field problem.

A subset of the $d$-dimensional lattice cube $[n]^d$ is sum-free if it contains no solution to the equation $x+y=z$. We study the total number of such subsets. For $d=1$, Cameron and Erdős conjectured that the number of sum-free subsets of $[n]$ is $O(2^{n/2})$, and this was proved independently by Green and Sapozhenko. A recent work by Ghosal solved the case $d = 2$. In this paper, we consider all remaining dimensions and prove that for every fixed integer $d \geqslant 3$, the number of sum-free subsets of $[n]^d$ is $2^{M([n]^d) + O_d(n^{d-1})}$, where $M([n]^d)$ is the maximum possible size of a sum-free subset of $[n]^d$. This verifies a conjecture of Elsholtz and Rackham. Our proof combines the dual weights constructed by Keevash and Lim in their work for $M([n]^d)$, a one-dimensional counting estimate due to Ghosal, a bipartite swapping lemma of Zhao, and a strong fractional entropy inequality of Madiman and Tetali, and it avoids the use of the container lemma or deriving a stability theorem first.

We study extremal questions on the average length and the number of subpaths in a graph. In particular, we prove the questions of Jamison (from $1983, 1984$) for the analogous concept of the average length of a subpath. Among other results, we prove that $K_n$ maximizes the average path length.

The boxicity of a graph $G$, denoted by $box(G)$, is the minimum integer $d\geq 0$ such that $G$ is the intersection graph of axis-parallel boxes in $\mathbb{R}^d$. The class of zero divisor graphs introduced by Beck (1988) is a popular class of graphs and has been studied extensively by several researchers. Suppose $Z(R)$ is the set of zero divisors of a ring $R$. The zero divisor graph $\Gamma(R)$ for a ring $R $ is defined as the graph with the vertex set $V(\Gamma(R))=Z(R)$ and $E(\Gamma(R))=\{\{x,y\}\colon x,y\in Z(R)\text{ with }x\neq y\text{ and }x y=0\}$. One can define an equivalence relation $\sim$ on $V(\Gamma(R))$ such that for vertices $x$ and $y$, one has $x\sim y$ if and only if $x$ and $y$ have the same annihilator, i.e., $Ann(x)=Ann(y)$. The compressed zero divisor graph $\Gamma_E(R)$ for a ring $R$ is the simple graph obtained from $\Gamma(R)$ by retaining exactly one vertex from each equivalence class induced by $\sim$. In this paper, we completely answer two open questions posed in Discrete Applied Mathematics 391 (2026), pp. 127-136. Let $N=\prod_{i=1}^a p_i^{n_i}$ be the prime factorization of a positive integer $N$ and let $\mathbb{Z}_N$ be the ring of integers modulo $N$. We determine the exact boxicity of the compressed zero divisor graph $\Gamma_E(\mathbb{Z}_N)$. We show that when $a\geq 2$, $box(\Gamma_E(\mathbb{Z}_N))= a-1$ if and only if one of the following is true: $(i)$ $a\geq 2$ and $N$ is the product of two coprime integers $x$ and $y$ such that $x$ is a square-free integer and $y$ is the cube of a prime number; $(ii)$ $a\geq 3$ and $N$ is square-free; $(iii)$ $a\geq 2$, $N$ is cube-free, not square-free, and contains at least one prime divisor $p_i$ such that $n_i=1$. If $a=2$ and $n_1=n_2=1$, then $\Gamma_{E}(\mathbb{Z}_N)$ is a clique, and so, $box(\Gamma_{E}(\mathbb{Z}_N))=0$. In all other cases, $box(\Gamma_{E}(\mathbb{Z}_N))=a$.

We prove Dennin's conjecture (Conjecture 8.9 of arXiv:2506.21052) that his variant of dual RSK correspondence is symmetric when restricted to biGrassmannian permutations. For a binary matrix $A$, let $A^\dagger$ denote its transpose-complement, and let $\operatorname{ins}(A)$ and $\operatorname{rec}(A)$ denote its insertion and recording tableaux. We prove that $\operatorname{ins}(A^\dagger) = \overline{\operatorname{rec}(A)}$, where the bar denotes the natural complement of the recording tableau. Our proof uses rectification of super pipe dreams and a downward induction on suffixes of $A$.