Pith. sign in

REVIEW 3 major objections 3 minor 40 references

Critical edge sets in vertex-critical graphs

T0 review · 3 major / 3 minor · reviewed 2026-08-05 · deepseek-v4-flash

Pith's one-line read For k ≥ 5, vertex-critical graphs can hide all small critical edge sets, the paper proves lower and upper bounds

desk verdict Can't judge the math: the record has only the abstract of the graph theory paper, and the attached full text is an unrelated medical-imaging paper. read the letter →

arxiv 2508.08703 v1 pith:XULY7ZTP submitted 2025-08-12 math.CO

classification math.CO MSC 05C1505C35
keywords vertex-criticalgraphscriticaledgesetschromaticnumberregularitylemmagluingconstructionasymptoticboundsgraphcoloring
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Criticality distinguishes graphs whose chromatic number drops when a single vertex is removed from those that drop only when an edge is removed. A problem posed in 1985 asked whether, for fixed $k\ge 4$, there are $k$-vertex-critical graphs of order $n$ in which no set of at most $f_k(n)$ edges is critical, with $f_k(n)\to\infty$. This paper answers yes for every $k>4$: it proves $f_k(n)=\Omega(n^{1/3})$, a stronger lower bound of order $\sqrt{n}$ along infinitely many $n$, and, for every $k\ge 4$, the first non-trivial upper bound $f_k(n)=O(n/(\log n)^{\Omega(1)})$. Only the case $k=4$ is left open. The lower-bound proof combines a gluing operation with an exhaustive analysis of proper colorings of a modified known construction; the upper bound follows from a variant of the regularity lemma.

What carries the argument

The gluing operation is the load-bearing device for the lower bound: it combines two $k$-vertex-critical graphs without small critical edge sets into a larger one, provided every proper colouring of the modified construction is compatible with the gluing. An exhaustive enumeration of the proper colourings of that modified example rules out colouring behaviours that would reintroduce a small critical edge set. For the upper bound, the regularity lemma variant decomposes an arbitrary $k$-vertex-critical graph into a bounded-complexity core plus a quasirandom remainder, which locates a critical edge set of size $O(n/(\log n)^{\Omega(1)})$.

What would settle it

For a fixed $k\ge 5$, exhibit arbitrarily large $k$-vertex-critical graphs of order $n$ in which every set of up to $n^{1/3-\varepsilon}$ edges is critical; this would refute $f_k(n)=\Omega(n^{1/3})$. Alternatively, for some $k\ge 4$ find a $k$-vertex-critical graph of order $n$ whose smallest critical edge set has size $\gg n/(\log n)^C$ for every fixed $C$, contradicting the upper bound.

Watch

Extended reading notes

Core claim

The paper's central claim is that the functions $f_k(n)$ grow like a power of $n$ for all $k\ge 5$: every sufficiently large $k$-vertex-critical graph can be chosen so that no set of at most $cn^{1/3}$ edges is critical, for some absolute $c>0$. It further shows $f_k(n)=\Omega(\sqrt{n})$ along an infinite sequence of orders, and proves the complementary bound $f_k(n)=O(n/(\log n)^{\Omega(1)})$ for every $k\ge 4$. The proof of the lower bound is constructive: a modification of an earlier example, analysed colouring-by-colouring, is combined with a gluing operation that preserves vertex-criticality, chromatic number $k$, and the absence of small critical edge sets. The upper bound uses a varia

Load-bearing premise

The lower bound holds only if the gluing operation and the complete case analysis of the modified construction's proper colourings cover every colouring that can arise; if some colouring behaviour escapes the analysis, a small critical edge set could enter and the $\Omega(n^{1/3})$ bound would fail.

Editorial extensions

