Pith. sign in

REVIEW 2 major objections 5 minor 111 references

Set-defined graph classes: $\chi$-boundedness meets tropical algebra

T0 review · 2 major / 5 minor · reviewed 2026-07-30 · grok-4.5

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

Pith's one-line read Full set-defined graph classes are either polynomially χ-bounded or contain high-chromatic shift graphs, and the distinction is decidable via tropical linear programs.

desk verdict Real two-way bridge between χ-boundedness of set-defined classes and tropical/mean-payoff feasibility; one fixable order-uniformity gap in the shift construction does not sink the theorems. read the letter →

arxiv 2607.23754 v1 pith:X3KY6IMK submitted 2026-07-26 cs.DM math.CO

Sarosh Adenwalla , Samuel Braunfeld , Tomáš Hons , John Sylvester , Viktor Zamaraev This is my paper
classification cs.DMmath.CO MSC 05C1505C7568R1091A43
keywords set-definedgraphsχ-boundednessshifttropicallinearprogrammingmean-payoffgameshereditaryclassesequalitylabelingschemes
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

Set-defined graph classes assign every vertex a fixed-length tuple of numbers and decide edges solely by which coordinates match. The paper asks when chromatic number stays controlled by clique number inside such a class. It proves that every graph in any set-defined class splits into polynomially many pieces (in the clique number), each a bounded union of graphs that map homomorphically into a shift graph; those unions are therefore the only obstruction to χ-boundedness. For the special “full” classes generated by a single Boolean rule, a sharp dichotomy holds: the class is either polynomially χ-bounded or already contains ordinary shift graphs (or their symmetrizations) of unbounded chromatic number. The same analysis yields an algorithm that reads the Boolean rule and decides which side of the dichotomy applies by checking feasibility of two finite tropical linear systems, dual to mean-payoff games. Conversely every integer tropical system encodes, in strongly polynomial time, as a full set-defined class whose χ-unboundedness is exactly the system’s feasibility. The result therefore supplies a purely graph-theoretic avatar of tropical feasibility and of the solvability of mean-payoff games.

What carries the argument

The tropical dichotomy for path-clause classes on functionally constrained vertex sets (Theorem 5.1): unbounded chromatic number if and only if both an associated max-plus system and an associated min-plus system admit finite solutions, the solutions supplying interval representations that embed high-dimensional shift digraphs, while non-feasibility forces long directed paths to be rigidly determined by their first vertex and therefore excludes the directed trees that force large chromatic number.

What would settle it

Exhibit a single full set-defined class that is χ-unbounded yet contains neither shift digraphs nor their symmetrizations of unbounded chromatic number, or exhibit a concrete Boolean function whose associated tropical pair is decided incorrectly by the algorithm.

Watch

Extended reading notes

Core claim

Every full set-defined digraph class is either polynomially χ-bounded or contains (symmetrized) shift digraphs of arbitrarily large chromatic number; χ-boundedness itself is decidable by reduction to feasibility of a pair of finite tropical systems, and every integer tropical system arises this way in strongly polynomial time.

Load-bearing premise

The external coloring fact that any digraph forbidding two long directed paths that share a common root (or the reverse of that tree) has chromatic number bounded by a linear function of the path length.

Editorial extensions

If this is right

  • Gyárfás–Sumner holds for every full set-defined graph class: the class is polynomially χ-bounded or contains every forest.
  • χ-boundedness of a full set-defined class can be decided algorithmically from its Boolean description alone.
  • Every mean-payoff game reduces in strongly polynomial time to the χ-boundedness question for an explicitly constructed set-defined class.
  • Inside set-defined classes the only possible witnesses of unbounded chromatic number are bounded unions of shift-colorable graphs.
  • A random full set-defined class is χ-unbounded with high probability.

Reading between the lines

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

  • Sufficient conditions for χ-boundedness already known for set-defined classes (bounded degeneracy, edge-stable bounded twin-width, …) immediately supply previously unrecognized polynomial-time islands for mean-payoff games.
  • The same tropical encoding may let combinatorial nullstellensatz or other algebraic tools for graph coloring attack the long-standing open question of polynomial-time solvability of mean-payoff games.
  • The decomposition isolates the classical Erdős–Hajnal girth-and-chromatic-number problem inside the narrower family of shift-colorable graphs, suggesting that progress on shift graphs alone would settle the conjecture for every set-defined class.
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

2 major / 5 minor

Summary. The manuscript studies hereditary classes in which vertices are fixed-length integer tuples and adjacency is determined by a Boolean rule on coordinate equalities. Its first main result decomposes every graph in such a class into polynomially many parts, relative to clique number, each a bounded union of shift-colorable digraphs. For full set-defined classes it proves a dichotomy between polynomial χ-boundedness and containment of shift or symmetrized shift digraphs of unbounded chromatic number. It further gives a finite tropical/mean-payoff criterion deciding χ-boundedness, proves a converse strongly polynomial encoding of integer tropical systems, and derives consequences including Gyárfás–Sumner for full classes and a random-class result.

