Papers

Core stability gives approval-based committee elections a strong form of coalitional proportionality, but deterministic existence is not known for an arbitrary number of seats. We prove that every finite election with nine seats has a deterministic Hare-quota core committee. Starting from an eight-seat committee that is both a global Proportional Approval Voting (PAV) maximizer and core stable, we suppose that all one-candidate extensions are blocked and extract an inclusion-minimal closed response system. Singleton responses are eliminated by exact equality rigidity. For the remaining responses, rational Farkas certificates bound every nonpositive PAV add-marginal drift below by $-n/189$ and force every successor drift above $n/126$. The uniform response chain is irreducible, so stationarity makes these bounds incompatible. The computer-assisted component comprises an exact pointwise check over 7,356 voter types, 36 one-blocker cells, and a symmetry-complete family of 19 two-blocker motifs. Exact certificate archives and standard-library verifiers support these checks. The theorem settles the nine-seat case but does not decide deterministic core existence for arbitrary committee size.

Chung, Graham, and Spiro introduced slow Fibonacci walks and used them to partition the integers $n\ge2$ into two sequences, the down-integers and the up-integers. They studied the local spacing of these two sequences and conjectured that their $\ell$-step gap sets agree for every $\ell\ge1$. We show that the conjecture fails at $\ell=4$ by proving \[ 9\in U_4\setminus D_4 . \]

The enumeration of pattern-avoiding permutations has been a popular area of study over the past several decades, but comparatively little attention has been given to the topic of pattern-avoiding involutions. In this paper, we derive the algebraic generating functions of two Wilf-equivalence classes of involutions avoiding a single pattern of length $4$, $\operatorname{Av^I}(2431)$ and $\operatorname{Av^I}(3421)$. We then adapt the Mosaic method, a fast counting algorithm for permutations, to count involutions and apply it to substantially extend the known initial terms of the counting sequences for the remaining two Wilf-equivalence classes avoiding a pattern of length $4$, $\operatorname{Av^I}(1324)$ and $\operatorname{Av^I}(4231)$. Based on these extended sequences, we empirically analyze the asymptotic behavior of the counting sequences of these two classes.

Given a finite family $\mathcal F$ of forbidden $r$-graphs, the Turán problem asks for the maximum asymptotic edge density of $\mathcal F$-free $r$-graphs and the structure of near-extremal examples. We show that both questions can encode arbitrary computation. Fix a universal Turing machine $\mathsf U$. For every sufficiently large fixed $r$, there is a rational $\tau_r\in(0,1)$ such that, from each binary word $\beta$, one can construct a finite family $\mathcal F_{r,\beta}$ with $\pi(\mathcal F_{r,\beta})=\tau_r$ if $\mathsf U$ does not halt on $\beta$, and $\pi(\mathcal F_{r,\beta})>\tau_r$ otherwise. The same dichotomy governs extremal structure. We construct finite families $\mathcal G_{r,\beta}$ such that nonhalting gives a unique extremal limit and Erdős–Simonovits stability, whereas halting gives two nonempty compact extremal phases separated by the sign of a fixed continuous statistic. Hence uniqueness and connectedness of the extremal space, symmetry breaking, two-phase behavior, and stability are all undecidable. The reductions are effective and verifiable in ZFC by finite certificates. Consequently, for every consistent computably axiomatized extension of ZFC and every sufficiently large fixed $r$, there is a finite family $\mathcal F$ for which the true equality $\pi(\mathcal F)=\tau_r$ is neither provable nor refutable; analogous independence holds for the five structural properties above. We also obtain effective approximation, classify exact comparison complexity, and show that the smallest improvement witnesses have Busy-Beaver growth, with no uniform computable positive lower bound on the density gain.

Let \(S\) be a smooth projective complex surface with irregularity \(q=h^{1,0}(S)\) and geometric genus \(g=h^{2,0}(S)\), and let \(S^{[n]}\) denote its Hilbert scheme of \(n\) points. We prove that, for every \(n\ge0\), the sequence \[ \left(h^{p,0}\bigl(S^{[n]}\bigr)\right)_{p=0}^{2n} \] is log-concave if and only if \(g\le\binom{q+1}{2}\). Moreover, log-concavity of all these sequences is already equivalent to log-concavity of the sequence for \(n=2\). We also prove that these sequences are unimodal for every \(n\ge0\) if and only if \(q\ge1\) or \(g=0\), and that this condition is already detected by the sequence for \(n=1\).

