Pith. sign in

REVIEW 1 major objections 4 minor 1 cited by

$(\Delta-1)$-dicolouring of digraphs

T0 review · 1 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Large digraphs with no large biclique are (Δ−1)-dicolourable unless one obstruction appears

desk verdict A substantial large-Δ directed analogue of Reed's theorem with a genuinely new obstruction, but the third generalization leans on an unproved external proposition. read the letter →

arxiv 2507.10266 v1 pith:XRUO5AQI submitted 2025-07-14 math.CO cs.DM

Ararat Harutyunyan , Ken-ichi Kawarabayashi , Lucas Picasarri-Arrieta , Gil Puig i Surroca This is my paper · ORCID
classification math.COcs.DM MSC 05C2005C15
keywords dichromaticnumberbicliqueBorodin–KostochkaconjectureReed'sdensedecompositiondigraphcolouringmaximumout-degreedirectedBrookstheorem
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

The paper proves, for all sufficiently large integers Δ, a directed analogue of the Borodin–Kostochka conjecture. The claim is that a digraph whose largest geometric-mean degree $\tilde{\Delta}$ is at most Δ and whose biclique number is at most Δ−1 has dichromatic number at most Δ−1, with exactly one exception: a directed 3-cycle completely joined to a complete digraph on Δ−2 vertices. The same conclusion holds when the bound is imposed only on the out-degree $\Delta^+$ rather than on $\tilde{\Delta}$. From these results the paper derives sufficient conditions phrased through $\Delta_{\min}$, the smaller of the in- and out-degree, and shows that one of these conditions is best possible through an NP-completeness result. The proof introduces a dense decomposition lemma for digraphs that transfers the classical dense-decomposition technique for graphs into the directed setting.

What carries the argument

The load-bearing tool is the Dense Decomposition Lemma: for $0<\varepsilon<1/2$ and a sublinear function $d$, every sufficiently large digraph admits a partition $X_1\sqcup\cdots\sqcup X_t\sqcup S$ where each $X_i$ has size about $\Delta_{\max}$, bounded arc boundary, and consists exactly of vertices with almost $\Delta_{\max}$ out-neighbours inside $X_i$, while vertices in $S$ are $d$-sparse. This lets the authors isolate quasi-biclique clusters, prove structural lemmas about special vertices they call saviours, and then run a Lovász Local Lemma-based random uncolouring argument: sparse vertices see repeated colours, and dense clusters are handled cluster by cluster. The unique obstruction $\vec{C}_3\boxtimes\overleftrightarrow{K}_{\Delta-2}$ is exactly the configuration on which this strategy is forced to fail.

What would settle it

Find, for arbitrarily large Δ, a digraph with $\tilde{\Delta}(D)\le\Delta$ and $\overleftrightarrow{\omega}(D)\le\Delta-1$ that contains no $\vec{C}_3\boxtimes\overleftrightarrow{K}_{\Delta-2}$ and still has dichromatic number at least Δ; such a digraph would disprove Theorem 8. Alternatively, exhibit a digraph for which the transformation promised by Proposition 7.3 of [25] increases the dichromatic number, which would refute Corollaries 13 and 14.

Watch

Extended reading notes

Core claim

What the paper establishes is a dichotomy, not just a bound: for every large Δ, the only way a digraph with $\tilde{\Delta}(D)\le\Delta$ and $\overleftrightarrow{\omega}(D)\le\Delta-1$ can need Δ colours is the explicit block $\vec{C}_3\boxtimes\overleftrightarrow{K}_{\Delta-2}$. It proves the same dichotomy when $\Delta^+(D)$ replaces $\tilde{\Delta}(D)$, and then converts the out-degree statement into a $\Delta_{\min}$-based sufficient condition: if the biclique number is smaller than $(\Delta-1)/2$, or the underlying graph has clique number at most $\Delta-1$, then $\Delta_{\min}(D)\le\Delta$ forces a $(\Delta-1)$-dicolouring. On symmetric digraphs the first dichotomy specialises to the undirected Borodin–Kostochka theorem for large Δ.

Load-bearing premise

The two large-degree theorems are built on the dense decomposition lemma, but the $\Delta_{\min}$ corollaries additionally rely on Proposition 7.3 from the cited preprint [25], an unproved transformation that is stated to preserve the dichromatic number while bounding the out-degree, and that the present paper quotes without proof.