Significance. If the missing construction detail is supplied, this is a substantial structural and algorithmic contribution. The decomposition theorem isolates shift-colorable graphs as the obstruction to χ-boundedness, while the full-class dichotomy is accompanied by an explicit finite decision criterion rather than a purely qualitative characterization. The two-way connection with tropical feasibility and mean-payoff games is novel and potentially useful across the areas involved. I also note the detailed proof outlines and examples, the quantitative bounds in Corollaries 5.22 and 5.33, and the strongly polynomial reverse reduction in Theorem 7.1 as particular strengths.

major comments (2)
  1. The proof does not establish that π[V(S)] is order-uniform, although order-uniformity is part of the definition of ⃗Y_{P,Z} in §4.5. Lemma 5.17 proves Z-functionality, and Lemmas 5.18–5.21 establish homomorphism/isomorphism properties, but arbitrary disjoint injections g_j need not preserve a common coordinate order. For example, in Example 5.4 choose an injective g_1 with g_1(1,2)>g_1(2,3) but g_1(1,3)<g_1(3,4); then π(1,2,3) and π(1,3,4) have opposite order in coordinates 1 and 2. Thus the constructed digraph may lie outside ⃗Y_{P,Z}, leaving (iii)⇒(ii) incomplete and affecting Theorems 5.1, 1.4, 1.6, and 7.1. The gap appears repairable: the authors could prove an encoding lemma for order-compatible g_j, possibly chosen separately for each finite S, for instance by ranking interval fragments by minimum entry, path tag, and then the tuple. Such a choice and the resulting order-uniform?/
  2. [§5.2, construction of π before Lemma 5.17] Related to the preceding point, the text should state whether the maps g_j in the construction of π are intended to be chosen once uniformly for all shift digraphs or may depend on the finite shift digraph S being realized. The latter is sufficient for the class-containment statement, but the current wording introduces one fixed collection of injections before considering arbitrary S. This distinction matters because an order-compatible encoding is straightforward on the finitely many interval fragments occurring in a fixed S, whereas a uniform encoding over all finite fragments requires a separate argument. Please make the quantifiers explicit and adjust Definition 5.6/Lemma 5.9 accordingly.
minor comments (5)
  1. [§1, paragraph after Definition 1.1 discussion] Typo: “can aslo be viewed” should be “can also be viewed.”
  2. [Example 3.3] The phrase “forms an of antichain” should be corrected, likely to “forms an antichain.”
  3. [Remark 5.38] “has no one” should read “has none” or “has no finite solution.”
  4. [Fact 5.28] Because this external coloring theorem is load-bearing later in §5.3, please give the precise theorem number or page in Addario-Berry–Havet–Thomassé and briefly explain that Λ_t is the relevant two-block orientation of the path on 2t−1 vertices. This would make the strict inequality in Fact 5.28 easier to verify.
  5. [§3 and §4.5] Please check the typography distinguishing arbitrary tuple sets from injective tuple sets in the definitions of N^I and its injective variant; in the present text the two notations are easy to conflate, especially when Y_{P,Z} is defined in §4.5.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: pure combinatorial/algebraic derivation with external dualities and coloring lemmas

full rationale

The paper’s central chain (decomposition → reduction to path clauses over functional sets → tropical systems dual to mean-payoff games → dichotomy/decidability/encoding) is self-contained mathematics. Tropical feasibility is linked to mean-payoff winning strategies by the external theorem of Akian–Gaubert–Guterman (and related DG06/Jos21 material), then specialized combinatorially to the path-clause systems constructed in §5; the graph classes ⃗X_f and ⃗Y_{P,Z} are defined via equality-pattern Boolean rules and functional constraints, not in terms of the chromatic conclusion. The bound converting non-feasibility into χ-boundedness (Fact 5.28) is an external coloring lemma (Addario-Berry–Havet–Thomassé). No parameters are fitted to data; no uniqueness theorem is imported from the authors to forbid alternatives; no ansatz is smuggled in via self-citation; known shift-graph facts (Fact 3.2) are standard and used as tools, not renamed as the main result. Minor citations to the authors’ prior set-defined/EBLS work are contextual background, not load-bearing for Theorems 1.4/1.6/1.7/5.1. Any gap about order-uniformity of π[V(S)] (skeptic) is a correctness concern, not circularity.

Assumptions & free parameters 0 free parameters · 6 assumptions · 3 invented entities

The paper rests on standard structural-graph and tropical-game foundations plus a short list of external coloring/game theorems; it introduces definitional machinery (set-defined classes, interval representations, trackable positions) that is fully specified inside the text rather than postulated as new physical entities.