We give deterministic FPTASes for two dense counting problems on which the known deterministic algorithms, based on zero-free interpolation, run in quasipolynomial time. For fixed $0<\gamma<1/2$ and $0<\theta\leq1$, the first approximates $\mathrm{haf}(A)$ for a symmetric matrix $A$ when its support graph $G$ has minimum degree at least $(1/2+\gamma)n$ and its nonzero entries lie in $[\theta,1]$. It also approximates permanents under the analogous bipartite condition, including full-support matrices in $[\theta,1]$. For fixed $\beta>0$ and $0<\kappa\leq1$, the second approximates the zero-field Ising partition function $Z(J)$ for zero-diagonal real symmetric matrices $J$ satisfying $\max_{i,j}|J_{ij}|\leq\beta/n$ and $\lambda_{\max}(J)\leq1-\kappa$. No separate lower-eigenvalue condition is imposed. We further prove $\log\mathrm{haf}(A)=h_A(G)-n/2+O_{\gamma,\theta}(1)$ and $Z(J)=2^n\det(I-J)^{-1/2}(1+O_{\beta,\kappa}(1/n))$. Here $h_A(G)$ is the maximum weighted fractional-matching entropy. For unweighted graphs, the first formula improves the Cuckler–Kahn error from $o(n)$ to $O_\gamma(1)$ on the fixed-margin class and extends it to weights in $[\theta,1]$. Both algorithms use a common Gaussian truncation principle. Each problem becomes an integral of a product of a fixed entire function over Gaussian coordinates, with possibly indefinite moment matrix entries of order $1/n$. Cancelling the linear term and exactly resumming the quadratic term leaves a coordinate remainder vanishing to order at least three. Complex dilation handles small supports. For large supports, we bound the recombined tail by a large-deviation rate that beats the entropy of the subsets. The truncation error is at most $(CR/n)^{R/2}+e^{-cn}$. This faster-than-geometric decay permits $R\log(en/R)=O(\log n+\log(1/\epsilon))$ and hence polynomial enumeration.

Let $G$ be a graph of order $n$, and let $s^+(G)$ and $s^-(G)$ denote the sums of the squares of the positive and negative adjacency eigenvalues of $G$, respectively. Recently, Liu, Tang, and Zhang proved the conjecture of Elphick, Farber, Goldberg, and Wocjan that every connected graph $G$ of order $n$ satisfies $ \min\{s^+(G), s^-(G)\} \ge n-1. $ For positive square energy, we strengthen this result by showing that every $2$-connected graph $G$ of order $n$ which is not a cycle satisfies $s^+(G)\ge n$. The formally analogous assertion for $s^-$ is false: the complete graph $K_n$ satisfies $s^-(K_n)=n-1$. We prove a natural counterpart in the triangle-free class: every triangle-free $2$-connected noncycle $G$ satisfies $ \min\{s^+(G),s^-(G)\}>n. $ More generally, it is enough that some maximum-degree vertex of $G$ belongs to no triangle. Together with the exact square energies of cycles, this characterizes the triangle-free $2$-connected graphs for which $s^-(G)\ge n$; the only exceptions are the cycles $C_{4k+3}$ with $k\geq1$.

We investigate limits of semigroups of stochastic matrices defined by their invariant distribution. Given probability vectors $\gamma(\beta)$ depending on a parameter $\beta$, we introduce a notion of convergence as $\beta\to\infty$ for the corresponding semigroups of $\gamma(\beta)$-preserving stochastic matrices and investigate the structure of the resulting limit. In general, the limiting semigroup differs from the semigroup preserving the limiting distribution, showing that these two operations do not commute. We develop a general framework for such limiting semigroups and study in detail the case in which the invariant distributions are Gibbs vectors at the inverse temperature $\beta$. We show that the limiting semigroup consists of block-upper-triangular stochastic matrices subject to additional substochasticity constraints. We characterise and enumerate their extremal elements and determine the preorder on probability vectors induced by the action of the semigroup. The resulting notion of Block-Triangular majorisation interpolates between ordinary majorisation and upper triangular (aka unordered) majorisation. We show that it is completely characterised by a finite family of monotones and analyse the corresponding behaviour of Rényi $\alpha$-entropies as $\beta\to\infty$.