Editorial extensions

If this is right

  • If Theorem 8 is correct, every symmetric digraph obtained from a graph with maximum degree Δ and clique number at most Δ−1 is (Δ−1)-dicolourable, reproducing the undirected Borodin–Kostochka result for large Δ.
  • The obstruction is unique: the only directed phenomenon preventing such a colouring is a directed triangle fused through every possible two-way arc to a complete digraph on Δ−2 vertices.
  • Corollary 14 gives a new route to the undirected theorem: a digraph whose underlying graph has clique number at most Δ−1 and whose smaller-degree parameter is at most Δ is (Δ−1)-dicolourable.
  • The NP-completeness result shows that the biclique-size threshold in Corollary 13 cannot be improved without changing the complexity of the decision problem.
  • The dense decomposition lemma alone provides a reusable decomposition for large-degree digraphs, independent of the colouring application.

Reading between the lines

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

  • The dense decomposition lemma is likely to be reusable: future proofs that bound a digraph parameter by splitting into sparse vertices and near-biclique clusters could run through the same partition.
  • If Proposition 7.3 of the cited preprint is supplied with a full proof, the $\Delta_{\min}$ corollaries become completely self-contained; as it stands their unconditional status depends on that external result.
  • The global dichotomy suggests a practical recognition angle: for large Δ, a digraph violating the bound must contain a small certificate of size Δ−1, so the bad case is structurally compressible rather than scattered.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

1 major / 4 minor

Summary. The paper proposes three digraph analogues of the Borodin–Kostochka and Reed theorems, replacing maximum degree, clique number, and chromatic number by geometric-mean degree, biclique number, and dichromatic number. The main theorems, Theorem 8 for the geometric-mean degree and Theorem 12 for the maximum out-degree, assert that for large Δ every digraph with the relevant degree parameter at most Δ and biclique number at most Δ−1 is (Δ−1)-dicolourable unless it contains the unique obstruction C3 ⊞ K_{Δ−2}. The proofs introduce a directed dense decomposition lemma (Lemma 9) and combine structural analysis with the Lovász Local Lemma, Talagrand's inequality, and Azuma's inequality. Section 6 derives Corollaries 13 and 14, giving a third generalisation via Δmin, and proves an NP-completeness result (Proposition 15). Theorems 8 and 12 appear to be proved from first principles, but the derivation of Corollary 30, and hence of Corollaries 13 and 14, relies on an unproved proposition from the authors' preprint [25].

Significance. If Theorems 8 and 12 are correct, they are substantial and natural generalizations of Reed's theorem to digraphs, with a clean directed obstruction, and the dense decomposition lemma is likely to be a useful tool in further work on digraph colouring. The proofs are detailed, internally coherent, and do not rely on fitted parameters: the thresholds are existential and all probability estimates are justified. However, the advertised third independent generalization, based on Corollary 30, is not established within the manuscript because its key step is delegated to an unreviewed same-author preprint. The paper would be acceptable for publication after this gap is addressed.

major comments (1)
  1. [6]
minor comments (4)
  1. [2.1] The phrase 'Adigon is a pair of arcs...' contains a typo; it should read 'A digon is a pair of arcs...'.
  2. [5, Claim 12.15] The first sentence of the proof of Claim 12.15 says 'Assume for a contradiction that |I≤6| ≥ 43', but the claim being proved bounds |I>6|; the subscript should be >6.
  3. [4.2, Claim 29.1] In the definition of W_{x,y}, the expression 'N^+(s) ∪ N(x) ∪ N(y) \ {x,y}' is clearer with parentheses around the union before the set difference.
  4. [6] The remark that every k-obstruction contains a biclique of size ⌈(k−1)/2⌉ is true, but a one-line justification would help, since the biclique may need to be taken inside one side of the partition (A,B) rather than across it.

Circularity Check

1 steps flagged · score 4.0 of 10

