Saddle-Point Asymptotics for Chromatic and Tutte Polynomial Evaluations of Complete Multipartite Graphs

Zhiyang Sun

arxiv: 2605.04006 · v1 · submitted 2026-05-05 · 🧮 math.CO

Saddle-Point Asymptotics for Chromatic and Tutte Polynomial Evaluations of Complete Multipartite Graphs

Zhiyang Sun This is my paper

Pith reviewed 2026-05-07 15:09 UTC · model grok-4.3

classification 🧮 math.CO

keywords saddle-point asymptoticschromatic polynomialTutte polynomialcomplete multipartite graphsacyclic orientationsKotesovec conjectureanalytic combinatoricsGamma integral

0 comments

The pith

Complete multipartite graphs admit exact Gamma-type integral representations for acyclic orientations that extend to negative chromatic evaluations and enable saddle-point asymptotics proving Kotesovec's fixed-column conjecture.

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

The paper develops saddle-point asymptotics for chromatic and Tutte polynomial evaluations of complete multipartite graphs using an exact Gamma-type integral representation for acyclic orientation counts. This representation extends via Gamma weights to the negative chromatic axis and supports an analytic-combinatorics-in-several-variables approach for fixed blow-ups. It proves Kotesovec's fixed-column conjecture for OEIS sequence A267383 with arbitrary fixed numbers of parts, supplies fixed-p asymptotics on the Tutte axis, establishes all-order expansions in polynomial windows for equal part sizes, and derives logarithmic asymptotics for related partition-sum sequences through a quadratic-energy model. A reader would care because the results deliver precise growth rates and higher-order corrections for quantities that count colorings and orientations, resolving conjectures on tabulated integer sequences.

Core claim

What carries the argument

The exact Gamma-type integral representation for acyclic orientation counts, extended by Gamma weights to the negative chromatic axis, which carries the saddle-point analysis and all subsequent expansions.

If this is right

Kotesovec's fixed-column conjecture holds for sequence A267383 with any fixed number of parts.
Fixed-p asymptotics are available along the Tutte axis for chromatic evaluations.
Chromatic evaluations of fixed graph blow-ups admit an analytic-combinatorics-in-several-variables framework.
Unconditional fixed-base families of evaluations reduce to balanced Turan graphs.
All-order expansions exist for equal-size parts throughout every fixed polynomial window, with explicit cubic-scale corrections.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The saddle-point methods may adapt to asymptotic counting for orientations or colorings on other dense graph families with comparable symmetry.
The quadratic-energy partition model could inform probabilistic limits on orientation distributions in random multipartite graphs.
The reduction to balanced Turan graphs suggests possible extensions to extremal questions on the growth of chromatic polynomials in dense graphs.
Higher-order terms in the expansions could refine numerical estimates for large instances in computational enumeration.

Load-bearing premise

The exact Gamma-type integral representation for acyclic orientation counts holds and extends to the negative chromatic axis for complete multipartite graphs.

What would settle it

Direct computation of acyclic orientation counts for a family of complete multipartite graphs with growing part sizes, followed by numerical comparison against the leading saddle-point asymptotic formula to check agreement in the predicted growth rate.

read the original abstract

We develop a saddle-point theory for acyclic orientations and negative chromatic evaluations of complete multipartite graphs, with applications to OEIS A267383, A372326, A372084, A372395, and A370613. The main tool is an exact Gamma-type integral representation for acyclic orientation counts and its Gamma-weighted extension to the negative chromatic axis. We prove Kotesovec's fixed-column conjecture for A267383 for arbitrary fixed numbers of parts, give the corresponding fixed-p Tutte-axis asymptotics, develop an analytic-combinatorics-in-several-variables framework for chromatic evaluations of fixed graph blow-ups, and give unconditional fixed-base families reducible to balanced Turan graphs. In the product regimes we prove fixed part-size and finite-profile expansions, and for equal-size parts we obtain an all-order expansion throughout every fixed polynomial window, including explicit corrections through the cubic scale. Finally, we prove logarithmic asymptotics for the partition-sum sequences A372395 and A370613 via a quadratic-energy partition model, a growing-window comparison for the Stirling-transform factors, and a random-permutation far-tail bound.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper proves Kotesovec's conjecture on A267383 asymptotics for fixed-part complete multipartite graphs and supplies explicit saddle-point expansions, but everything rests on an exact Gamma integral whose derivation and domain need close checking.