We prove a necessary condition conjecture ([27, Conjecture B]) for the maximal singularity of the Hilbert scheme of points in 3D for a large class of degrees, which in particular implies the 1978 Briançon-Iarrobino Conjecture for a tetrahedral degree, and vastly generalises the result in [19]. The novelty lies in introducing a new upper bound on the dimensions of the tangent spaces of the claimed non-maximally singular ideals, constructing canonical ideals that satisfy the claimed maximal singularity condition, providing a lower bound on the dimension of their tangent spaces, and finally comparing the two cases.

For a numerical semigroup $S$ with embedding dimension four, we study the relationship between its type $t(S)$ and the cardinality of its minimal presentations $\eta(S)$. Using an approach based on the geometry of the Apéry set, we prove that $4t(S) + 5 \geq \eta(S) \geq t(S)-11$. This resolves a problem of Moscariello and Sammartano asking whether $t(S)$ is bounded by a function of $\eta(S)$, and improves the previously known bound $9t(S) + 4 \geq \eta(S)$ due to Bresinsky.

The theory of combinatorial Hopf algebras (CHA) is a powerful framework for studying algebraic invariants of combinatorial objects. For instance, Stanley's chromatic symmetric function and the chromatic polynomial arise naturally from the CHA of graphs. In this paper, we define a CHA of signed graphs in order to study, in the same spirit, invariants of signed graphs such as the signed chromatic polynomial. The key ingredient of our construction is a well-chosen character, from which the signed chromatic invariants are obtained. Via the antipode, we obtain new proofs of combinatorial reciprocity results for these invariants. Moreover, by deforming the character with an additional parameter, we incorporate bivariate invariants into this framework, both for classical and signed graphs. In the classical case, this technique recovers the Tutte polynomial.

We prove that the set of bounded ratios $\BR(X)$ on a semialgebraic set $X\subset\R^n_{>0}$ is the convex cone of linear forms that are nonnegative on the tropicalization $\trop(X)$. In particular, it is a rational polyhedral convex cone. For $X$ the set of Lorentzian polynomials with fixed M-convex support, it is the dual to the set of M-convex functions. We record an explicit counterexample to a conjecture of Huang–Huh–Soskin–Wang on the bounded ratios on Lorentzian polynomials. The bounded ratio in the counterexample corresponds to the non-hypermetric clique-web facet $\mathrm{CW}^1_7(1,1,1,1,1,-1,-1)$ of the cut cone on seven vertices.

Two permutations $\sigma,\tau\in S_n$ are called disjoint if the composition $\sigma\tau^{-1}$ has no fixed point. If a family $\mathcal F\subseteq S_n$ contains no $s$ pairwise disjoint permutations, then a simple averaging argument gives $|\mathcal F|\leq(s-1)(n-1)!$. Inozemtsev, Kolupaev and Kupavskii characterized the equality cases in the range $s\leq n/(2^{17}\log n).$ We characterize all equality cases throughout the range $2\le s\le n$: equality holds if and only if $\mathcal F$ is a union of $(s-1)$ pairwise disjoint $1$-cosets. We also prove the linear statement underlying this classification: a real-valued function on $S_n$ has constant sum on every one-factorization if and only if it lies in the span of the indicators of the $1$-cosets. The proof is combinatorial and applies to every order, with a few small orders handled separately.

We study the operators obtained by inserting copies of a new largest letter into multiset permutations. Let $G_r$ denote the operator which inserts $r$ copies of a new largest letter. After the change of variables $\delta=y-x$, $u=x/y$, and $E=u\partial_u$, we find that $$G_r=\frac{\delta^r}{r!}E(E+1)\cdots(E+r-1).$$ Its generating series acts by a rational substitution, which yields the composition law. Our main result gives a common symmetric-function explanation for the ordinary and major-index operators. For $N\geq 0$, define $\Phi_N(F_{N,S})=x^{|S|+1}y^{N-|S|}$. We prove that multiplication by the complete homogeneous symmetric function $h_r$ becomes the ordinary insertion operator: $\Phi_{N+r}(h_r f)=G_r\Phi_N(f)$, where $f\in\mathrm{QSym}_N$. There is a parallel specialization for the major index. A reverse finite principal specialization sends multiplication by $h_r$ to an operator $Q_r$, which is a polynomial in the $q$-shift $\Theta_qf(t)=f(qt)$. Thus the ordinary and major-index operators arise from the same multiplication operator $f\mapsto h_r f$. Since the functions $h_r$ freely generate the ring of symmetric functions, the assignment $h_r\mapsto G_r$ extends to an algebra homomorphism. We determine the kernel of this homomorphism and the image of every homogeneous component. The images of Schur functions satisfy the Littlewood–Richardson multiplication identities, and the one-row case gives an Eulerian form of the Pieri rule.

