Pith Number

pith:S2JPBV34

pith:2024:S2JPBV34MOQPEEWYNOJBCJYF3K

not attested not anchored not stored refs resolved

Measurable Brooks's Theorem for Directed Graphs

Cecelia Higgins

Borel directed graphs of maximum degree d admit measurable d-dicolorings unless they contain the complete symmetric digraph on d+1 vertices.

arxiv:2405.00991 v4 · 2024-05-02 · math.LO · math.CO

Open paper page JSON Open Graph Bundle Merged state Verified badge What is a Pith Number?

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{S2JPBV34MOQPEEWYNOJBCJYF3K}

Prints a linked badge after your title and injects PDF metadata. Compiles on arXiv. Learn more · Embed verified badge

Record completeness

1 Bitcoin timestamp

2 Internet Archive

3 Author claim open · sign in to claim

4 Citations open

5 Replications open

✓ Portable graph bundle live · download bundle · merged state

The bundle contains the canonical record plus signed events. A mirror can host it anywhere and recompute the same current state with the deterministic merge algorithm.

Claims

C1strongest claim

if D is a Borel directed graph on a standard Borel space X such that the maximum degree of each vertex is at most d ≥ 3, then unless D contains the complete symmetric directed graph on d + 1 vertices, D admits a μ-measurable d-dicoloring with respect to any Borel probability measure μ on X, and D admits a τ-Baire-measurable d-dicoloring with respect to any Polish topology τ compatible with the Borel structure on X.

C2weakest assumption

The directed graph D must be Borel as a subset of X × X on a standard Borel space X; this Borel assumption is what permits the existence of measurable colorings with respect to arbitrary Borel measures and compatible Polish topologies (abstract, first sentence of main result).

C3one line summary

Borel directed graphs of bounded degree admit mu-measurable and Baire-measurable d-dicolorings unless containing the complete symmetric digraph on d+1 vertices, plus a definable Gallai theorem for list dicolorings.

References

2 extracted · 2 resolved · 0 Pith anchors

[1] [BCG+24] S. Brandt, Y. J. Chang, J. Greb´ ık, C. Grunau, V. Rozhoˇ n, and Z. Vidny´ anszky,On homomor- phism graphs, Forum Math. Pi12(2024), e10. [Ber19] A. Bernshteyn,Measurable versions of the Lov´ 2024

[2] Borel order dimension 1999

Formal links

2 machine-checked theorem links

Receipt and verification

First computed	2026-06-11T00:08:10.168169Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

9692f0d77c63a0f212d86b92112705dabdc0f31d88e4664be7e6f35622e6fba7

Aliases

arxiv: 2405.00991 · arxiv_version: 2405.00991v4 · doi: 10.48550/arxiv.2405.00991 · pith_short_12: S2JPBV34MOQP · pith_short_16: S2JPBV34MOQPEEWY · pith_short_8: S2JPBV34

Agent API

Resolver JSON Graph JSON Events JSON Schema Signing key

Verify this Pith Number yourself

curl -sH 'Accept: application/ld+json' https://pith.science/pith/S2JPBV34MOQPEEWYNOJBCJYF3K \
  | jq -c '.canonical_record' \
  | python3 -c "import sys,json,hashlib; b=json.dumps(json.loads(sys.stdin.read()), sort_keys=True, separators=(',',':'), ensure_ascii=False).encode(); print(hashlib.sha256(b).hexdigest())"
# expect: 9692f0d77c63a0f212d86b92112705dabdc0f31d88e4664be7e6f35622e6fba7

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "b8420b99c27cfa85d5bed190ee3079f55370be2ea7f514e2ce1539774bb868bf",
    "cross_cats_sorted": [
      "math.CO"
    ],
    "license": "http://creativecommons.org/licenses/by/4.0/",
    "primary_cat": "math.LO",
    "submitted_at": "2024-05-02T04:08:45Z",
    "title_canon_sha256": "28f81badb702c8709c3ac3a28fd00da58c630cbdba68720776b87e7c4ffb5c05"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2405.00991",
    "kind": "arxiv",
    "version": 4
  }
}