read the letter

The core advance is a saddle-point treatment of chromatic and Tutte evaluations on complete multipartite graphs that settles the fixed-column case of Kotesovec's conjecture for A267383 and gives matching fixed-p asymptotics on the Tutte axis. The same machinery produces all-order expansions (through cubic corrections) when part sizes are equal, plus finite-profile expansions in product regimes and logarithmic asymptotics for the partition-sum sequences via a quadratic-energy model. The analytic-combinatorics-in-several-variables setup for fixed blow-ups is also new in this setting and cleanly reduces some families to balanced Turán graphs. These are concrete, checkable results rather than general existence statements. The paper does a reasonable job keeping the contour choices and Stirling-transform comparisons explicit enough that a reader can follow the logic once the integral representation is granted. The weakest link is precisely that representation: an exact Gamma-type integral for acyclic orientations that is extended to the negative chromatic axis. The abstract presents it as the main tool without showing the derivation or the precise domain restrictions for multipartite graphs, so any hidden assumption there would affect the saddle contours, the fixed-column proofs, and the error terms. If the full text supplies a self-contained justification and verifies the extension on a few small cases, the rest of the argument looks solid. Minor points include the usual need for uniform error bounds across the growing windows and a clearer statement of how the random-permutation tail bound interacts with the quadratic model. This is specialized work aimed at people who already use saddle-point methods on graph polynomials or track OEIS conjectures in enumeration. A combinatorialist or analytic combinatorist working on chromatic polynomials or multipartite graphs will find usable expansions and a new proof technique. It is worth sending to a serious referee; the conjecture resolution and the explicit expansions give it enough substance to justify review time even if the integral step requires extra scrutiny.

Referee Report

1 major / 1 minor

Summary. The manuscript develops saddle-point asymptotics for chromatic and Tutte polynomial evaluations of complete multipartite graphs. The central tool is an exact Gamma-type integral representation for acyclic orientation counts, extended via Gamma-weighting to the negative chromatic axis. Applications include a proof of Kotesovec's fixed-column conjecture for OEIS A267383 for arbitrary fixed numbers of parts, fixed-p Tutte-axis asymptotics, an ACV framework for chromatic evaluations of fixed graph blow-ups, unconditional fixed-base families reducible to balanced Turán graphs, fixed part-size and finite-profile expansions in product regimes, all-order expansions (with cubic corrections) for equal-size parts in every fixed polynomial window, and logarithmic asymptotics for partition-sum sequences A372395 and A370613 via quadratic-energy models, Stirling-transform comparisons, and random-permutation tail bounds.

Significance. If the Gamma-type integral representation holds exactly and extends to the claimed regimes, the results would resolve a conjecture, supply explicit asymptotic expansions for multiple OEIS sequences, and advance analytic combinatorics in several variables for graph polynomials on blow-ups and multipartite graphs. The all-order expansions and partition-sum analysis are notable strengths.

major comments (1)

[Abstract] Abstract and introduction: the exact Gamma-type integral representation for acyclic orientation counts (and its Gamma-weighted extension to the negative chromatic axis for complete multipartite graphs) is asserted as the main tool without a self-contained derivation, error analysis, or verification steps; this is load-bearing for the saddle-point contours, fixed-column proofs, fixed-p asymptotics, and all-order expansions, as any domain restriction would propagate directly into the claimed results.

minor comments (1)

[Abstract] Abstract: the list of OEIS sequences and their precise relation to the graph polynomials could be clarified with one additional sentence for readers unfamiliar with the enumeration context.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for highlighting the central role of the Gamma-type integral representation. We address the major comment below and will revise the paper accordingly to strengthen the presentation.

read point-by-point responses