If this is right

  • For every $k\ge 5$, there are arbitrarily large $k$-vertex-critical graphs whose smallest critical edge set has size at least $c\,n^{1/3}$.
  • Vertex-criticality and edge-criticality can diverge arbitrarily in the sublinear range: a graph may be critical under vertex deletion while still having no small critical edge set.
  • The first non-trivial upper bound caps the possible resilience at $O(n/(\log n)^{\Omega(1)})$ for all $k\ge 4$.
  • An infinite sequence of orders achieves the stronger $\Omega(\sqrt{n})$ lower bound.
  • The case $k=4$ remains open; all lower-bound results require $k>4$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the gluing operation can be iterated without degrading the order of the graphs, the lower bound might be pushed to $\Theta(n^{1/2})$ for all sufficiently large $n$, not just along a sparse sequence.
  • The regularity-lemma upper bound suggests that the true maximum of $f_k$ may be determined by quasirandom behaviour; random-like critical graphs are a natural testbed for whether the $n/(\log n)^c$ bound is tight.
  • The $k=4$ case may be reparable by adding a small gadget to the gluing that forces all colourings into the analysed cases, since the obstruction is the colouring analysis rather than the gluing concept.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

Summary. The submission is identified as arXiv:2508.08703 (math.CO), and its abstract announces results on critical edge sets in k-vertex-critical graphs: for every k > 4, f_k(n) = Ω(n^{1/3}), with a stronger Ω(√n) lower bound along an infinite sequence of n, and a first nontrivial upper bound f_k(n) = O(n/(log n)^{Ω(1)}) for every k ≥ 4. The proof is said to use a modification of Jensen's 2002 construction, a gluing operation, and a variant of Szemerédi's regularity lemma due to Conlon and Fox, with the k = 4 lower bound left open. However, the only full text supplied in the submission record is arXiv:2508.08705v1, an unrelated medical-image segmentation paper on adaptive confidence-wise loss for AS-OCT lens structure segmentation. Consequently, none of the graph-theoretic arguments, lemma statements, or proof details are present in the record, and the central claims cannot be checked.

Significance. If the announced results are correct, they would resolve Erdős's question for every k > 4 and provide the first nontrivial upper bound for the functions f_k, a substantial advance on a long-standing problem. The lower bound is especially significant because it strengthens previous partial results and leaves only k = 4 open. That said, this assessment is conditional: no proof is available to verify. The submission includes no machine-checked proofs, reproducible code, or parameter-free derivations; the only documented content is the abstract. The significance of the mathematical contribution therefore cannot be confirmed from the submitted record.

major comments (3)
  1. [Abstract / Submitted full text] The central claim f_k(n) = Ω(n^{1/3}) for all k > 4 is asserted in the abstract, but the only full text attached to the submission is an unrelated AS-OCT segmentation paper (arXiv:2508.08705v1). There are no theorem statements, lemmas, proofs, or definitions in the record that support the claimed lower bound. This is a load-bearing gap: the result cannot be verified or reproduced.
  2. [Abstract (gluing operation)] The proof of the lower bound is said to combine a modification of Jensen's construction with a gluing operation that preserves k-vertex-criticality and the absence of small critical edge sets. The abstract describes this operation only qualitatively. No argument is provided that the gluing preserves the three required properties simultaneously, nor is there an analysis of all proper colorings of the glued graph. Without these steps, the Ω(n^{1/3}) claim is unsupported.
  3. [Abstract (upper bound)] The upper bound f_k(n) = O(n/(log n)^{Ω(1)}) is stated to follow from a variant of Szemerédi's regularity lemma due to Conlon and Fox. The record contains no statement of this variant, no verification that its hypotheses are satisfied for k-vertex-critical graphs, and no derivation of the bound. As a result, the upper-bound claim is also unverifiable.
minor comments (3)
  1. [Abstract] The abstract says 'for every k ≥ 4' for the upper bound and 'for all k > 4' for the lower bound; this is clear enough, but a sentence explicitly separating the k = 4 status would help readers.
  2. [Abstract] The stronger lower bound of order √n along an infinite sequence of n is announced without indicating how the infinite sequence is generated or how it relates to the n^{1/3} bound. A remark on the underlying construction would be useful.
  3. [References] The abstract cites Jensen (2002) and Conlon and Fox, but the submitted record contains no bibliography. Full references should be supplied with the correct manuscript.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity visible in the available abstract; the attached full text is an unrelated AS-OCT paper, so the proof chain cannot be audited but nothing in the record reduces f_k to itself by construction.