We prove a Haglund–Haiman–Loehr type combinatorial formula for the torus fixed point classes $I_{\mu,w}$ in the equivariant $K$-theory $K_{\mathbb{C}^{*}\times\mathbb{C}^{*}}(\operatorname{PFH}_{n,n-k})$ of parabolic flag Hilbert schemes. Under the identification of Bechtloff Weising and Orr, our result gives an HHL type formula for modified partially symmetric Macdonald functions in terms of weighted partial Dyck paths. When $w=\emptyset$, it specializes to the classical HHL formula. The proof relies essentially on the Carlsson–Gorsky–Mellit action of the Carlsson–Mellit algebra $\mathbb{A}_{q,t}$.

The cohomology ring of the complement of a complex hyperplane arrangement is given by its Orlik–Solomon algebra. It is known that the defining ideal of the Orlik–Solomon algebra has a quadratic Gröbner basis in the standard presentation if and only if the intersection lattice is supersolvable; such algebras are automatically Koszul. In 1997, Shelton and Yuzvinsky posed the question as to whether all Koszul Orlik–Solomon algebras arise from supersolvable arrangements. We answer this question negatively using three related constructions that produce non-supersolvable arrangements whose Orlik–Solomon algebras are Koszul. Moreover, these arrangements may be chosen to be irreducible, realizable over $\mathbb{Q}$, and of any rank $\geq 3$. Our constructions rely on a result of Falk and Proudfoot which we strengthen and generalize. In two of the three cases, we show non-supersolvability using a corrected form of a result of Ziegler regarding supersolvability of parallel connections. We also construct Koszul Orlik–Terao algebras coming from non-supersolvable arrangements.

Graded Möbius algebras were a key tool in the proof of the Dowling-Wilson Top Heavy Conjecture. They are commutative algebras whose Hilbert functions recover the Whitney numbers of the second kind, i.e. the number of flats of a given rank. The graded Betti numbers of the defining ideal of a graded Möbius algebra refine the Hilbert function and describe its minimal free resolution. In this paper we derive precise formulas for the graded Betti numbers of the defining ideals of graded Möbius algebra for any uniform matroid. We also study when the graded Möbius algebra of an arbitrary matroid is linearly presented.

An edge-colored graph is rainbow if all of its edges receive distinct colors. For a fixed graph $H$, an edge-colored graph $F$ is called weakly $H$-rainbow saturated if there exists an ordering $e_1,e_2,\ldots,e_{|E(\bar{F})|}$ of $E(\bar{F})$ such that, for any edge coloring $c$ of $E(\bar{F})$ with $c(e_i)\neq c(e_j)$, there is always a rainbow copy of $H$ that contains $e_i$ in $F+\{e_1,e_2,\ldots,e_i\}$. The weak rainbow saturation number $\operatorname{rwsat}(n,H)$ is the minimum number of edges in a weakly $H$-rainbow saturated graph on $n$ vertices. Li, Ma, and Xie [JGT, 2025] showed that $\lim_{n\to\infty} \frac{\operatorname{rwsat}(n,H)}{n}$ exists for every nonempty graph $H$. Paths and stars attain, respectively, the minimum and maximum ordinary weak saturation numbers among all trees of the same order. We determine their weak rainbow saturation numbers exactly. For all $\ell>30$, we show that $$ \ell+1=\s(n,P_\ell)< \s(n,S_\ell)=\binom{\ell}{2}-1$$ where $P_\ell$ and $S_\ell$ denote the path and star on $\ell$ vertices, respectively. Thus, their dependence on $\ell$ is linear for paths and quadratic for stars. We then focus on cycles. Li, Ma, and Xie asked whether $\operatorname{rwsat}(n,C_\ell)$ has leading term $\frac32n$ for every $\ell\ge4$. We answer this question negatively by giving an explicit construction showing that, for every $\ell\ge4$ and all sufficiently large $n$, $$\s(n,C_\ell)< \frac{\ell}{\ell-1}n+c_\ell,$$ where $c_\ell$ depends only on $\ell$. Since $\frac{\ell}{\ell-1}<\frac32$, this strictly improves the proposed leading coefficient for every cycle $C_\ell$ with $\ell\ge4$.