Referee: [Abstract] Abstract and introduction: the exact Gamma-type integral representation for acyclic orientation counts (and its Gamma-weighted extension to the negative chromatic axis for complete multipartite graphs) is asserted as the main tool without a self-contained derivation, error analysis, or verification steps; this is load-bearing for the saddle-point contours, fixed-column proofs, fixed-p asymptotics, and all-order expansions, as any domain restriction would propagate directly into the claimed results.

Authors: We agree that a self-contained derivation is necessary for the load-bearing claims. The manuscript introduces the exact Gamma-type integral representation for acyclic orientation counts of complete multipartite graphs and its Gamma-weighted extension, but the referee is correct that the current version does not include a full derivation, error bounds, or explicit verification steps in the abstract and introduction. In the revised manuscript we will add a dedicated subsection (new Section 2) that derives the representation from first principles using the integral form of the Gamma function applied to the product formula for the number of acyclic orientations, followed by a rigorous error analysis for the contour deformation and an explicit verification for small multipartite graphs that confirms the extension to the negative chromatic axis holds without domain restrictions in the regimes used for the saddle-point analysis. This will directly support the fixed-column proofs, fixed-p asymptotics, and all-order expansions. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained around an asserted integral representation

full rationale

The paper introduces an exact Gamma-type integral representation for acyclic orientation counts as its main tool and extends it to the negative chromatic axis, then applies saddle-point analysis to derive asymptotics, prove the Kotesovec conjecture for fixed columns, and obtain expansions for chromatic/Tutte evaluations. No quoted step reduces a claimed prediction or uniqueness result to a fitted parameter, self-definition, or load-bearing self-citation chain; the representation is treated as an independent starting point whose validity is external to the subsequent saddle-point contours and logarithmic asymptotics. The derivation chain therefore remains non-circular by the enumerated criteria.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Full text unavailable; abstract identifies the Gamma-type integral representation as the central tool but provides no explicit free parameters, additional axioms, or invented entities.

axioms (1)

domain assumption Existence of an exact Gamma-type integral representation for acyclic orientation counts that extends to negative chromatic evaluations
Stated as the main tool in the abstract for developing the saddle-point theory.

pith-pipeline@v0.9.0 · 5489 in / 1292 out tokens · 88267 ms · 2026-05-07T15:09:03.921964+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

[1]

Andrews,The Theory of Partitions, Cambridge Mathematical Library, Cambridge University Press, first paperback edition ed

George E. Andrews,The Theory of Partitions, Cambridge University Press, 1998,https: //doi.org/10.1017/CBO9780511608650

work page doi:10.1017/cbo9780511608650 1998
[2]

Bender,Central and local limit theorems applied to asymptotic enumeration, Journal of Combinatorial Theory, Series A 15 (1973), 91–111,https://doi.org/10.1016/ 0097-3165(73)90038-1

Edward A. Bender,Central and local limit theorems applied to asymptotic enumeration, Journal of Combinatorial Theory, Series A 15 (1973), 91–111,https://doi.org/10.1016/ 0097-3165(73)90038-1

work page 1973
[3]

Bela Bollobas,Modern Graph Theory, Graduate Texts in Mathematics 184, Springer, 1998, https://doi.org/10.1007/978-1-4612-0619-4

work page doi:10.1007/978-1-4612-0619-4 1998
[4]

Cameron, C

Peter J. Cameron, C. A. Glass, Kamilla Rekv´ enyi, and R. U. Schumacher,Acyclic orientations and poly-Bernoulli numbers, arXiv preprint arXiv:1412.3685, 2014,https: //doi.org/10.48550/arXiv.1412.3685

work page doi:10.48550/arxiv.1412.3685 2014
[5]

Walter Carballosa, Francisco A. Reyes, and Jessica Khera,Encoding and enumerat- ing acyclic orientations of graphs, Utilitas Mathematica 125 (2025), 21–41; see also arXiv:2303.09021v2,https://doi.org/10.61091/um125-02

work page doi:10.61091/um125-02 2025
[6]

Reidel, 1974,https://doi.org/10.1007/ 978-94-010-2196-8

Louis Comtet,Advanced Combinatorics, D. Reidel, 1974,https://doi.org/10.1007/ 978-94-010-2196-8

