The random graph ideal and fractional coloring

Introduction

Submeasure representations are a fundamental tool in the study of definable ideals on countable sets. Classical theorems of Mazur [27] and Solecki [30] provide representations by lower semicontinuous submeasures for $F_\sigma$ ideals and analytic $P$-ideals, respectively. These representations lead to the distinction between pathology and nonpathology, studied in particular by Farah [12]. A submeasure is nonpathological if it is a supremum of measures; an $F_\sigma$ ideal is nonpathological if it admits such a representation by a nonpathological submeasure, and pathological otherwise. We recall the precise definitions in § 2.

For analytic $P$-ideals, Hrušák’s measure dichotomy yields a characterization of nonpathology through the Katětov order [20 Corollary 5.6]. More recent work has focused on pathology for $F_\sigma$ ideals and its connections with representations in Banach spaces [26, 24], following earlier work on representations of analytic $P$-ideals [5, 4]. These results motivate the search for combinatorial criteria that distinguish pathological from nonpathological $F_\sigma$ ideals.

The random graph ideal $\mathcal{R}$, generated by the cliques and independent sets of the countable random graph, is a natural example in this setting. It is a tall $F_\sigma$ ideal closely connected to Ramsey properties and the Katětov order [18, 20]; see also [8] for recent work on Ramsey properties of ideals. A theorem of Hrušák, Meza-Alcántara, Thümmel and Uzcátegui shows that every tall $F_\sigma$ ideal has a positive restriction above $\mathcal{R}$ in the Katětov order [18].

López-Abad, Olmos-Prieto and Uzcátegui-Aylwin asked whether $\mathcal{R}$ is pathological [24 Question 5.19]. We answer this question affirmatively by constructing a positive hereditarily pathological restriction: every further positive restriction of this witness is pathological. Together with a positive restriction isomorphic to the nonpathological ideal $\mathcal{E}\mathcal{D}_{\mathrm{fin}}$, this gives the two local behaviors of Corollary 3.9.

The pathological witness is an induced disjoint union of finite Kneser graphs. Their unbounded chromatic numbers and independent star covers of uniformly positive density satisfy the block criterion of Martínez, Meza-Alcántara and Uzcátegui [26 Theorem 3.8], which also applies on every positive restriction of the witness. For the nonpathological restriction, universality gives an induced copy of a disjoint union of finite complete graphs of increasing sizes, whose homogeneous-set ideal is isomorphic to $\mathcal{E}\mathcal{D}_{\mathrm{fin}}$ [26 Examples 3.5 and 4.5]. Proposition 3.10 also shows that a positive hereditarily pathological restriction of $\mathcal{R}$ lies above Solecki’s ideal in the Katětov order, connecting the Kneser construction with the ideal appearing in Hrušák’s measure dichotomy.

We use covering representations to prove in Theorem 4.7 that every $F_\sigma$ ideal admitting a proper nonpathological $F_\sigma$ extension has a least such extension.

To describe the construction, let $\mathcal{I}$ be a proper $F_\sigma$ ideal on $V$. Choose a compact hereditary family $\mathcal{C} \subseteq2^V$ containing the singletons and generating $\mathcal{I}$; such a family exists for every $F_\sigma$ ideal. Write $\varphi_{\mathcal{C}}(A)$ for the least number of members of $\mathcal{C}$ covering $A$, with value $\infty$ when no finite cover exists. The nonpathological envelope $\widehat{\varphi}_{\mathcal{C}}$ is the supremum of all measures dominated by $\varphi_{\mathcal{C}}$. Then

is the least nonpathological $F_\sigma$ extension of $\mathcal{I}$ when a proper such extension exists, and equals $\mathcal{P}(V)$ otherwise. In particular, $\mathcal{J}_{\mathcal{I}}$ depends only on $\mathcal{I}$, not on the choice of $\mathcal{C}$.

To prove that this extension is the least one, we compare the covering envelope with any nonpathological representation of an extension of $\mathcal{I}$. If $\widehat{\varphi}_{\mathcal{C}}(A)<\infty$, classical finite covering duality [9 Theorem 2.1] and compactness give a probability on the generators contained in $A$ such that every vertex of $A$ is covered with a uniformly positive probability. This covering bound shows that every nonpathological lower semicontinuous submeasure that is finite on the generators is also finite on $A$.