assumptions (6)
  • standard math Mean-payoff games admit optimal positional strategies and finite values (Ehrenfeucht–Mycielski; Gurvich–Karzanov–Khachiyan).
    Invoked as Theorem 3.11 to connect tropical systems to winning regions.
  • standard math Max-plus system Ax ≤ Bx has a finite solution iff the row player does not lose from any start state (Akian–Gaubert–Guterman / Dhingra–Gaubert).
    Theorem 3.12 / Corollaries 3.13–3.16; load-bearing for both directions of the dichotomy.
  • standard math Digraphs excluding Λ_t or its reverse satisfy χ ≤ 2t−1 (Addario-Berry–Havet–Thomassé).
    Fact 5.28; converts the no-bifurcation property into a chromatic bound.
  • standard math Disjunction of χ-bounded classes is χ-bounded with product binding function (Gyárfás).
    Lemma 3.7; used throughout the DNF reductions.
  • standard math Shift graphs S(n,d) have unbounded chromatic number and odd-girth 2d+1; iterated directed line graphs of acyclic digraphs embed into them.
    Fact 3.2 (Hell–Nešetřil et al.); supplies the hard side of the dichotomy.
  • domain assumption Hereditary classes are closed under induced subgraphs and isomorphism; digraphs are loopless and without opposite multi-edges unless symmetrized.
    Standing conventions of §3 that fix the objects under study.
invented entities (3)
  • Interval representation of a path clause over functional constraints independent evidence
    purpose: Encodes finite tropical solutions as concrete embeddings of high-dimensional shift digraphs into Y_{P,Z}.
    Definition 5.6; central constructive device for (iii)⇒(ii) of Theorem 5.1. Fully defined, not an external postulate.
  • Trackable positions / coordinate multidigraph K, Θ independent evidence
    purpose: Witness that long directed paths have second vertex functionally determined by the first when a tropical system is infeasible.
    Definitions 5.39–5.42; technical engine of the chromatic upper bound. Internal combinatorial construction.
  • Full set-defined class X_f / path-clause class Y_{P,Z} independent evidence
    purpose: Precise objects whose χ-boundedness is classified and decided.
    Definitional core of the paper (Def. 1.1, §4.5); standard style of introducing a graph class.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Set-defined graph classes: $\chi$-boundedness meets tropical algebra." pith.science (2026). https://pith.science/paper/X3KY6IMK

@misc{pith2026260723754,
  author       = {Pith},
  title        = {Pith review of: Set-defined graph classes: $\chi$-boundedness meets tropical algebra},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/X3KY6IMK}},
  note         = {Machine review of arXiv:2607.23754}
}
abstract

We study set-defined graph classes: hereditary classes whose vertices are assigned fixed-length numerical tuples, with adjacency determined solely by equality patterns among coordinates. These classes arise in structural graph theory, communication complexity, logic, and adjacency labeling schemes. We ask when they are $\chi$-bounded, that is, when chromatic number is bounded in terms of clique number throughout the class. First, we prove a decomposition theorem: every graph in a set-defined class can be partitioned into a number of parts polynomially bounded in its clique number, each inducing a union of a bounded number of shift-colorable graphs, that is, graphs admitting a homomorphism to a shift graph. Thus bounded unions of shift-colorable graphs form the fundamental obstruction to $\chi$-boundedness in set-defined classes. For full set-defined classes, consisting of all graphs realizable by a fixed Boolean rule on equality patterns, we prove a stronger dichotomy: every such class is either polynomially $\chi$-bounded or contains shift graphs of arbitrarily large chromatic number. Moreover, we provide an algorithm that, given a Boolean-function description of a full set-defined class, decides $\chi$-boundedness of the class. It reduces the problem to feasibility of tropical linear programs, and its correctness follows from a duality with winning strategies in mean-payoff games. Conversely, every integer system of tropical inequalities, and hence every mean-payoff game, can be encoded in strongly polynomial time as a set-defined class whose non-$\chi$-boundedness is equivalent to feasibility. This provides a graph-theoretic counterpart of tropical feasibility and mean-payoff-game solvability, linking structural graph theory, tropical algebra, and game-theoretic algorithms.

Figures

Figures reproduced from arXiv: 2607.23754 by the authors.