work page 1974
[7]

Philippe Flajolet and Robert Sedgewick,Analytic Combinatorics, Cambridge University Press, 2009,https://doi.org/10.1017/CBO9780511801655

work page doi:10.1017/cbo9780511801655 2009
[8]

Boris L. Granovsky, Dudley Stark, and Michael Erlihson,Meinardus’ theorem on weighted partitions: extensions and a probabilistic proof, Advances in Applied Mathematics 41 (2008), 307–328,https://doi.org/10.1016/j.aam.2007.11.001

work page doi:10.1016/j.aam.2007.11.001 2008
[9]

Boris L. Granovsky and Dudley Stark,Developments in the Khintchine–Meinardus prob- abilistic method for asymptotic enumeration, Electronic Journal of Combinatorics 22(4) (2015), Paper P4.32,https://doi.org/10.37236/4581

work page doi:10.37236/4581 2015
[10]

org/10.1090/S0002-9947-1983-0712251-1

Curtis Greene and Thomas Zaslavsky,On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-Radon partitions, and orientations of graphs, Transactions of the American Mathematical Society 280 (1983), 97–126,https://doi. org/10.1090/S0002-9947-1983-0712251-1

work page doi:10.1090/s0002-9947-1983-0712251-1 1983
[11]

G. H. Hardy and S. Ramanujan,Asymptotic formulae in combinatory analysis, Proceedings of the London Mathematical Society s2-17 (1918), 75–115,https://doi.org/10.1112/ plms/s2-17.1.75. 40

work page 1918
[12]

Jessica Khera and Erik Lundberg,The distribution of the length of the longest path in random acyclic orientations of a complete bipartite graph, Annals of Combinatorics 29 (2025), 1177–1209,https://doi.org/10.1007/s00026-025-00741-6

work page doi:10.1007/s00026-025-00741-6 2025
[13]

Jessica Khera, Erik Lundberg, and Stephen Melczer,Asymptotic enumeration of lonesum matrices, Advances in Applied Mathematics 123 (2021), Article 102118,https://doi.org/ 10.1016/j.aam.2020.102118

work page doi:10.1016/j.aam.2020.102118 2021
[14]

Erik Lundberg, Elisabeth Rodriguez, and Aiden Corcoran,Asymptotic enumeration of acyclic orientations on complete multipartite graphs, conference abstract (unpub- lished), Florida Atlantic University, 2026,https://www.math.fau.edu/combinatorics/ abstracts/cocoran-57-1.pdf(accessed May 2, 2026)

work page 2026
[15]

OEIS Foundation Inc.,A267383: number of acyclic orientations of the Tur´ an graphT(n, k), https://oeis.org/A267383(accessed May 2, 2026)

work page 2026
[16]

OEIS Foundation Inc.,A370613: acyclic orientations over complete multipartite graphs with distinct part sizes,https://oeis.org/A370613(accessed May 2, 2026)

work page 2026
[17]

OEIS Foundation Inc.,A372084: main diagonalA372326(n, n) =A267383(n 2, n),https: //oeis.org/A372084(accessed May 2, 2026)

work page 2026
[18]

OEIS Foundation Inc.,A372326: number of acyclic orientations ofT(kn, n),https:// oeis.org/A372326(accessed May 2, 2026)

work page 2026
[19]

OEIS Foundation Inc.,A372395: sum of acyclic orientations over complete multipartite graphs,https://oeis.org/A372395(accessed May 2, 2026)

work page 2026
[20]

Wilson, and Stephen Melczer,Analytic Combinatorics in Several Variables, second edition, Cambridge University Press, 2024,https://doi.org/10.1017/ 9781108874144

Robin Pemantle, Mark C. Wilson, and Stephen Melczer,Analytic Combinatorics in Several Variables, second edition, Cambridge University Press, 2024,https://doi.org/10.1017/ 9781108874144

work page 2024
[21]

Stanley,Acyclic orientations of graphs, Discrete Mathematics 5 (1973), 171–178, https://doi.org/10.1016/0012-365X(73)90108-8

