MétaCan
Menu
← Back to cohort
Record W4417044359 · doi:10.1016/j.jctb.2025.11.010

Reduced bandwidth: A qualitative strengthening of twin-width in minor-closed classes (and beyond)

2025· article· en· W4417044359 on OpenAlexfundno aff
Édouard Bonnet, O‐joung Kwon, David R. Wood

Bibliographic record

VenueJournal of Combinatorial Theory Series B · 2025
Typearticle
Languageen
FieldSocial Sciences
TopicSchool Choice and Performance
Canadian institutionsnot available
FundersAustralian Research CouncilNatural Sciences and Engineering Research Council of CanadaInstitute for Basic ScienceNational Research Foundation of KoreaAgence Nationale de la Recherche
KeywordsClass (philosophy)Algebra over a fieldField (mathematics)Qualitative analysis

Abstract

fetched live from OpenAlex

In a reduction sequence of a graph, vertices are successively identified until the graph has one vertex. At each step, when identifying u and v , each edge incident to exactly one of u and v is coloured red. Bonnet, Kim, Thomassé and Watrigant (2022) [19] defined the twin-width of a graph G to be the minimum integer k such that there is a reduction sequence of G in which every red graph has maximum degree at most k . For any graph parameter f , we define the reduced f of a graph G to be the minimum integer k such that there is a reduction sequence of G in which every red graph has f at most k . Our focus is on graph classes with bounded reduced bandwidth, which implies and is stronger than bounded twin-width (reduced maximum degree). We show that every proper minor-closed class has bounded reduced bandwidth, which is qualitatively stronger than an analogous result of Bonnet et al. for bounded twin-width. In many instances, we also make quantitative improvements. For example, all previous upper bounds on the twin-width of planar graphs were at least 2 1000 . We show that planar graphs have reduced bandwidth at most 466 and twin-width at most 583. Our bounds for graphs of Euler genus γ are O ( γ ) . Lastly, we show that fixed powers of graphs in a proper minor-closed class have bounded reduced bandwidth (irrespective of the degree of the vertices). In particular, we show that map graphs of Euler genus γ have reduced bandwidth O ( γ 4 ) . Lastly, we separate twin-width and reduced bandwidth by showing that any infinite class of expanders excluding a fixed complete bipartite subgraph has unbounded reduced bandwidth, while there are bounded-degree expanders with twin-width at most 6.

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.

How this classification was reachedexpand

Full frame machine prediction

Teacher imitation

Not calibrated prevalence, not ground truth. Human validation pending. The Gemma side is a direct model label for every work in the frame, read from the title-only record. The Codex side is a classifier learned from the 10,348 direct Codex labels and calibrated to design-weighted sample rates; fields without enough sample support carry no Codex call. Candidate is the union of the two sides; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels.

metaresearch head score (Codex)0.002
metaresearch head score (Gemma)0.013
Version: metacan-v3-hybrid-931329e0061cValidation status: machine_predicted_unvalidated
Candidate categoriesnone
Consensus categoriesnone
DomainCandidate signal: none · Consensus signal: none
Study designCandidate signal: Theoretical or conceptual · Consensus signal: Theoretical or conceptual
GenreCandidate signal: Empirical · Consensus signal: Empirical
Teacher disagreement score0.014
Threshold uncertainty score0.048

Distilled classifier scores by category (both heads)

CategoryCodexGemma
Metaresearch0.0020.013
Meta-epidemiology (narrow)0.0000.001
Meta-epidemiology (broad)0.0010.001
Bibliometrics0.0010.001
Science and technology studies0.0020.005
Scholarly communication0.0030.008
Open science0.0020.003
Research integrity0.0010.002
Insufficient payload (model declined to judge)0.0140.001

Machine scores (provisional)

The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.

Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.

Opus teacher head0.018
GPT teacher head0.344
Teacher spread0.326 · how far apart the two teachers sit on this one work
Validation statusscore_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from it

Classification

machine, unvalidated

Machine predicted; a candidate call from one source (direct Gemma or distilled Codex), not a consensus.

The models applied no category: nothing in the taxonomy fit this work.
Study designTheoretical or conceptual
Domainnot available
GenreEmpirical

How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".

Quick stats

Citations0
Published2025
Admission routes1
Has abstractno

Explore more

Same venueJournal of Combinatorial Theory Series B→Same topicSchool Choice and Performance→French-language works237,207→