full rationale

The only available text from the claimed graph paper is the abstract. The lower bound f_k(n)=Omega(n^{1/3}) is described as following from an intricate analysis of proper colorings of a modification of Jensen's construction plus a gluing operation, and the upper bound is said to use a Conlon-Fox variant of Szemeredi's regularity lemma. These are external ingredients; they are not defined in terms of f_k, and no equation in the abstract fits a parameter and then renames it as a prediction. The submitted full text is arXiv:2508.08705v1, a medical image segmentation paper about Adaptive Confidence-Wise loss, which is unrelated to the claimed combinatorics paper. This means the derivation's key steps are not inspectable in this record, which is a correctness/reproducibility concern, not a circularity finding. Per the instructions, circularity must be exhibited by quoting a specific reduction; none can be exhibited here. Therefore the appropriate finding is no significant circularity.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters are visible from the abstract: f_k(n) is a defined extremal function, and the constants hidden in Ω and O are existential proof constants rather than numbers fitted to data. The main unverified imports are Jensen's construction and the Conlon-Fox regularity lemma variant. The gluing operation and the coloring analysis, which carry the lower-bound proof, cannot be audited without the manuscript body, which the supplied record does not contain.

assumptions (4)
  • domain assumption Jensen's 2002 result: for every k ≥ 5, there exists a k-vertex-critical graph with no critical edges (Dirac's conjecture for k ≥ 5).
    Invoked in the abstract as the basis for the new construction ('a modification of an earlier construction due to Jensen'); its correctness is imported, not re-proved.
  • domain assumption The Conlon-Fox variant of Szemerédi's regularity lemma is correct and applicable to the graphs used in the upper-bound proof.
    The abstract states the upper bound f_k(n) = O(n/(log n)^{Ω(1)}) 'is obtained using a variant of Szemerédi's regularity lemma due to Conlon and Fox'; the lemma and its applicability are assumed.
  • standard math Standard definitions and elementary facts about k-chromatic, vertex-critical, and edge-critical graphs (Dirac, 1950s).
    Background for the definitions of f_k(n) and for the claim that removing a set of edges lowers the chromatic number; standard textbook material.
  • standard math The extremal function f_k(n) is well-defined, i.e., for each admissible n there exists at least one k-vertex-critical graph of order n whose removal resilience attains the stated extremes.
    Needed for the Ω and O bounds to have meaning; standard existence reasoning in chromatic graph theory.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Critical edge sets in vertex-critical graphs." pith.science (2026). https://pith.science/paper/XULY7ZTP

@misc{pith2026250808703,
  author       = {Pith},
  title        = {Pith review of: Critical edge sets in vertex-critical graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XULY7ZTP}},
  note         = {Machine review of arXiv:2508.08703}
}
abstract

Criticality is a fundamental notion in graph theory that has been studied continually since its introduction in the early 50s by Dirac. A graph is called $k$-vertex-critical ($k$-edge-critical) if it is $k$-chromatic but removing any vertex (edge) lowers the chromatic number to $k-1$. A set of edges in a graph is called critical if its removal reduces the chromatic number of the graph. In 1970, Dirac conjectured a rather strong distinction between the notions of vertex- and edge-criticality, namely that for every $k\ge 4$ there exists a $k$-vertex-critical graph that does not have any critical edges. This conjecture was proved for $k\ge 5$ by Jensen in 2002 and remains open only for $k=4$. A much stronger version of Dirac's conjecture was proposed by Erd\H{o}s in 1985: Let $k\ge 4$ be fixed, and let $f_k(n)$ denote the largest integer such that there exists a $k$-vertex-critical graph of order $n$ in which no set of at most $f_k(n)$ edges is critical. Is it true that $f_k(n)\rightarrow \infty$ for $n\rightarrow \infty$? Strengthening previous partial results, we solve this problem affirmatively for all $k>4$, proving that $$f_k(n)=\Omega(n^{1/3}).$$ This leaves only the case $k=4$ open. We also show that a stronger lower bound of order $\sqrt{n}$ holds along an infinite sequence of numbers $n$. Finally, we provide a first non-trivial upper bound on the functions $f_k$ by proving that $$f_k(n)=O\left(\frac{n}{(\log n)^{\Omega(1)}}\right)$$ for every $k\ge 4$. Our proof of the lower bound on $f_k(n)$ involves an intricate analysis of the structure of proper colorings of a modification of an earlier construction due to Jensen, combined with a gluing operation that creates new vertex-critical graphs without small critical edge sets from given such graphs. The upper bound is obtained using a variant of Szemer\'{e}di's regularity lemma due to Conlon and Fox.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

