Lattice Gases and Antiferromagnetic Potts Models — Question 5

Definitions and mathematical statement

The supplied excerpt does not define the quantity $C_{\mathrm{opt}}(\Delta)$, the graph-dependent function of $q$ being bounded, or the admissible class of graphs. Consequently, a complete mathematical formulation cannot be recovered from this record alone. The following preserves the questions and qualifications without supplying these missing hypotheses.

For a finite graph $G$, when its degree convention has been specified, its maximum degree is $\Delta(G)=\max_{v\in V(G)}\deg_G(v)$. For a graph with at least two vertices, its second-largest degree is the second entry in the nonincreasing list of vertex degrees, counted with multiplicity. The excerpt does not specify whether loops or multiple edges are permitted, nor does it define the graph parameter called "max flow." A nonnegative bound $f(t)$ is sublinear in a parameter $t$ if $f(t)/t\to0$ as $t\to\infty$.

1. (a) Determine the quantity denoted by $C_{\mathrm{opt}}(\Delta)$, described in the source as the sharp bound. Does $2\Delta$ give a valid bound? Is \[ C_{\mathrm{opt}}(3)=3? \] What bounds can be obtained using regions of the complex $q$-plane other than discs centered at $q=0$? The excerpt does not specify the defining property of these regions, the function to which they apply, or whether disc boundaries are included.

2. (b) Can the dependence on second-largest degree in the bound under discussion be replaced by dependence on "max flow"? The source explicitly refers to $[\mathrm{Sokal\_00a},\ \text{Section }7]$ for details; those details are absent from the supplied record.

3. (c) Can a sublinear bound be obtained for suitable subclasses of graphs? The source gives the following subclass-specific qualifications.
   • A theta graph $\Theta_{s_1,\ldots,s_p}$ consists of two endvertices connected by $p$ internally disjoint paths of lengths $s_1,\ldots,s_p$. The source reports an affirmative answer for these graphs, with a bound of order $p/\log p$, attributed to $[\mathrm{Brown\_et\_al}]$. The excerpt does not provide the precise inequality, its constants, or its uniformity in the path lengths.
   • For series-parallel graphs, Sokal conjectures an affirmative answer for maximum degree, again with the stated scale $p/\log p$, and a negative answer for second-largest degree or max flow. The symbol $p$ is not defined for general series-parallel graphs in the excerpt. The source also states that Sokal was then trying to prove these claims; this is a historical qualification from the supplied 2000 source.
   • For planar graphs, the source describes the question as open, without specifying a sharper subclass-dependent formulation.

The reported theta-graph result, the series-parallel conjectures, and the planar open-question description are supplied source assertions, not independently verified mathematical or literature assessments.

Short English statement

Sokal's Question 5 asks for sharp graph-parameter bounds, possible replacements of second-largest degree by max flow, and sublinear bounds for special graph classes. The excerpt reports a theta-graph bound, states conjectures for series-parallel graphs, and describes the planar case as open. It omits the definition of the bound and its underlying mathematical object, so a complete precise statement requires additional source context.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $800574$, exact source problem code catalogue entry, titled "Lattice Gases and Antiferromagnetic Potts Models --- Question 5." The record attributes the problem to Sokal, with proposed year 2000, and supplies the status label "open." This label is registry metadata, not an independently verified current status. The supplied upstream revision is d371ee917ac9647fbb06cd6fc529deec6f3dda82.
• Sokal, A Personal List of Unsolved Problems Concerning Lattice Gases and Antiferromagnetic Potts Models (2000), Question 5. Supplied source URL: https://arxiv.org/abs/cond-mat/0004231. The record states "Accessed: 2026-10-16" and extraction method arxiv_latex; these are supplied provenance statements, not a claim of independent access or verification.
• The excerpt cites $[\mathrm{Sokal\_00a},\ \text{Section }7]$ for the proposed max-flow improvement. The supplied record does not include a full bibliographic entry or a separate link for this reference key.
• The excerpt attributes the theta-graph bound of order $p/\log p$ to $[\mathrm{Brown\_et\_al}]$. The supplied record does not include authors' full names, a title, publication details, or a link for this reference key.