Filipów and Tryba [14 Theorem 11.2] and, independently, Figueroa-Sierra and Hrušák [13 Corollary 6.1.2] proved that every nonpathological $F_\sigma$ ideal is an intersection of summable ideals. Combining this representation with the least-extension theorem, we identify $\mathcal{J}_{\mathcal{I}}$ with the intersection of all proper summable extensions of $\mathcal{I}$. Corollary 4.10 also identifies it with the intersection of all matrix ideals containing $\mathcal{I}$. Consequently, for an $F_\sigma$ ideal, being nonpathological, being an intersection of summable ideals, and being an intersection of matrix ideals are equivalent conditions. This answers both converses in [14 Question 11.6].

Corollary 4.11 shows that every nonpathological analytic $P$-ideal containing $\mathcal{I}$ also contains $\mathcal{J}_{\mathcal{I}}$. In particular, every $F_\sigma$ ideal representable by unconditional convergence in a Banach space is also representable by bounded finite subsums, answering [24 Question 2.4].

For a countable graph $H$, the covering submeasure associated with the family of independent sets is $\varphi_{\chi}(A)=\chi(H[A])$. Define the fractional submeasure by

Finite covering duality gives $\widehat{\varphi}_{\chi}=\varphi_{\chi_f}$, as we show in Theorem 5.3.²

If $H$ has no infinite clique, independent sets generate its homogeneous-set ideal $\mathcal{I}_H$. Assuming that $\mathcal{I}_H$ is proper, Theorem 5.5 shows that it is nonpathological if and only if, for every $C > 0$, the chromatic numbers $\chi(H[F])$ are bounded as $F$ ranges over the finite vertex sets satisfying $\chi_f(H[F]) \le C$. For a disjoint union of finite graphs, this bound must hold uniformly over the induced subgraphs of all blocks. The criterion gives partial answers to [24 Questions 5.21 and 5.22] for graphs with no infinite clique.

The proof adapts the extraction argument in [17 proof of Theorem 17]. If the condition fails, it produces a positive set whose induced graph is a disjoint union of finite graphs with unbounded chromatic numbers and uniformly bounded fractional chromatic numbers. The restriction to this set is hereditarily pathological.

The least-extension theorem also describes super-pathology, the property of admitting no proper nonpathological $F_\sigma$ extension. In Theorem 8.4, we prove that $\mathcal{J}_I$ consists exactly of the members of $I$ together with the positive sets $A$ for which $I \mathbin{\upharpoonright} A$ is super-pathological. In particular, every pathological $F_\sigma$ ideal has a positive super-pathological restriction. For a graph $H$ with no infinite clique and $A \in I_H^+$, the restriction $\mathcal{I}_H \mathbin{\upharpoonright} A$ is super-pathological exactly when $\varphi_{\chi_f}(A) < \infty$.

For $\mathcal{R}$, the general construction uses covers by both cliques and independent sets. Theorem 6.5 shows that its least nonpathological $F_\sigma$ extension is proper and is computed by the fractional cochromatic numbers of finite induced subgraphs of $\mathcal{R}$. Thus, $\mathcal{R}$ is not super-pathological, whereas its Kneser restriction is.

For $d \ge3$, pathology of the random $d$-uniform hypergraph ideal $\mathcal{R}_d$ and the existence of positive hereditarily pathological restrictions already follow from the constructions in [24 Theorem 5.14 and Corollary 5.15]. We recover these conclusions from the graph case: in Theorem 7.4, we use a standard extension of graph colorings to obtain a positive restriction of $\mathcal{R}_d$ isomorphic to $\mathcal{R}$ for every $d \ge2$. This also transfers the positive nonpathological restriction isomorphic to $\mathcal{ED}_{\mathrm{fin}}$. Comparing the homogeneous-cover submeasures and their envelopes, we show that the least nonpathological $F_\sigma$ extension of $\mathcal{R}_d$ is proper.

Finally, for every $d \ge3$ and $n \ge d + 1$, the homogeneous-set ideal of the universal $K_n^{(d)}$-free hypergraph is pathological but not super-pathological. Remark 8.13 explains why the super-pathology assertion in [24 Corollary 5.18] does not follow from the positive restrictions constructed there.

§ 2 fixes the notation and recalls the submeasure framework. § 3 proves pathology of $\mathcal{R}$ and describes its two local behaviors. § 4 proves the least-extension theorem and studies summable, matrix and nonpathological analytic $P$-ideal extensions. § 5 proves the chromatic criterion for graphs with no infinite clique and derives the corresponding block criteria. § 6 describes the least extension of $\mathcal{R}$, applies Prömel–Rödl universality to Erdős sequences, and relates the envelope to Kelley covering densities. § 7 transfers the random-graph results to uniform hypergraphs. § 8 describes super-pathological restrictions, gives the block classification, and treats universal hypergraphs with a finite complete hypergraph forbidden.

