Several graph shapes can now be tied to exact values of a quantity from algebra, while a single inequality covers the wider universe of graphs. An arXiv preprint reports that the diagonal F-threshold associated with a graph and its binomial edge ideal equals the graph's number of vertices for cycles, graphs with a perfect matching and graphs with a 2-factor. For bipartite graphs, a different exact rule uses the size of the largest independent set. The study also gives a lower and upper bound for arbitrary graphs.
From graph to algebra
At the center of the paper is a quantity called the diagonal F-threshold. The study attaches it to a finite simple graph and its binomial edge ideal, an algebraic object generated by a two-term difference for each graph edge. For an edge linking vertices i and j, that difference pairs the x-variable at one endpoint with the y-variable at the other, then subtracts the reversed pairing. The question is how the resulting threshold reflects graph combinatorics.
To follow the quantity through the algebra, the proofs use reduced Gröbner bases for the combined object written as (m[k], JG). They separate the reduced basis into a monomial part M and a binomial part B. This division keeps the two types of polynomial terms distinct as the argument proceeds.
A range, then several exact answers
For arbitrary graphs in the stated setting, the threshold is at least n, where n is the number of vertices. The paper's combined bound places it no higher than twice n minus b(G). Here b(G) is the maximum number of vertices covered by a clique matching. This gives a common frame for the more specific results.
Cycles meet the lower edge of that range. For a cycle on n vertices, the diagonal F-threshold equals n. The same equality holds for every graph on n vertices with a perfect matching. A graph with a 2-factor also has threshold n. Several different graph conditions therefore lead to the same exact value.
Bipartite graphs follow another exact rule. Their threshold equals twice d, where d is the size of a maximum independent set. In ordinary terms, d counts the vertices in the largest set with no edge between two of its members. The result ties the algebraic quantity to a specific measure of graph structure.
Where graph structure fixes the value
Block graphs sit at the upper side of the general picture. For this class, the threshold equals twice the number of vertices minus b(G), so the expression used as a general ceiling is exact. The same expression applies to a cycle with at least one whisker.
The whisker result also comes with a step-by-step relation. If e is a whisker joining u and v, removing e relates the threshold of the original graph to the threshold of the graph with e removed, with an additive term of 2. The manuscript thus turns a local graph operation into a precise recurrence for the algebraic quantity.
A flexible tool for other graphs
The paper also develops a device called a CI-matching. It combines an independent set with disjoint cliques subject to a stated nonadjacency condition. If the independent-set part has size aP and the clique part covers bP vertices, the threshold is at least twice aP plus bP and at most twice n minus bP. These two numbers turn a chosen piece of graph structure into a pair of bounds.
An accompanying Algorithm 4.9 takes a CI-matching as input and returns a reduced CI-matching. That gives the general-bound argument a way to simplify the combinatorial structure before applying it. Taken together, the results show how matchings, independent sets, clique matchings and cycle-based structures can determine the threshold exactly or place it within a stated range.
The supplied record identifies the manuscript as arXiv:2608.28083v1, dated 28 August 2026. It is a preprint, and its conclusions are formal statements about finite simple graphs and their binomial edge ideals.
Paper data and sources
Original title: Diagonal F-threshold of binomial edge ideals
Authors: Giancarlo Rinaldo, Francesco Romeo
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-28
DOI: Not available
Original paper · Full text