Theorems 8 and 12 are proved from first principles with no fitted inputs; the only load-bearing self-citation is [25, Prop 7.3], imported without proof to derive the third advertised generalization (Corollaries 13, 14, 30).

  1. self citation load bearing [Section 6, proof of Corollary 30 (second paragraph, application of Theorem 12 to the transformed digraph bD)]
    "It was proved in [25, Proposition 7.3] that ∆+( bD) ⩽ ∆min(D) ⩽ ∆ and ⃗ χ( bD) ⩾ ⃗ χ(D) ⩾ ∆, we omit the proof."

    Corollary 30 is the entire bridge to the advertised 'third independent generalisation' (Corollaries 13 and 14). To apply Theorem 12 to the transformed digraph bD, the proof needs exactly the hypotheses ∆+(bD) ⩽ ∆min(D) and χ̃(bD) ⩾ χ̃(D); both inequalities are imported verbatim from [25, Proposition 7.3], a preprint by two of the present authors (Kawarabayashi and Picasarri-Arrieta, arXiv:2407.05827), and the paper explicitly says 'we omit the proof'. No machine-check, code, or independent derivation is supplied, so the third generalization reduces to a self-citation that is unverified within this manuscript: the hypotheses of Theorem 12 for bD are literally the conclusions of [25, Prop 7.3]. Theorems 8 and 12 themselves do not use this proposition.

full rationale

The central results are derived from first principles. Theorem 8 follows from the Dense Decomposition Lemma (Lemma 9, proved by elementary claims 9.1–9.7), structural lemmas 20–27, and the probabilistic Lemma 29 with standard Talagrand/Azuma bounds; no parameter is fitted to data and no equation is defined in terms of its own conclusion. Theorem 12 is obtained from Theorem 8 plus a discharging argument (Claims 12.1–12.15). The single load-bearing self-citation is in Section 6: Corollary 30 (and hence Corollaries 13, 14 and the 'third independent generalisation') applies Theorem 12 to a transformed digraph bD using hypotheses exactly supplied by [25, Proposition 7.3], an unreviewed same-author preprint whose proof is omitted here ('we omit the proof'). Because the main theorems (Theorems 8 and 12) have independent content and the self-citation only supports the third corollary chain, the circularity burden is partial rather than structural; this is the one flagged step and the basis of the score of 4.

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

No empirical data are fitted; the free parameters listed are proof constants chosen for convenience, not tuned to observations. The only non-standard imported ingredient is the unproved proposition from [25]. No new physical or mathematical entities are postulated.

free parameters (5)
  • epsilon in Lemma 9 = 1/100 in Theorem 8 proof
    Sparsity/denseness threshold in the dense decomposition lemma; any sufficiently small constant would work, but 1/100 is chosen by hand.
  • d in Lemma 9 = log_3(Δ)
    Sparsity function defining d-dense vertices; chosen as a sublinear function tending to infinity, any ω(1) ∩ o(Δ) works.
  • r in Section 4.1 = log_4(Δ)
    Threshold for the r-saviour sets; chosen so that concentration bounds and greedy colour extension arguments succeed.
  • Δ8 in Theorem 8 = not explicit, exists by proof
    The paper proves existence of a threshold but does not compute it.
  • Δ12 in Theorem 12 = max(Δ8, 556)
    Threshold in Theorem 12, depends on the unspecified Δ8.
assumptions (5)
  • standard math Lovász Local Lemma (symmetric version)
    Used in Lemma 29 to show that an extendable partial dicolouring exists with positive probability.
  • standard math Talagrand's Inequality (integer-valued version, proved in Appendix A)
    Used to prove concentration of M_s in Claim 29.1.
  • standard math Azuma's Inequality
    Used to prove concentration of M_i in Claim 29.2.2.
  • standard math Directed Brooks' Theorem (Mohar)
    Invoked in Lemma 20 to rule out Δmax = Δ−1 in a minimal counterexample.
  • domain assumption Proposition 7.3 of [25] (same authors' preprint)
    Used without proof in Corollary 30 to construct a digraph with bounded Δ+ and preserved dichromatic number; the proposition is not reproduced in this paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of $(\Delta-1)$-dicolouring of digraphs." pith.science (2026). https://pith.science/paper/XRUO5AQI

@misc{pith2026250710266,
  author       = {Pith},
  title        = {Pith review of: $(\Delta-1)$-dicolouring of digraphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XRUO5AQI}},
  note         = {Machine review of arXiv:2507.10266}
}
abstract