40 extracted references · 37 canonical work pages

  1. [1]

    W. H. Organization, World report on vision (2019)

  2. [2]

    Zhang, Z

    X. Zhang, Z. Xiao, H. Fu, Y . Hu, J. Yuan, Y . Xu, R. Higashita, J. Liu, Attention to region: Region-based integration-and-recalibration networks for nuclear cataract classification using as-oct images, Medical Image Analysis 80 (2022) 102499

  3. [3]

    Zhang, Y

    X.-Q. Zhang, Y . Hu, Z.-J. Xiao, J.-S. Fang, R. Higashita, J. Liu, Machine learning for cataract classification /grading on ophthalmic imaging modalities: a survey, Machine Intelligence Research 19 (3) (2022) 184–208

  4. [4]

    Zhang, Z

    X. Zhang, Z. Xiao, B. Yang, X. Wu, R. Higashita, J. Liu, Regional context-based recalibration network for cataract recognition in as-oct, Pattern Recognition 147 (2024) 110069

  5. [5]

    W. Wang, J. Zhang, X. Gu, X. Ruan, X. Chen, X. Tan, G. Jin, L. Wang, M. He, N. Congdon, Objective quantification of lens nuclear opacities using swept- source anterior segment optical coherence tomography, British Journal of Oph- thalmology (2021). 26

  6. [6]

    Z. Xiao, X. Zhang, B. Zheng, Y . Guo, R. Higashita, J. Liu, Multi-style spatial attention module for cortical cataract classification in as-oct image with super- vised contrastive learning, Computer Methods and Programs in Biomedicine 244 (2024) 107958

  7. [7]

    P. Yin, M. Tan, H. Min, Y . Xu, G. Xu, Q. Wu, Y . Tong, H. Risa, J. Liu, Automatic segmentation of cortex and nucleus in anterior segment oct images, in: Compu- tational Pathology and Ophthalmic Medical Image Analysis: First International Workshop, COMPAY 2018, and 5th International Workshop, OMIA 2018, Held in Conjunction with MICCAI 2018, Granada, Spain...

  8. [8]

    Zhang, Y

    S. Zhang, Y . Yan, P. Yin, Z. Qiu, W. Zhao, G. Cao, W. Chen, J. Yuan, R. Higashita, Q. Wu, M. Tan, J. Liu, Guided m-net for high-resolution biomedical image seg- mentation with weak boundaries, in: Ophthalmic Medical Image Analysis: 6th International Workshop, OMIA 2019, Held in Conjunction with MICCAI 2019, Shenzhen, China, October 17, Proceedings 6, Spr...