A labeling of a connected graph $G$ on $n$ vertices is a bijection $c:V(G)\to\{1,\dots,n\}$; writing $c(u,v)=|c(u)-c(v)|$, a vertex $u$ is list-distance consistent if $d(u,v)<d(u,w)$ implies $c(u,v)\le c(u,w)$ for all $v,w$. The maximum number of such vertices over all labelings is the list-distance consistency ldc$(G)$, introduced by Casselgren and Henricsson. We prove that in a tree, the consistent vertices of any labeling lie on a single path, along which the labels form a block of consecutive integers in increasing order (with respect to a suitable orientation of the path), no vertex off the path receiving a label from that block. We deduce that ldc equals $3$ for every complete $k$-ary tree except the binary tree of height two, and we determine ldc for all spiders.

For planar graphs, it is known that their treewidth is bounded by $O(\sqrt{n})$, where $n$ is the number of vertices of the graph. A related invariant to treewidth, is the scramble number of graphs. Recently, Connor et. al proved that planar graphs of bounded maximal degree have scramble number bounded by $O(\sqrt{n})$. An open question is whether the scramble number of any planar graph follows this same bound. We give a definitive answer with an explicit bound for a subset of planar graphs, the simple outerplanar graphs and the simple near outerplanar graphs.

Granville and Ono proved that there is an $e$-core partition of $n$ for every $n\in\mathbb{N}$ if and only if $e\geq 4$, which translates to a statement about the existence of defect $0$ blocks for symmetric groups in positive characteristic and defect $0$ unipotent blocks of finite general linear groups in positive, non-defining characteristic. Motivated by analogous applications to the block theory of finite classical groups, imprimitive spetses, and cyclotomic Hecke algebras, we prove similar positivity statements about different variants of $e$-cores for charged multipartitions.

In their work on sphere packing and the modular bootstrap, Afkhami-Jeddi, Cohn, Hartman, de Laat, and Tajdini conjectured the exact high-dimensional exponent of the Cohn-Elkies sphere-packing linear program. OpenAI's Chapter 1 subsequently proved their conjecture by establishing that both Fourier sign-uncertainty radii are $(1/\pi+o(1))\sqrt d$. We prove the binary coding analogue: \[ R_D\!\left(\frac12-\frac1\pi\right)=\frac12. \] We also formulate the two Krawtchouk sign-uncertainty problems and determine both of their asymptotics. If $A^{\mathrm K}_{\pm}(n)$ denotes the smallest radius $r$ for which a nonzero Krawtchouk $(\pm1)$-eigenfunction $f$ exists with $f(0) = 0$ and $f(x) \ge 0$ for all $|x| \ge r$, then \[ \frac{A^{\mathrm K}_{\pm}(n)}n\longrightarrow \frac12-\frac1\pi. \] The lower bound proves a mass-concentration principle similar to OpenAI's Chapter 1 for Hamming space. The upper bound, on the other hand, follows the approach of the spherical-code construction in OpenAI's Chapter 2. Gay, Jeronimo, and Liu formulated a hierarchy for binary codes analogous to the spherical-code construction and improved the best known binary coding rate bounds by evaluating the first level of the corresponding hierarchy. We prove this hierarchy bounds the Delsarte program and give a construction at arbitrarily deep levels of the hierarchy, attaining the upper bound in the limit. The construction uses an $N$-qubit generalization of the pure-state channel of Alrabiah and Guruswami.