In 1977, Borodin and Kostochka conjectured that every graph with maximum degree $\Delta \geq 9$ is $(\Delta-1)$-colourable, unless it contains a clique of size $\Delta$. In 1999, Reed confirmed the conjecture when $\Delta\geq 10^{14}$. We propose different generalisations of this conjecture for digraphs, and prove the analogue of Reed's result for each of them. The chromatic number and clique number are replaced respectively by the dichromatic number and the biclique number of digraphs. If $D$ is a digraph such that $\min(\tilde{\Delta}(D),\Delta^+(D)) = \Delta \geq 9$, we conjecture that $D$ has dichromatic number at most $\Delta-1$, unless either (i) $D$ contains a biclique of size $\Delta$, or (ii) $D$ contains a biclique $K$ of size $\Delta-2$, a directed $3$-cycle $\vec{C_3}$ disjoint from $K$, and all possible arcs in both directions between $\vec{C_3}$ and $K$. If true, this implies the conjecture of Borodin and Kostochka. We prove it when $\Delta$ is large enough, thereby generalising the result of Reed. We finally give a sufficient condition for a digraph $D$ to have dichromatic number at most $\Delta_{\min}(D)-1$, assuming that $\Delta_{\min}(D)$ is large enough. In particular, this holds when the underlying graph of $D$ has no clique of size $\Delta_{\min}(D)$, thus yielding a third independent generalisation of Reed's result. We further give a hardness result witnessing that our sufficient condition is best possible. To obtain these new upper bounds on the dichromatic number, we prove a dense decomposition lemma for digraphs having large maximum degree, which generalises to the directed setting the so-called dense decomposition of graphs due to Molloy and Reed. We believe this may be of independent interest, especially as a tool in various applications.

Figures

Figures reproduced from arXiv: 2507.10266 by the authors.

Figure 1
Figure 1. An illustration of the decomposition X1 ⊔. . .⊔ Xt ⊔S provided by Lemma 9. Each set Xi has size close to ∆, and each vertex in Xi has a large fraction of its out-neighbours inside Xi . Intuitively, each Xi is thus close to being a biclique on ∆ vertices. Vertices in S are d-sparse. that is not d-sparse is d-dense. Given a subset of vertices X, we denote by ∂ +(X) (respectively ∂ −(X)) the set of arcs of D going out … view at source ↗
Figure 2
Figure 2. The two distinguished cases in the proof of Claim [PITH_FULL_IMAGE:figures/full_fig_p036_2.png] view at source ↗
Figure 3
Figure 3. The construction of Dij when i, j ∈ I ± (Figure (a)), and i, j ∈ I ⩽6 ∪I >6 (Figure (b)). In both figures, Dij is built from D by removing the dotted red part and adding the solid blue one. In Figure (b), wi does not have any out-neighbour in X nor any in-neighbour in N˜ i . Moreover, all but at most one vertex of N˜ i are out-neighbours of wi . The same properties hold for wj and N˜ j . for a contradiction that Dij… view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: The three possible types of a k-obstruction. In Figure (a), p is any value between 0 and k. In Figures (b) and (c), p is any value between 2 and k. auxiliary tournament T I with V (T I ) = I, and we orient each edge ij from i to j if Kij contains wj , and from j to i o…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Coloring digraphs with $\Delta-b$ colors

    math.CO 2026-07 conditional novelty 7.0 of 10

    Every digraph with sufficiently large maximum geometric-mean degree either contains a biclique exceeding that bound minus 2b or has dichromatic number at most that bound minus b.

Reference graph

Works this paper leans on

43 extracted references · 33 canonical work pages · cited by 1 Pith paper

  1. [25]

    Kawarabayashi and L

    K. Kawarabayashi and L. Picasarri-Arrieta. An analogue of Reed’s conjecture for digraphs. preprint arXiv:2407.05827, 2024

    arXiv 2024

  2. [1]

    Aboulker and G

    P. Aboulker and G. Aubian. Four proofs of the Directed Brooks’ Theorem.Discrete Math- ematics, page 113193, 2022

    work page 2022

  3. [2]

    Aboulker, G

    P. Aboulker, G. Aubian, and P. Charbit. Digraph colouring and arc-connectivity.preprint arXiv:2304.04690, 2023

    arXiv 2023

  4. [3]

    Aboulker, G

    P. Aboulker, G. Aubian, P. Charbit, and S. Thomassé. (− →P6, triangle)-free digraphs have bounded dichromatic number.The Electronic Journal of Combinatorics, 31(P4.60), 2024

    work page 2024

  5. [4]

    Aboulker, G

    P. Aboulker, G. Aubian, and R. Steiner. Heroes in orientations of chordal graphs.SIAM Journal on Discrete Mathematics, 36(4):2497–2505, 2022

    work page 2022

  6. [5]

    Aboulker, P

    P. Aboulker, P. Charbit, and R. Naserasr. Extension of Gyárfás-Sumner conjecture to digraphs. The Electronic Journal of Combinatorics, 28(P2.27), 2021

    work page 2021

  7. [6]

    Aboulker and Q

    P. Aboulker and Q. Vermande. Various bounds on the minimum number of arcs in a k-dicritical digraph. The Electronic Journal of Combinatorics, 31(P1.22), 2024

    work page 2024

  8. [7]

    Alon and J

    N. Alon and J. H. Spencer.The probabilistic method. Wiley Series in Discrete Mathematics and Optimization. Wiley-Blackwell, Hoboken, NJ, 3rd edition, 2008

    work page 2008