Preliminaries

Let $\omega= \{0,1,\ldots\}$, with each natural number identified with the set of its predecessors. For a set $X$ and $k \in\omega$, write $[X]^k$ for the family of subsets of $X$ of cardinality $k$. All underlying sets are countably infinite unless stated otherwise. An ideal $\mathcal{I}$ on $X$ is closed under subsets and finite unions, contains all finite subsets of $X$, and is proper, i.e., $X \notin\mathcal{I}$. For an ideal $\mathcal{I}$ on $X$, put $\mathcal{I}^{+} = \mathcal{P}(X) \setminus\mathcal{I}$ and $\mathcal{I} \mathord{\upharpoonright} Y = \mathcal{I} \cap\mathcal{P}(Y)$. This restriction is proper precisely when $Y \in\mathcal{I}^{+}$. We identify $\mathcal{P}(X)$ with $2^{X}$ via characteristic functions and equip it with the product topology. An ideal on $X$ is $F_{\sigma}$ if it is a countable union of closed sets in this topology, and is tall if every infinite subset of $X$ contains an infinite member of the ideal. All notions are invariant under bijections of the underlying sets.

A lower semicontinuous submeasure (lscsm) on $X$ is a map $\varphi: \mathcal{P}(X) \to[0,\infty]$ satisfying $\varphi(\varnothing) = 0$, monotonicity, subadditivity, $\varphi(\{x\}) < \infty$ for $x \in X$, and

Write $\operatorname{FIN}(\varphi) = \{A \subseteq X \mid\varphi(A) < \infty\}$. The proper ideals of this form are exactly the $F_{\sigma}$ ideals, by Mazur’s theorem [27]; see also [19], Theorem 1.5.

A measure means a countably additive function $\mu(A) = \sum_{x\in A}m(x)$, where $m : X \to[0,\infty)$ is finite at each point. For submeasures write $\psi\leq\varphi$ for pointwise domination and let $\mathcal{M}(X,\varphi)$ be the measures dominated by $\varphi$. The submeasure $\varphi$ is nonpathological if

This follows the countably additive convention of [26 §3]; for lsc submeasures it is equivalent to Farah's notion [12 p. 21], by [14 Proposition 4.1(7a)]. For $F_{\sigma}$ ideals we use [26 Definition 3.1]: $\mathcal{I}$ is nonpathological if $\mathcal{I} = \operatorname{FIN}(\varphi)$ for some nonpathological lscsm, and pathological otherwise. The ideal-level definition concerns all representations, not just a chosen submeasure. An $F_{\sigma}$ ideal is hereditarily pathological if $\mathcal{I} \mathord{\upharpoonright} Y$ is pathological for every $Y \in\mathcal{I}^{+}$.

Indeed, if $\mathcal{I} = \operatorname{FIN}(\varphi)$ with $\varphi$ nonpathological, then $\mathcal{I} \mathord{\upharpoonright} Y = \operatorname{FIN}(\varphi\mathord{\upharpoonright} \mathcal{P}(Y))$, and positivity makes this ideal proper. The last assertion follows by contraposition.

For a graph $H = (V,E)$ and $A \subseteq V$, write $H[A] = (A, E \cap[A]^2)$ for the subgraph induced by $A$. A set is homogeneous if it is a clique or an independent set. Write $\mathcal{H}(H)$ for this family and $\langle\mathcal{H}(H)\rangle$ for the sets covered by finitely many members of it.

The chromatic number $\chi(H)$ is the least number of independent sets covering $V$, with $\chi(\varnothing) = 0$ and value $\infty$ when no finite independent cover exists. A proper coloring with $m$ colors is a map $c : V \to m$ whose fibers are independent. Since every finite independent cover can be refined to a partition, $\chi(H)$ is equivalently the least number of colors in a proper coloring.

The random graph ideal: pathology and local extremes

The random graph $R = (\omega,E)$ is the unique countable graph with the extension property: for disjoint finite $a,b \subseteq\omega$, some vertex outside $a \cup b$ is adjacent to every point of $a$ and none of $b$. Every countable graph occurs as an induced subgraph [7 Proposition 4.1]. Its homogeneous-set ideal $\mathcal{R} = \langle\mathcal{H}(R) \rangle$ is proper, tall and $F_{\sigma}$ [20 p. 834]. For an induced copy $H = R[X]$, hereditary closure of homogeneity gives

one restricts a finite homogeneous cover to $X$, and conversely every homogeneous subset of $H$ is homogeneous in $R$.