For every $\beta>0$, we establish multi-time soft-edge moment convergence for the Jack–Plancherel process, a discrete $\beta$-analogue of Dyson Brownian motion. The limiting moments admit an absolutely convergent expansion in terms of nonnegative Brownian bridges decorated by pairs of equal and opposite jumps. At equal times, we identify this limit with the joint Laplace statistics of the Airy$_\beta$ process for $\beta\geq1$. The same Brownian expansion yields an asymptotic $\beta$-topological expansion of the marginal $b$-conjecture and, at $\beta=2$, an explicit nonnegative formula for the Witten–Kontsevich intersection numbers.

For a graph $G$ without isolated vertices, $\gamma(G)\le\gamma_t(G)\le 2\gamma(G)$. While graphs attaining $\gamma(G)=\gamma_t(G)$ have been studied extensively, a complete structural description in the smallest nontrivial case $\gamma(G)=2$ has remained open. We resolve this case according to girth. When $g(G)\ne 3$, we show $\gamma_t(G)=2$ forces $G$ bipartite, give an exact degree-sum criterion for this equality, and show $\gamma_t(G)\in\{2,4\}$ under the additional hypothesis $\delta(G)\ge 2$. When $g(G)=3$, we use Golumbic's vertex-multiplication operation together with known classifications of graphs of rank $2$ through $5$ to completely list the families satisfying $\gamma(G)=\gamma_t(G)=2$. As an application, we show that every graph in the extremal family of diameter-two, dominating-vertex-free graphs identified by Erdős and Rényi and classified by Henning and Southey satisfies $\gamma_t(G)\in\{3,6\}$, so $\gamma=\gamma_t=2$ never occurs there. Together these results give a full structural dictionary translating $\gamma_t(G)=2$ into concrete, checkable graph-theoretic properties.

We report on our ongoing project to develop a computational pipeline, AutoGraphForge, for an automated graph-theoretic conjecturing-refuting-formalizing-proving system. Conjecture generation is counterexample-guided and runs in rounds: a Graffiti3 generator proposes conjectures over a small, evolving snapshot table $T$ (initially a few hundred graphs with their computed invariants) that grows only by counterexamples to its own conjectures. A novelty filter of $559$ classical and folklore relations, closed under transitive composition and linear identity substitution, decides via a linear program whether a candidate is already implied by known results. Surviving candidates are tested against a dataset of about $348,000$ graphs, unioning the complete House of Graphs invariant export, the exhaustive census of all connected graphs on at most nine vertices, several extremal families (strongly regular, minimal Ramsey, Cayley, cages, barbells, lollipops, spiders), and random models. Counterexample-search algorithms then attack the remainder. Run for several rounds on an HPC cluster, the loop yields $6,522$ conjectures that survived the refutation dataset, the novelty filter and every active-search run – among them nontrivial relations between the annihilation number and the edge-cover number for bipartite and regular graphs, which we prove by hand. A subsequent formalization and proving stage deterministically translates each surviving conjecture into a Lean 4 statement skeleton; every candidate proof is kernel-verified against a pinned mathlib4 and our custom invariant preamble. This stage integrates two neural provers – DeepSeek-Prover-V2-671B (served with vLLM) and the Lean-specialised OProver-32B – behind the independent kernel check. It is implemented end-to-end and passes initial sanity checks, with the full pipeline currently running on the cluster.

For distinct positive integers v_1, ..., v_n let ML(v_1, ..., v_n) be the largest number L such that at some time t every t vi is at distance at least L from the nearest integer; the Lonely Runner Conjecture asserts that ML >= 1/(n+1). Write ML = p/q in lowest terms. Kravitz conjectured that whenever ML < 1/n one has q = np + 1; Fan and Sun found counterexamples for n = 4, conjectured that q = np + k with 1 <= k <= n always holds, and observed that in their data for n = 6 only k = 1 and k = 3 occur. We explain this observation. For six speeds we show that all but finitely many tuples with ML < 1/6 satisfy ML = (P-1)/(6P) for an integer P congruent to 1 or 5 modulo 6; in particular k is 1 or 3 and the denominator q is odd. The proof determines the three infinite two-parameter families of tuples on which such values concentrate, computes ML exactly on each family, and describes exactly where k = 3 occurs. An exhaustive search over the 2 x 10^9 sextuples with speeds at most 110 finds no exception. For five speeds the same method, together with Chen's classification of the tuples attaining ML = 1/5, shows that all but finitely many tuples with ML < 1/5 satisfy Kravitz's original conjecture. The computations are exact and the code is provided.