Show all 43 references
  1. [8]

    S. D. Andres and W. Hochstättler. Perfect digraphs.Journal of Graph Theory, 79(1):21–29, 2015

    2015

  2. [9]

    Axenovich, A

    M. Axenovich, A. Girão, R. Snyder, and L. Weber. Strong complete minors in digraphs. Combinatorics, Probability and Computing, 31(3):489–506, 2022

    2022

  3. [10]

    K. Azuma. Weighted sums of certain dependent random variables.Tohoku Mathematical Journal, Second Series, 19(3):357–367, 1967

    1967

  4. [11]

    Bang-Jensen and G

    J. Bang-Jensen and G. Z. Gutin.Digraphs: Theory, Algorithms and Applications. Springer- Verlag, London, 2nd edition, 2009

    2009

  5. [12]

    Bokal, G

    D. Bokal, G. Fijavz, M. Juvan, P. M. Kayll, and B. Mohar. The circular chromatic number of a digraph.Journal of Graph Theory, 46(3):227–240, 2004

    2004

  6. [13]

    O. V. Borodin and A. V. Kostochka. On an upper bound of a graph’s chromatic number, depending on the graph’s degree and density.Journal of Combinatorial Theory, Series B, 23(2-3):247–250, 1977. 43

    1977

  7. [14]

    R. L. Brooks. On colouring the nodes of a network. Mathematical Proceedings of the Cambridge Philosophical Society, 37(2):194–197, 1941

    1941

  8. [15]

    X. Chen, X. Hu, and W. Zang. A min-max theorem on tournaments.SIAM Journal on Computing, 37(3):923–937, 2007

    2007

  9. [16]

    L. Cook, T. Masařík, M. Pilipczuk, A. Reinald, and U. S. Souza. Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations ofP4. The Electronic Journal of Combinatorics, 30(P3.36), 2023

    2023

  10. [17]

    P. Erdős. Problems and results in number theory and graph theory. InProceedings of the ninth Manitoba Conference on Numerical Mathematics and Computing, pages 3–21, 1979

    1979

  11. [18]

    Erdős and L

    P. Erdős and L. Lovász. Problems and results on 3-chromatic hypergraphs and some related questions. Infinite and Finite Sets, 10(2):609–627, 1975

    1975

  12. [19]

    Farzad, M

    B. Farzad, M. Molloy, and B. Reed. (∆ − k)-critical graphs. Journal of Combinatorial Theory, Series B, 93(2):173–185, 2005

    2005

  13. [20]

    Golowich

    N. Golowich. The m-degenerate chromatic number of a digraph. Discrete Mathematics, 339(6):1734–1743, 2016

    2016

  14. [21]

    Gonçalves, L

    D. Gonçalves, L. Picasarri-Arrieta, and A. Reinald. Brooks-type colourings of digraphs in linear time. preprint arXiv:2405.05222, 2024

    2024 arXiv

  15. [22]

    Harutyunyan and B

    A. Harutyunyan and B. Mohar. Gallai’s theorem for list coloring of digraphs.SIAM Journal on Discrete Mathematics, 25(1):170–180, 2011

    2011

  16. [23]

    Harutyunyan and B

    A. Harutyunyan and B. Mohar. Strengthened Brooks' theorem for digraphs of girth at least three. The Electronic Journal of Combinatorics, 18(P195), 2011

    2011

  17. [24]

    Havet, L

    F. Havet, L. Picasarri-Arrieta, and C. Rambaud. On the minimum number of arcs in 4-dicritical oriented graphs.Journal of Graph Theory, 107(4):778–809, 2024

    2024

  18. [26]

    Kawarabayashi and L

    K. Kawarabayashi and L. Picasarri-Arrieta. An analogue of Reed’s conjecture for digraphs. InProceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3310–3324. SIAM, 2025

    2025

  19. [27]

    A. V. Kostochka and M. Stiebitz. The minimum number of edges in 4-critical digraphs of given order.Graphs and Combinatorics, 36(3):703–718, 2020

    2020

  20. [28]

    Mészáros and R

    T. Mészáros and R. Steiner. Complete directed minors and chromatic number.Journal of Graph Theory, 101(4):623–632, 2022

    2022

  21. [29]

    B. Mohar. Circular colorings of edge-weighted graphs.Journal of Graph Theory, 43(2):107– 116, 2003

    2003

  22. [30]

    B. Mohar. Eigenvalues and colorings of digraphs. Linear Algebra and its Applications, 432(9):2273–2277, 2010

    2010

  23. [31]

    Molloy and B

    M. Molloy and B. Reed. A bound on the total chromatic number.Combinatorica, 18(2):241– 280, 1998. 44

    1998

  24. [32]

    Molloy and B

    M. Molloy and B. Reed. The size of the giant component of a random graph with a given degree sequence. Combinatorics, probability and computing, 7(3):295–305, 1998

    1998

  25. [33]

    Molloy and B

    M. Molloy and B. Reed. Graph colouring and the probabilistic method. Algorithms and Combinatorics. Springer, Berlin, Germany, Nov. 2001

    2001

  26. [34]

    Molloy and B

    M. Molloy and B. Reed. Colouring graphs when the number of colours is almost the maximum degree.Journal of Combinatorial Theory, Series B, 109:134–195, 2014

    2014

  27. [35]

    Neumann-Lara

    V. Neumann-Lara. The dichromatic number of a digraph.Journal of Combinatorial Theory, Series B, 33:265–270, 1982

    1982

  28. [36]

    Picasarri-Arrieta

    L. Picasarri-Arrieta. Strengthening the Directed Brooks’ Theorem for oriented graphs and consequences on digraph redicolouring.Journal of Graph Theory, 106(1):5–22, 2024

    2024

  29. [37]

    Picasarri-Arrieta and M

    L. Picasarri-Arrieta and M. Stiebitz. Minimum number of arcs ink-critical digraphs with order at most2k − 1. Discrete Mathematics, 347(9):114072, 2024

    2024

  30. [38]

    B. Reed. ω, ∆, and χ. Journal of Graph Theory, 27(4):177–212, 1998

    1998

  31. [39]

    B. Reed. A strengthening of Brooks’ theorem.Journal of Combinatorial Theory, Series B, 76(2):136–149, 1999

    1999

  32. [40]

    Talagrand

    M. Talagrand. Concentration of measure and isoperimetric inequalities in product spaces. Publications Mathématiques de l’Institut des Hautes Etudes Scientifiques, 81:73–205, 1995. 45 A Proof of Lemma 17 As explained in Section 2, we show in this appendix how Lemma 17 is derive...

    1995

  33. [41]

    changing the outcome of any one trial can affectX by at mostc, and

  34. [42]

    Then P (|X − E(X)| > t) ⩽ 4 exp −t2 32c2r(E(X) + t) for any real numbert >126c p rE(X) + 344c2r

    for every s ∈ N, if X ⩾ s then there is a set of at mostrs trials whose outcomes certify that X ⩾ s. Then P (|X − E(X)| > t) ⩽ 4 exp −t2 32c2r(E(X) + t) for any real numbert >126c p rE(X) + 344c2r. Proof. We proceed in two steps. We first show that X is concentrated around its...

  35. [43]

    ♢ Claim 17.2

    By Theorem 31, we thus have P(X < µ− t) = P(B) ⩽ 2e−ℓ2/4 = 2 exp −t2 4c2rµ , as desired. ♢ Claim 17.2. For every t ⩾ 0, P(X > µ+ t) ⩽ 2 exp −t2 4c2r(µ+t+1) . Proof of claim. The proof is analogous to that of Claim 17.1, with some additional rounding arguments. Therefore, let A...

Pith tools

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