Richard P. Stanley,Acyclic orientations of graphs, Discrete Mathematics 5 (1973), 171–178, https://doi.org/10.1016/0012-365X(73)90108-8

work page doi:10.1016/0012-365x(73)90108-8 1973
[22]

Joyal and R

Richard P. Stanley,A symmetric function generalization of the chromatic polynomial of a graph, Advances in Mathematics 111 (1995), 166–194,https://doi.org/10.1006/aima. 1995.1020

work page doi:10.1006/aima 1995
[23]

Stanley , title =

Richard P. Stanley,Enumerative Combinatorics, Volume 1, second edition, Cambridge University Press, 2011,https://doi.org/10.1017/CBO9781139058520

work page doi:10.1017/cbo9781139058520 2011
[24]

Maitland Wright,Asymptotic partition formulae: II

E. Maitland Wright,Asymptotic partition formulae: II. Weighted partitions, Proceedings of the London Mathematical Society s2-36 (1934), 117–141,https://doi.org/10.1112/ plms/s2-36.1.117. 41

work page 1934

[1] [1]

Andrews,The Theory of Partitions, Cambridge Mathematical Library, Cambridge University Press, first paperback edition ed

George E. Andrews,The Theory of Partitions, Cambridge University Press, 1998,https: //doi.org/10.1017/CBO9780511608650

work page doi:10.1017/cbo9780511608650 1998

[2] [2]

Bender,Central and local limit theorems applied to asymptotic enumeration, Journal of Combinatorial Theory, Series A 15 (1973), 91–111,https://doi.org/10.1016/ 0097-3165(73)90038-1

Edward A. Bender,Central and local limit theorems applied to asymptotic enumeration, Journal of Combinatorial Theory, Series A 15 (1973), 91–111,https://doi.org/10.1016/ 0097-3165(73)90038-1

work page 1973

[3] [3]

Bela Bollobas,Modern Graph Theory, Graduate Texts in Mathematics 184, Springer, 1998, https://doi.org/10.1007/978-1-4612-0619-4

work page doi:10.1007/978-1-4612-0619-4 1998

[4] [4]

Cameron, C

Peter J. Cameron, C. A. Glass, Kamilla Rekv´ enyi, and R. U. Schumacher,Acyclic orientations and poly-Bernoulli numbers, arXiv preprint arXiv:1412.3685, 2014,https: //doi.org/10.48550/arXiv.1412.3685

work page doi:10.48550/arxiv.1412.3685 2014

[5] [5]

Walter Carballosa, Francisco A. Reyes, and Jessica Khera,Encoding and enumerat- ing acyclic orientations of graphs, Utilitas Mathematica 125 (2025), 21–41; see also arXiv:2303.09021v2,https://doi.org/10.61091/um125-02

work page doi:10.61091/um125-02 2025

[6] [6]

Reidel, 1974,https://doi.org/10.1007/ 978-94-010-2196-8

Louis Comtet,Advanced Combinatorics, D. Reidel, 1974,https://doi.org/10.1007/ 978-94-010-2196-8

work page 1974

[7] [7]

Philippe Flajolet and Robert Sedgewick,Analytic Combinatorics, Cambridge University Press, 2009,https://doi.org/10.1017/CBO9780511801655

work page doi:10.1017/cbo9780511801655 2009

[8] [8]

Boris L. Granovsky, Dudley Stark, and Michael Erlihson,Meinardus’ theorem on weighted partitions: extensions and a probabilistic proof, Advances in Applied Mathematics 41 (2008), 307–328,https://doi.org/10.1016/j.aam.2007.11.001

work page doi:10.1016/j.aam.2007.11.001 2008

[9] [9]

Boris L. Granovsky and Dudley Stark,Developments in the Khintchine–Meinardus prob- abilistic method for asymptotic enumeration, Electronic Journal of Combinatorics 22(4) (2015), Paper P4.32,https://doi.org/10.37236/4581

work page doi:10.37236/4581 2015

[10] [10]

org/10.1090/S0002-9947-1983-0712251-1

Curtis Greene and Thomas Zaslavsky,On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-Radon partitions, and orientations of graphs, Transactions of the American Mathematical Society 280 (1983), 97–126,https://doi. org/10.1090/S0002-9947-1983-0712251-1