Show all 40 references
  1. [9]

    Ronneberger, P

    O. Ronneberger, P. Fischer, T. Brox, U-net: Convolutional networks for biomed- ical image segmentation, in: Medical Image Computing and Computer-Assisted Intervention–MICCAI 2015: 18th International Conference, Munich, Germany, October 5-9, 2015, Proceedings, Part III 18, Spri...

  2. [10]

    T.-Y . Lin, P. Goyal, R. Girshick, K. He, P. Doll´ar, Focal loss for dense object de- tection, in: Proceedings of the IEEE international conference on computer vision, 2017, pp. 2980–2988

  3. [11]

    Caliva, C

    F. Caliva, C. Iriondo, A. M. Martinez, S. Majumdar, V . Pedoia, Distance map loss penalty term for semantic segmentation, arXiv preprint arXiv:1908.03679 (2019)

  4. [12]

    C. Guo, G. Pleiss, Y . Sun, K. Q. Weinberger, On calibration of modern neural networks, in: International conference on machine learning, PMLR, 2017, pp. 1321–1330. 27

  5. [13]

    Zhong, J

    Z. Zhong, J. Cui, S. Liu, J. Jia, Improving calibration for long-tailed recognition, in: Proceedings of the IEEE /CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2021, pp. 16489–16498

  6. [14]

    Patra, R

    R. Patra, R. Hebbalaguppe, T. Dash, G. Shro ff, L. Vig, Calibrating deep neural networks using explicit regularisation and dynamic data pruning, in: Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, 2023, pp. 1541–1549

  7. [15]

    D. Wang, B. Gong, L. Wang, On calibrating semantic segmentation models: anal- yses and an algorithm, in: Proceedings of the IEEE /CVF Conference on Com- puter Vision and Pattern Recognition, 2023, pp. 23652–23662

  8. [16]

    H. Ye, X. Zhang, Y . Hu, H. Fu, J. Liu, Vsr-net: Vessel-like structure rehabilitation network with graph clustering, arXiv preprint arXiv:2312.13116 (2023)

  9. [17]

    Landman, Z

    B. Landman, Z. Xu, J. Igelsias, M. Styner, T. Langerak, A. Klein, Miccai multi- atlas labeling beyond the cranial vault–workshop and challenge, in: Proc. MIC- CAI Multi-Atlas Labeling Beyond Cranial Vault—Workshop Challenge, V ol. 5, 2015, p. 12

  10. [18]

    J. Ma, Y . He, F. Li, L. Han, C. You, B. Wang, Segment anything in medical images, Nature Communications 15 (1) (2024) 654

  11. [19]

    J. Hao, F. Li, H. Hao, H. Fu, Y . Xu, R. Higashita, X. Zhang, J. Liu, Y . Zhao, Hy- brid variation-aware network for angle-closure assessment in as-oct, IEEE Trans- actions on Medical Imaging 41 (2) (2021) 254–265

  12. [20]

    H. Fu, Y . Xu, S. Lin, D. W. K. Wong, M. Baskaran, M. Mahesh, T. Aung, J. Liu, Angle-closure detection in anterior segment oct based on multilevel deep net- work, IEEE transactions on cybernetics 50 (7) (2019) 3358–3366

  13. [21]

    A. G. Roy, S. Conjeti, S. P. K. Karri, D. Sheet, A. Katouzian, C. Wachinger, N. Navab, Relaynet: retinal layer and fluid segmentation of macular optical coher- ence tomography using fully convolutional networks, Biomedical optics express 8 (8) (2017) 3627–3642. 28

  14. [22]

    C. S. Lee, A. J. Tyring, N. P. Deruyter, Y . Wu, A. Rokem, A. Y . Lee, Deep- learning based, automated segmentation of macular edema in optical coherence tomography, Biomedical optics express 8 (7) (2017) 3440–3448

  15. [23]

    W. Wu, Y . Gong, H. Hao, J. Zhang, P. Su, Q. Yan, Y . Ma, Y . Zhao, Choroidal layer segmentation in oct images by a boundary enhancement network, Frontiers in Cell and Developmental Biology 10 (2022) 1060241

  16. [24]

    Q. Yan, Y . Gu, J. Zhao, W. Wu, Y . Ma, J. Liu, J. Zhang, Y . Zhao, Automatic choroid layer segmentation in oct images via context e fficient adaptive network, Applied Intelligence 53 (5) (2023) 5554–5566

  17. [25]

    T. S. Mathai, K. L. Lathrop, J. Galeotti, Learning to segment corneal tissue inter- faces in oct images, in: 2019 IEEE 16th International Symposium on Biomedical Imaging (ISBI 2019), IEEE, 2019, pp. 1432–1436

  18. [26]

    Y . Sun, N. Maimaiti, P. Xu, P. Jin, J. Cai, G. Qian, P. Chen, M. Xu, G. Jia, Q. Wu, An as-oct image dataset for deep learning-enabled segmentation and 3d reconstruction for keratitis, Scientific Data 11 (1) (2024) 627

  19. [27]

    B. Yang, X. Zhang, S. Li, R. Higashita, J. Liu, Ha-net: Hierarchical attention network based on multi-task learning for ciliary muscle segmentation in as-oct, IEEE Signal Processing Letters 30 (2023) 1342–1346. ���������������� ������������

  20. [28]

    G. Cao, W. Zhao, R. Higashita, J. Liu, W. Chen, J. Yuan, Y . Zhang, M. Yang, An efficient lens structures segmentation method on as-oct images, in: 2020 42nd Annual International Conference of the IEEE Engineering in Medicine & Biology Society (EMBC), IEEE, 2020, pp. 1646–1649

  21. [29]

    H. Fang, P. Yin, H. Chen, Y . Fang, W. Chen, J. Yuan, H. Risa, J. Liu, Y . Xu, Lens structure segmentation from as-oct images via shape-based learning, Computer Methods and Programs in Biomedicine 230 (2023) 107322. 29

  22. [30]

    Z. Xiao, X. Zhang, R. Higashita, J. Liu, Mm-unet: A mixed mlp architecture for improved ophthalmic image segmentation (2024). ���������������� . URL ��������������������������������

  23. [31]

    Fausto Milletari, A

    N. Fausto Milletari, A. S.-A. V-Net, Fully convolutional neural networks for vol- umetric medical image segmentation

  24. [32]

    Petit, N

    O. Petit, N. Thome, C. Rambour, L. Themyr, T. Collins, L. Soler, U-net trans- former: Self and cross attention for medical image segmentation, in: Machine Learning in Medical Imaging: 12th International Workshop, MLMI 2021, Held in Conjunction with MICCAI 2021, Strasbourg, Fra...

  25. [33]

    J. Ma, J. Chen, M. Ng, R. Huang, Y . Li, C. Li, X. Yang, A. L. Martel, Loss odyssey in medical image segmentation, Medical Image Analysis 71 (2021) 102035

  26. [34]

    El Jurdi, C

    R. El Jurdi, C. Petitjean, P. Honeine, V . Cheplygina, F. Abdallah, High-level prior- based loss functions for medical image segmentation: A survey, Computer Vision and Image Understanding 210 (2021) 103248

  27. [35]

    S. S. M. Salehi, D. Erdogmus, A. Gholipour, Tversky loss function for image seg- mentation using 3d fully convolutional deep networks, in: International workshop on machine learning in medical imaging, Springer, 2017, pp. 379–387

  28. [36]

    Abraham, N

    N. Abraham, N. M. Khan, A novel focal tversky loss function with improved attention u-net for lesion segmentation, in: 2019 IEEE 16th international sympo- sium on biomedical imaging (ISBI 2019), IEEE, 2019, pp. 683–687

  29. [37]

    Y . Chen, L. Yu, J.-Y . Wang, N. Panjwani, J.-P. Obeid, W. Liu, L. Liu, N. Ko- valchuk, M. F. Gensheimer, L. K. Vitzthum, B. M. Beadle, D. T. Chang, Q.-T. Le, B. Han, L. Xing, Adaptive region-specific loss for improved medical image segmentation, IEEE Transactions on Pattern A...

  30. [38]

    J. Chen, Y . Lu, Q. Yu, X. Luo, E. Adeli, Y . Wang, L. Lu, A. L. Yuille, Y . Zhou, Transunet: Transformers make strong encoders for medical image segmentation, arXiv preprint arXiv:2102.04306 (2021)

  31. [39]

    Zhang, Z

    X. Zhang, Z. Xiao, X. Wu, Y . Chen, J. Zhao, Y . Hu, J. Liu, Pyramid pixel con- text adaption network for medical image classification with supervised contrastive learning, IEEE Transactions on Neural Networks and Learning Systems (2024) 1–14

  32. [40]

    Loshchilov, F

    I. Loshchilov, F. Hutter, Sgdr: Stochastic gradient descent with warm restarts, arXiv preprint arXiv:1608.03983 (2016). 31

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.