Figure 1
Figure 1. Examples of graphs from set-defined classes: shift graphs, equivalence graphs (i.e. graphs in which [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Examples of clause digraphs corresponding to different types of injective clauses. [PITH_FULL_IMAGE:figures/full_fig_p017_2.png] view at source ↗
Figure 3
Figure 3. Game graph Γ corresponding to Example 3.10, with R = {r1, r2, r3} and C = {c1, c2}. corresponding to the system 3 + x1 ≤ 1 + x1, −3 + x1 ≤ max{−3 + x1, 2 + x2}, max{−2 + x1, 1 + x2} ≤ 4 + x2. The corresponding game graph Γ is displayed in [PITH_FULL_IMAGE:figures/full_fig_p021_3.png] view at source ↗
Figures from the paper (6 more)
Figure 4
Figure 4. Figure 4: Coordinate tracking using the functional constraints and the equality relations between coordinates [PITH_FULL_IMAGE:figures/full_fig_p049_4.png]
Figure 5
Figure 5. Figure 5: Game digraph Γ from Example 5.35. Only non-zero weights are displayed. Next, we want to exploit the connection between systems of tropical inequalities and mean payoff games from Section 3.7, in particular Theorem 3.12. We need to point out, though, that the system Aye…
Figure 6
Figure 6. Figure 6: The multidigraph Θ from Example 5.45. The vertex in row ℓ and column c is v ℓ c . Clearly, the identity is an embedding of K to Θ. While trivial, let us explicitly mention that the embedding respects levels, weights of edges, and membership to bunches. We want to relat…
Figure 7
Figure 7. Figure 7: The multidigraph Φ from Example 5.48. Only non-zero weights are displayed. The relation between Γ|S and Φ is clear from the definition of Φ (or rather the discussion preceding Defini￾tion 5.46). To relate Θ and Φ, we show that the following ‘level-squeezing’ mapping fr…
Figure 8
Figure 8. Figure 8: The graphs Γ opt |S , Φ opt, and Θopt from Example 5.54. Note that by keeping only those edges of Θ whose ζ-image is present in Φ opt, the restriction ζ opt : Θopt → Φ opt of ζ is a covering projection. Obviously, ζ opt still respects bunches and preserves edge-weights…
Figure 9
Figure 9. Figure 9: Relations among certain elements of π0(u) and π0(w) from Example 6.2. They close a cycle of inequalities, which are impossible to satisfy. Consider increasing 4-tuples u, w ∈ V (S) ⊂ N 4 . Suppose for contradiction that P ′ j induces the edge (π(u), π(w)). The relation…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

111 extracted references · 10 canonical work pages

  1. [1]

    Results in Mathematics , volume=

    Functionality of box intersection graphs , author=. Results in Mathematics , volume=. 2024 , publisher=

    2024

  2. [2]

    Forum of Mathematics, Sigma , volume=

    Zarankiewicz’s problem for semilinear hypergraphs , author=. Forum of Mathematics, Sigma , volume=. 2021 , organization=

    2021

  3. [3]

    arXiv preprint arXiv:2501.04166 , year=

    Graph classes through the lens of logic , author=. arXiv preprint arXiv:2501.04166 , year=

    arXiv

  4. [4]

    2012 , publisher=

    Ne. 2012 , publisher=

    2012

  5. [5]

    An invitation to the promise constraint satisfaction problem , year =

    Krokhin, Andrei and Opr. An invitation to the promise constraint satisfaction problem , year =. doi:10.1145/3559736.3559740 , journal =

    arXiv

  6. [6]

    Garey, M. R. and Johnson, D. S. , title =. 1976 , issue_date =. doi:10.1145/321921.321926 , journal =

    arXiv 1976

  7. [7]

    arXiv preprint arXiv:2602.23503 , year=

    Spiky Rank and Its Applications to Rigidity and Circuits , author=. arXiv preprint arXiv:2602.23503 , year=

    arXiv

  8. [8]

    Combinatorics, Probability and Computing , volume=

    On graph complexity , author=. Combinatorics, Probability and Computing , volume=. 2006 , publisher=

    2006

Show all 111 references
  1. [9]

    SIAM Journal on Computing , volume =

    Chiba, Norishige and Nishizeki, Takao , title =. SIAM Journal on Computing , volume =. 1985 , doi =

    1985

  2. [10]

    Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs , url =

    Alon, Noga and Gutner, Shai , date =. Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs , url =. Algorithmica , number =. 2009 , bdsk-url-1 =. doi:10.1007/s00453-008-9204-0 , id =

    2009 doi

  3. [11]

    Journal of the ACM (JACM) , volume=

    Smallest-last ordering and clustering and graph coloring algorithms , author=. Journal of the ACM (JACM) , volume=. 1983 , publisher=

    1983

  4. [12]

    The Orthogonal Vectors Conjecture and Non-Uniform Circuit Lower Bounds , year=

    Williams, Ryan , booktitle=. The Orthogonal Vectors Conjecture and Non-Uniform Circuit Lower Bounds , year=

  5. [13]

    2004 , publisher=

    Graphs and Homomorphisms , author=. 2004 , publisher=

    2004

  6. [14]

    Annals of Pure and Applied Logic , volume=

    Structures coordinatized by indiscernible sets , author=. Annals of Pure and Applied Logic , volume=

  7. [15]

    arXiv preprint arXiv:2512.21278 , year=

    Taking model-complete cores , author=. arXiv preprint arXiv:2512.21278 , year=

    arXiv

  8. [16]

    Structures preserved by primitive actions of

    Bodirsky, Manuel and Bodor, Bertalan , journal=. Structures preserved by primitive actions of

  9. [17]

    arXiv preprint arXiv:2101.12194 , year=

    Notes on trace equivalence , author=. arXiv preprint arXiv:2101.12194 , year=

    arXiv

  10. [18]

    Combinatorica , volume=

    What must and what need not be contained in a graph of uncountable chromatic number? , author=. Combinatorica , volume=. 1984 , publisher=

    1984

  11. [19]

    Topics in Topology , editor=

    On some general properties of chromatic number , author=. Topics in Topology , editor=

  12. [20]

    Sumner, D. P. , TITLE =. The theory and applications of graphs (. 1981 , ISBN =

    1981

  13. [21]

    Gy. On. Infinite and finite sets (. 1975 , MRCLASS =

    1975

  14. [22]

    Combinatorial structures and their applications

    Problem 43 , author=. Combinatorial structures and their applications. Proceedings of the Calgary International Conference on Combinatorial Structures and Their Applications held at the University of Calgary, Calgary, Alberta, Canada, June, 1969. , editor=

    1969

  15. [23]

    Model Theory , volume=

    Infinite cliques in simple and stable graphs , author=. Model Theory , volume=. 2025 , publisher=

    2025

  16. [24]

    Infinite stable graphs with large chromatic number

    Halevi, Yatir and Kaplan, Itay and Shelah, Saharon , journal=. Infinite stable graphs with large chromatic number

  17. [25]

    Transactions of the American Mathematical Society , volume=

    Infinite stable graphs with large chromatic number , author=. Transactions of the American Mathematical Society , volume=

  18. [26]

    Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Burling graphs in graphs with large chromatic number , author=. Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2026 , organization=

    2026

  19. [27]

    2021 , publisher=

    Chudnovsky, Maria and Scott, Alex and Seymour, Paul , journal=. 2021 , publisher=

    2021

  20. [28]

    Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages=

    The Meta-Complexity of Secret Sharing , author=. Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages=

  21. [29]

    Daniel Avraham and Amir Yehudayoff , title =. Comput. Complex. , volume =. 2024 , doi =

    2024

  22. [30]

    arXiv preprint arXiv:2412.19551 , year=

    Boolean combinations of graphs , author=. arXiv preprint arXiv:2412.19551 , year=

    arXiv

  23. [31]

    Burling Graphs in Graphs with Large Chromatic Number , booktitle =

    Tara Abrishami and Marcin Brianski and James Davies and Xiying Du and Jana Masar. Burling Graphs in Graphs with Large Chromatic Number , booktitle =. 2026 , doi =

    2026

  24. [32]

    Journal of Combinatorial Theory, Series B , volume=

    Graph functionality , author=. Journal of Combinatorial Theory, Series B , volume=. 2021 , publisher=

    2021

  25. [33]

    Discrete & Computational Geometry , volume=

    On forbidden induced subgraphs for unit disk graphs , author=. Discrete & Computational Geometry , volume=. 2018 , publisher=

    2018

  26. [34]

    Journal of Combinatorial Theory, Series A , volume=

    Crossing patterns of semi-algebraic sets , author=. Journal of Combinatorial Theory, Series A , volume=. 2005 , publisher=

    2005

  27. [35]

    SIAM Journal on Discrete Mathematics , volume=

    Intersections of Graphs and -Boundedness , author=. SIAM Journal on Discrete Mathematics , volume=. 2026 , publisher=

    2026

  28. [36]

    16th Innovations in Theoretical Computer Science Conference (ITCS 2025) , pages=

    Adjacency Labeling Schemes for Small Classes , author=. 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) , pages=. 2025 , organization=

    2025

  29. [37]

    Discrete Mathematics , volume=

    Logical labeling schemes , author=. Discrete Mathematics , volume=. 2023 , publisher=

    2023

  30. [38]

    34th Computational Complexity Conference (CCC 2019) , pages=

    Equality alone does not simulate randomness , author=. 34th Computational Complexity Conference (CCC 2019) , pages=. 2019 , organization=

    2019

  31. [39]

    European Journal of Combinatorics , volume=

    Transducing paths in graph classes with unbounded shrubdepth , author=. European Journal of Combinatorics , volume=. 2025 , publisher=

    2025

  32. [40]

    Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Rankwidth meets stability , author=. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2021 , organization=

    2021

  33. [41]

    Approximation, Randomization, and Combinatorial Optimization

    Sketching Distances in Monotone Graph Classes , author=. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques , pages=

  34. [42]

    Conference on Learning Theory , pages=

    Sample complexity bounds on differentially private learning via communication complexity , author=. Conference on Learning Theory , pages=. 2014 , organization=

    2014

  35. [43]

    Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms , pages=

    Density and regularity theorems for semi-algebraic hypergraphs , author=. Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms , pages=. 2014 , organization=

    2014

  36. [44]

    Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science , pages=

    Stable graphs of bounded twin-width , author=. Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science , pages=

  37. [45]

    11th Innovations in Theoretical Computer Science Conference,

    Nathaniel Harms , title =. 11th Innovations in Theoretical Computer Science Conference,. 2020 , doi =

    2020

  38. [46]

    Randomized Communication and Implicit Graph Representations , volume =

    Harms, Nathaniel and Wild, Sebastian and Zamaraev, Viktor , year =. Randomized Communication and Implicit Graph Representations , volume =. doi:10.46298/theoretics.25.20 , journal =

    doi

  39. [47]

    Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Randomized communication and implicit representations for matrices and graphs of small sign-rank , author=. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2024 , organization=

    2024

  40. [48]

    Israel Journal of Mathematics , volume=

    Dimension-free bounds and structural results in communication complexity , author=. Israel Journal of Mathematics , volume=. 2023 , publisher=

    2023

  41. [49]

    Proceedings of the thirty-ninth annual ACM symposium on Theory of computing , pages=

    Lower bounds in communication complexity based on factorization norms , author=. Proceedings of the thirty-ninth annual ACM symposium on Theory of computing , pages=

  42. [50]

    Transactions of the American Mathematical Society , volume=

    Regularity lemmas for stable graphs , author=. Transactions of the American Mathematical Society , volume=

  43. [51]

    1991 , publisher=

    On coloring j-unit sphere graphs , author=. 1991 , publisher=

    1991

  44. [52]

    Discrete Mathematics , volume=

    Shift graphs, chromatic number and acyclic one-path orientations , author=. Discrete Mathematics , volume=. 2025 , publisher=

    2025

  45. [53]

    European Journal of Combinatorics , pages=

    A survey of degree-boundedness , author=. European Journal of Combinatorics , pages=. 2024 , publisher=

    2024

  46. [54]

    Jiang, Y. and Ne. Regular partitions of gentle graphs , JOURNAL =. 2020 , NUMBER =. doi:10.1007/s10474-020-01074-x , URL =

    2020 doi

  47. [55]

    Oriented Trees in O(k

    Bessy, St. Oriented Trees in O(k. International Workshop on Graph-Theoretic Concepts in Computer Science , pages=. 2024 , organization=

    2024

  48. [56]

    Disjunctive Programming , ISBN =

    Balas, Egon , year =. Disjunctive Programming , ISBN =. doi:10.1007/978-3-030-00148-3 , publisher =

    doi

  49. [57]

    Max-linear Systems: Theory and Algorithms , ISBN =

    Butkovič, Peter , year =. Max-linear Systems: Theory and Algorithms , ISBN =. doi:10.1007/978-1-84996-299-5 , series =

    doi

  50. [58]

    Recognizing Weakly Stable Matrices , volume =

    Butkovič, Peter and Schneider, Hans and Sergeev, Sergeĭ , year =. Recognizing Weakly Stable Matrices , volume =. SIAM Journal on Control and Optimization , publisher =. doi:10.1137/110837942 , number =

    doi

  51. [59]

    On tropical supereigenvectors , volume =

    Butkovič, Peter , year =. On tropical supereigenvectors , volume =. doi:10.1016/j.laa.2016.02.033 , journal =

    2016 doi

  52. [60]

    Applications of Mathematics , volume=

    Complete solution of tropical vector inequalities using matrix sparsification , author=. Applications of Mathematics , volume=. 2020 , publisher=

    2020

  53. [61]

    Applicationes Mathematicae , volume=

    Problems from the world surrounding perfect graphs , author=. Applicationes Mathematicae , volume=. 1987 , publisher=

    1987

  54. [62]

    International Journal of Algebra and Computation , volume=

    Tropical polyhedra are equivalent to mean payoff games , author=. International Journal of Algebra and Computation , volume=. 2012 , publisher=

    2012

  55. [63]

    Fundamenta Mathematicae , volume=

    On generalized shift graphs , author=. Fundamenta Mathematicae , volume=

  56. [64]

    The chromatic number of finite type-graphs , journal =

    Christian Avart and Bill Kay and Christian Reiher and Vojtěch Rödl , keywords =. The chromatic number of finite type-graphs , journal =. 2017 , issn =. doi:https://doi.org/10.1016/j.jctb.2016.10.004 , url =

    2017 doi

  57. [65]

    How to solve large scale deterministic games with mean payoff by policy iteration , year =

    Dhingra, Vishesh and Gaubert, St\'. How to solve large scale deterministic games with mean payoff by policy iteration , year =. Proceedings of the 1st International Conference on Performance Evaluation Methodolgies and Tools , pages =. doi:10.1145/1190095.1190110 , abstract =

  58. [66]

    and Mycielski, J

    Ehrenfeucht, A. and Mycielski, J. , title=. International Journal of Game Theory , year=. doi:10.1007/BF01768705 , url=

    doi

  59. [67]

    Proceedings of the Eleventh Southeastern Conference on Combinatorics, Graph Theory and Computing, Boca Raton, Congr

    Subtrees of directed graphs and hypergraphs , author=. Proceedings of the Eleventh Southeastern Conference on Combinatorics, Graph Theory and Computing, Boca Raton, Congr. Numer , volume=

  60. [68]

    Addario-Berry and F

    L. Addario-Berry and F. Havet and S. Thomassé , keywords =. Paths with two blocks in n -chromatic digraphs , journal =. 2007 , issn =. doi:https://doi.org/10.1016/j.jctb.2006.10.001 , url =

    2007 doi

  61. [69]

    Polynomial

    Davies, James and Yuditsky, Yelena , journal=. Polynomial

  62. [70]

    Joswig, Michael , title =

  63. [71]

    The complexity of mean payoff games on graphs , journal =

    Uri Zwick and Mike Paterson , abstract =. The complexity of mean payoff games on graphs , journal =. 1996 , issn =. doi:https://doi.org/10.1016/0304-3975(95)00188-3 , url =

    1996 doi

  64. [72]

    Complexity of colored graph covers I

    Kratochv \'i l, Jan and Proskurowski, Andrzej and Telle, Jan Arne. Complexity of colored graph covers I . C olored directed multigraphs. Graph-Theoretic Concepts in Computer Science. 1997

    1997

  65. [73]

    Pevzner, Pavel A and Tang, Haixu and Waterman, Michael S , journal=. An. 2001 , publisher=

    2001

  66. [74]

    Genome research , volume=

    De novo assembly of human genomes with massively parallel short read sequencing , author=. Genome research , volume=. 2010 , publisher=

    2010

  67. [75]

    Velvet: algorithms for de novo short read assembly using de

    Zerbino, Daniel R and Birney, Ewan , journal=. Velvet: algorithms for de novo short read assembly using de. 2008 , publisher=

    2008

  68. [76]

    International Workshop on Peer-to-Peer Systems , pages=

    Koorde: A simple degree-optimal distributed hash table , author=. International Workshop on Peer-to-Peer Systems , pages=. 2003 , organization=

    2003

  69. [77]

    A novel discrete time series representation with

    Cakiroglu, Mert Onur and Kurban, Hasan and Buxton, Elham and Dalkilic, Mehmet , journal=. A novel discrete time series representation with. 2025 , publisher=

    2025

  70. [78]

    ACM Transactions on Algorithms , volume=

    Tight bounds for monotone minimal perfect hashing , author=. ACM Transactions on Algorithms , volume=. 2025 , publisher=

    2025

  71. [79]

    uredi, Z. and Hajnal, P. and R\

    F\"uredi, Z. and Hajnal, P. and R\"odl, V. and Trotter, W. T. , TITLE =. Sets, graphs and numbers (. 1992 , ISBN =

    1992

  72. [80]

    Combinatorica , volume=

    Separating polynomial -boundedness from -boundedness , author=. Combinatorica , volume=. 2024 , publisher=

    2024

  73. [81]

    Shift graphs and lower bounds on

    Duffus, Dwight and Lefmann, Hanno and R. Shift graphs and lower bounds on. Discrete Math. , FJOURNAL =. 1995 , NUMBER =. doi:10.1016/0012-365X(93)E0139-U , URL =

    1995 doi

  74. [82]

    Theory of Graphs (Proc

    On chromatic number of infinite graphs , author=. Theory of Graphs (Proc. Colloq., Tihany, 1966) , pages=

    1966

  75. [83]

    Information and Computation , pages=

    A Hierarchy of Constant Communication Complexity , author=. Information and Computation , pages=. 2026 , publisher=

    2026

  76. [84]

    Constant-cost communication is not reducible to

    Fang, Yuting and G. Constant-cost communication is not reducible to. Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages=

  77. [85]

    Approximation, Randomization, and Combinatorial Optimization

    Equality Is Far Weaker Than Constant-Cost Communication , author=. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025) , pages=

    2025

  78. [86]

    Equality Is Far Weaker Than Constant-Cost Communication , booktitle =

    Mika G. Equality Is Far Weaker Than Constant-Cost Communication , booktitle =. 2025 , doi =

    2025

  79. [87]

    Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages=

    No complete problem for constant-cost randomized communication , author=. Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages=

  80. [88]

    ACM SIGACT News , volume=

    Guest column: Structure in communication complexity and constant-cost complexity classes , author=. ACM SIGACT News , volume=. 2024 , publisher=

    2024

  81. [89]

    Algorithmic Aspects of Regular Graph Covers with Applications to Planar Graphs , booktitle =

    Jir. Algorithmic Aspects of Regular Graph Covers with Applications to Planar Graphs , booktitle =. 2014 , doi =

    2014

  82. [90]

    Ne. The. Journal of Combinatorial Theory, Series B , volume=. 1976 , publisher=

    1976

  83. [91]

    Gurvich and A.V

    V.A. Gurvich and A.V. Karzanov and L.G. Khachivan , abstract =. Cyclic games and an algorithm to find minimax cycle means in directed graphs , journal =. 1988 , issn =. doi:https://doi.org/10.1016/0041-5553(88)90012-2 , url =

    1988 doi

  84. [92]

    45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) , pages =

    Fijalkow, Nathana\". 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) , pages =. 2020 , volume =

    2020

  85. [93]

    46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) , pages =

    Dorfman, Dani and Kaplan, Haim and Zwick, Uri , title =. 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) , pages =. 2019 , volume =

    2019

  86. [94]

    Proceedings of the American Mathematical Society , volume=

    On the chromatic number of subgraphs of a given graph , author=. Proceedings of the American Mathematical Society , volume=

  87. [95]

    Problems and results in combinatorial analysis , author=. Colloq. Internat. Theor. Combin. Rome , pages=

  88. [96]

    Combinatorics, Probability and Computing , volume=

    Triangle-free subgraphs with large fractional chromatic number , author=. Combinatorics, Probability and Computing , volume=. 2022 , publisher=

    2022

  89. [97]

    A survey of ‐boundedness , volume =

    Scott, Alex and Seymour, Paul , year =. A survey of ‐boundedness , volume =. Journal of Graph Theory , publisher =

  90. [98]

    Subgraphs of

    Mohar, Bojan and Wu, Hehui , year =. Subgraphs of. The Art of Discrete and Applied Mathematics , publisher =

  91. [99]

    Uma conjectura de

    Enju, Rodrigo Aparecido , year=. Uma conjectura de

  92. [100]

    G. On an. 2018 , note =

    2018

  93. [101]

    On a Clique Game and the

    Pettie, Seth and Tardos, G. On a Clique Game and the. Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2026 , organization=

    2026

  94. [102]

    2017 , type =

    Esperet, Louis , title=. 2017 , type =

    2017

  95. [103]

    Journal of Combinatorial Theory, Series B , volume=

    Reuniting -boundedness with polynomial -boundedness , author=. Journal of Combinatorial Theory, Series B , volume=. 2026 , publisher=

    2026

  96. [104]

    Geometric Algorithms and Combinatorial Optimization , ISBN =

    Gr\". Geometric Algorithms and Combinatorial Optimization , ISBN =. doi:10.1007/978-3-642-78240-4 , journal =

    doi

  97. [105]

    and Jain, Sanjay and Khoussainov, Bakhadyr and Li, Wei and Stephan, Frank , year =

    Calude, Cristian S. and Jain, Sanjay and Khoussainov, Bakhadyr and Li, Wei and Stephan, Frank , year =. Deciding parity games in quasipolynomial time , url =. doi:10.1145/3055399.3055409 , booktitle =

  98. [106]

    Proceedings of the forty-sixth annual ACM symposium on Theory of computing , pages=

    Faster all-pairs shortest paths via circuit complexity , author=. Proceedings of the forty-sixth annual ACM symposium on Theory of computing , pages=

  99. [107]

    SIAM Journal on Discrete Mathematics , volume=

    Tropical Linear Regression and Mean Payoff Games: Or, How to Measure the Distance to Equilibria , author=. SIAM Journal on Discrete Mathematics , volume=. 2022 , publisher=

    2022

  100. [108]

    48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) , year=

    Lower Bounds on Dynamic Programming for Maximum Weight Independent Set , author=. 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) , year=

    2021

  101. [109]

    SIAM Journal on Discrete Mathematics , volume=

    Tropicalizing the simplex algorithm , author=. SIAM Journal on Discrete Mathematics , volume=. 2015 , publisher=

    2015

  102. [110]

    Discrete Applied Mathematics , volume=

    A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games , author=. Discrete Applied Mathematics , volume=. 2007 , publisher=

    2007

  103. [111]

    Linear Algebra and its Applications , volume=

    Max-algebra: the linear algebra of combinatorics? , author=. Linear Algebra and its Applications , volume=. 2003 , publisher=

    2003

Pith tools

Reviewed July 30, 2026 · model on record in the stance chip above.