work page doi:10.1090/s0002-9947-1983-0712251-1 1983

[11] [11]

G. H. Hardy and S. Ramanujan,Asymptotic formulae in combinatory analysis, Proceedings of the London Mathematical Society s2-17 (1918), 75–115,https://doi.org/10.1112/ plms/s2-17.1.75. 40

work page 1918

[12] [12]

Jessica Khera and Erik Lundberg,The distribution of the length of the longest path in random acyclic orientations of a complete bipartite graph, Annals of Combinatorics 29 (2025), 1177–1209,https://doi.org/10.1007/s00026-025-00741-6

work page doi:10.1007/s00026-025-00741-6 2025

[13] [13]

Jessica Khera, Erik Lundberg, and Stephen Melczer,Asymptotic enumeration of lonesum matrices, Advances in Applied Mathematics 123 (2021), Article 102118,https://doi.org/ 10.1016/j.aam.2020.102118

work page doi:10.1016/j.aam.2020.102118 2021

[14] [14]

Erik Lundberg, Elisabeth Rodriguez, and Aiden Corcoran,Asymptotic enumeration of acyclic orientations on complete multipartite graphs, conference abstract (unpub- lished), Florida Atlantic University, 2026,https://www.math.fau.edu/combinatorics/ abstracts/cocoran-57-1.pdf(accessed May 2, 2026)

work page 2026

[15] [15]

OEIS Foundation Inc.,A267383: number of acyclic orientations of the Tur´ an graphT(n, k), https://oeis.org/A267383(accessed May 2, 2026)

work page 2026

[16] [16]

OEIS Foundation Inc.,A370613: acyclic orientations over complete multipartite graphs with distinct part sizes,https://oeis.org/A370613(accessed May 2, 2026)

work page 2026

[17] [17]

OEIS Foundation Inc.,A372084: main diagonalA372326(n, n) =A267383(n 2, n),https: //oeis.org/A372084(accessed May 2, 2026)

work page 2026

[18] [18]

OEIS Foundation Inc.,A372326: number of acyclic orientations ofT(kn, n),https:// oeis.org/A372326(accessed May 2, 2026)

work page 2026

[19] [19]

OEIS Foundation Inc.,A372395: sum of acyclic orientations over complete multipartite graphs,https://oeis.org/A372395(accessed May 2, 2026)

work page 2026

[20] [20]

Wilson, and Stephen Melczer,Analytic Combinatorics in Several Variables, second edition, Cambridge University Press, 2024,https://doi.org/10.1017/ 9781108874144

Robin Pemantle, Mark C. Wilson, and Stephen Melczer,Analytic Combinatorics in Several Variables, second edition, Cambridge University Press, 2024,https://doi.org/10.1017/ 9781108874144

work page 2024

[21] [21]

Stanley,Acyclic orientations of graphs, Discrete Mathematics 5 (1973), 171–178, https://doi.org/10.1016/0012-365X(73)90108-8

Richard P. Stanley,Acyclic orientations of graphs, Discrete Mathematics 5 (1973), 171–178, https://doi.org/10.1016/0012-365X(73)90108-8

work page doi:10.1016/0012-365x(73)90108-8 1973

[22] [22]

Joyal and R

Richard P. Stanley,A symmetric function generalization of the chromatic polynomial of a graph, Advances in Mathematics 111 (1995), 166–194,https://doi.org/10.1006/aima. 1995.1020

work page doi:10.1006/aima 1995

[23] [23]

Stanley , title =

Richard P. Stanley,Enumerative Combinatorics, Volume 1, second edition, Cambridge University Press, 2011,https://doi.org/10.1017/CBO9781139058520

work page doi:10.1017/cbo9781139058520 2011

[24] [24]

Maitland Wright,Asymptotic partition formulae: II

E. Maitland Wright,Asymptotic partition formulae: II. Weighted partitions, Proceedings of the London Mathematical Society s2-36 (1934), 117–141,https://doi.org/10.1112/ plms/s2-36.1.117. 41

work page 1934