Characterizing graphs uniquely determined by their spectra (DS) is a core open problem in spectral graph theory. While this problem has been extensively investigated for simple undirected graphs, it remains relatively underexplored for oriented graphs. For a simple undirected graph $G$ equipped with an orientation $\sigma$, the corresponding oriented graph $\Sigma=(G,\sigma)$ is the digraph obtained by orienting each edge of $G$ according to $\sigma$. An oriented graph $\Sigma$ is said to be determined by its generalized skew spectrum (DGSS) if every oriented graph sharing the same generalized skew spectrum is isomorphic to $\Sigma$. This paper develops a new sufficient criterion for recognizing DGSS controllable oriented graphs, which applies to a much broader family of graphs than previously known results. Let $S$ be the skew-adjacency matrix of $\Sigma$, $W(\Sigma)=[e,Se,\ldots,S^{n-1}e]$, and $d_n$ the last invariant factor of $W(\Sigma)$. For each odd prime $p$, we define the polynomial $\Phi_p(\Sigma;x)=\gcd(\chi(S;x),\chi(S+J;x))$ over the finite field $\mathbb{F}_p$, which is invariant under generalized skew cospectrality. By analyzing the square-free part of $\Phi_p(\Sigma;x)$ and the associated $p$-main polynomial, we establish a DGSS sufficient condition under the square-free assumption on $d_n$. The proposed criterion allows higher $p$-nullity and recovers the square-free determinant criterion of Qiu, Wang and Wang~(2019) as a special case. We further provide illustrative examples to verify the wider applicability of our new condition and to highlight the role of the compatibility constraints on the irreducible factors of $\Phi_p(\Sigma;x)$.

A graph is fractionally Hamiltonian if it admits a nonnegative edge weighting in $[0,1]$ of total weight equal to its order such that every nontrivial edge cut has weight at least two. Motivated by Chvátal's Toughness Conjecture, Scheinerman and Ullman conjectured that every $2$-tough graph is fractionally Hamiltonian. In this paper, we show that every connected graph on at least three vertices that is not fractionally Hamiltonian has a non-Hamiltonian chordal spanning supergraph. Since adding edges does not decrease toughness, a theorem of Kabela and Kaiser that every $10$-tough chordal graph on at least three vertices is Hamiltonian yields that every $10$-tough graph on at least three vertices is fractionally Hamiltonian. We apply this result to resistance curvature. We prove that every fractionally Hamiltonian graph is resistance positive (RP), and consequently every $10$-tough graph is RP, confirming a conjecture of Devriendt. In the other direction, for every $\varepsilon>0$, we construct a graph that is not resistance nonnegative and has toughness greater than $3/2-\varepsilon$, extending a recent construction of Agrahari, Bibby, Boros, Garcia, Heidercheidt, and Wang.

The adjacent vertex distinguishing (AVD)-total chromatic number $\chi''_{a}(G)$ of a graph $G$ is the least integer $k$ for which $G$ has a proper total coloring $f$ with $k$ colors such that $C_G(u)\neq C_G(v)$ for every edge $uv\in E(G)$, where $C_G(u)=\{f(u)\}\cup\{f(uw):uw\in E(G)\}$. The AVD-total coloring conjecture (AVD-TCC) asserts that $\chi''_{a}(G)\leq \Delta(G)+3$ for every simple graph $G$, where $\Delta(G)$ is the maximum degree of $G$. In this paper, we prove the AVD-TCC for certain classes of graph products, including Cartesian products, lexicographic products, skew products, cover products, comb products, and Indu–Bala products.

Let $\delta\in\mathbb{F}_{2^n}$ satisfy $\operatorname{Tr}_{\mathbb{F}_{2^n}/\mathbb{F}_2}(\delta)=1$. We study the permutation behavior of $$ f(x) = \left(\frac{1}{x^2+x+\delta}\right)^{2^k}+x $$ over $\mathbb{F}_{2^n}$. Helleseth and Zinoviev proved that $f(x)$ is a permutation for $k=0,1$, and remarked that numerical evidence suggests that no other cases occur. In this paper, we confirm their assertion by proving that, for $0\leq k<n$, $f(x)$ is a permutation of $\mathbb{F}_{2^n}$ if and only if $k=0$ or $k=1$.