An official website of the United States government
Abstract We determine the order of thek-core in a large class of dense graph sequences. Let$$G_n$$be a sequence of undirected,n-vertex graphs with edge weights$$\{a^n_{i,j}\}_{i,j \in [n]}$$that converges to a graphon$$W\colon[0,1]^2 \to [0,+\infty)$$in the cut metric. Keeping an edge (i,j) of$$G_n$$with probability$${a^n_{i,j}}/{n}$$independently, we obtain a sequence of random graphs$$G_n({1}/{n})$$. Using a branching process and the theory of dense graph limits, under mild assumptions we obtain the order of thek-core of random graphs$$G_n({1}/{n})$$. Our result can also be used to obtain the threshold of appearance of ak-core of ordern.
more »
« less
This content will become publicly available on November 11, 2025
Borel line graphs
Abstract We characterize Borel line graphs in terms of 10 forbidden induced subgraphs, namely the nine finite graphs from the classical result of Beineke together with a 10th infinite graph associated with the equivalence relation$$\mathbb {E}_0$$on the Cantor space. As a corollary, we prove a partial converse to the Feldman–Moore theorem, which allows us to characterize all locally countable Borel line graphs in terms of their Borel chromatic numbers.
more »
« less
- PAR ID:
- 10594832
- Publisher / Repository:
- Cambridge University Press
- Date Published:
- Journal Name:
- The Journal of Symbolic Logic
- ISSN:
- 0022-4812
- Page Range / eLocation ID:
- 1 to 22
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract This is the second installment in a series of papers applying descriptive set theoretic techniques to both analyze and enrich classical functors from homological algebra and algebraic topology. In it, we show that the Čech cohomology functorson the category of locally compact separable metric spaces each factor into (i) what we term theirdefinable version, a functortaking values in the category$$\mathsf {GPC}$$ofgroups with a Polish cover(a category first introduced in this work’s predecessor), followed by (ii) a forgetful functor from$$\mathsf {GPC}$$to the category of groups. These definable cohomology functors powerfully refine their classical counterparts: we show that they are complete invariants, for example, of the homotopy types of mapping telescopes ofd-spheres ord-tori for any$$d\geq 1$$, and, in contrast, that there exist uncountable families of pairwise homotopy inequivalent mapping telescopes of either sort on which the classical cohomology functors are constant. We then apply the functorsto show that a seminal problem in the development of algebraic topology – namely, Borsuk and Eilenberg’s 1936 problem of classifying, up to homotopy, the maps from a solenoid complement$$S^3\backslash \Sigma $$to the$$2$$-sphere – is essentially hyperfinite but not smooth. Fundamental to our analysis is the fact that the Čech cohomology functorsadmit two main formulations: a more combinatorial one and a more homotopical formulation as the group$$[X,P]$$of homotopy classes of maps fromXto a polyhedral$$K(G,n)$$spaceP. We describe the Borel-definable content of each of these formulations and prove a definable version of Huber’s theorem reconciling the two. In the course of this work, we record definable versions of Urysohn’s Lemma and the simplicial approximation and homotopy extension theorems, along with a definable Milnor-type short exact sequence decomposition of the space$$\mathrm {Map}(X,P)$$in terms of its subset ofphantom maps; relatedly, we provide a topological characterization of this set for any locally compact Polish spaceXand polyhedronP. In aggregate, this work may be more broadly construed as laying foundations for the descriptive set theoretic study of the homotopy relation on such spaces$$\mathrm {Map}(X,P)$$, a relation which, together with the more combinatorial incarnation of, embodies a substantial variety of classification problems arising throughout mathematics. We show, in particular, that ifPis a polyhedralH-group, then this relation is both Borel and idealistic. In consequence,$$[X,P]$$falls in the category ofdefinable groups, an extension of the category$$\mathsf {GPC}$$introduced herein for its regularity properties, which facilitate several of the aforementioned computations.more » « less
-
Abstract Counting independent sets in graphs and hypergraphs under a variety of restrictions is a classical question with a long history. It is the subject of the celebrated container method which found numerous spectacular applications over the years. We consider the question of how many independent sets we can have in a graph under structural restrictions. We show that any$$n$$-vertex graph with independence number$$\alpha$$without$$bK_a$$as an induced subgraph has at most$$n^{O(1)} \cdot \alpha ^{O(\alpha )}$$independent sets. This substantially improves the trivial upper bound of$$n^{\alpha },$$whenever$$\alpha \le n^{o(1)}$$and gives a characterisation of graphs forbidding which allows for such an improvement. It is also in general tight up to a constant in the exponent since there exist triangle-free graphs with$$\alpha ^{\Omega (\alpha )}$$independent sets. We also prove that if one in addition assumes the ground graph is chi-bounded one can improve the bound to$$n^{O(1)} \cdot 2^{O(\alpha )}$$which is tight up to a constant factor in the exponent.more » « less
-
Abstract We study the locations of complex zeroes of independence polynomials of bounded-degree hypergraphs. For graphs, this is a long-studied subject with applications to statistical physics, algorithms, and combinatorics. Results on zero-free regions for bounded-degree graphs include Shearer’s result on the optimal zero-free disc, along with several recent results on other zero-free regions. Much less is known for hypergraphs. We make some steps towards an understanding of zero-free regions for bounded-degree hypergaphs by proving that all hypergraphs of maximum degree$$\Delta$$have a zero-free disc almost as large as the optimal disc for graphs of maximum degree$$\Delta$$established by Shearer (of radius$$\sim 1/(e \Delta )$$). Up to logarithmic factors in$$\Delta$$this is optimal, even for hypergraphs with all edge sizes strictly greater than$$2$$. We conjecture that for$$k\ge 3$$,$$k$$-uniformlinearhypergraphs have a much larger zero-free disc of radius$$\Omega (\Delta ^{- \frac{1}{k-1}} )$$. We establish this in the case of linear hypertrees.more » « less
-
Abstract The well-studied moduli space of complex cubic surfaces has three different, but isomorphic, compact realizations: as a GIT quotient$${\mathcal {M}}^{\operatorname {GIT}}$$, as a Baily–Borel compactification of a ball quotient$${(\mathcal {B}_4/\Gamma )^*}$$, and as a compactifiedK-moduli space. From all three perspectives, there is a unique boundary point corresponding to non-stable surfaces. From the GIT point of view, to deal with this point, it is natural to consider the Kirwan blowup$${\mathcal {M}}^{\operatorname {K}}\rightarrow {\mathcal {M}}^{\operatorname {GIT}}$$, whereas from the ball quotient point of view, it is natural to consider the toroidal compactification$${\overline {\mathcal {B}_4/\Gamma }}\rightarrow {(\mathcal {B}_4/\Gamma )^*}$$. The spaces$${\mathcal {M}}^{\operatorname {K}}$$and$${\overline {\mathcal {B}_4/\Gamma }}$$have the same cohomology, and it is therefore natural to ask whether they are isomorphic. Here, we show that this is in factnotthe case. Indeed, we show the more refined statement that$${\mathcal {M}}^{\operatorname {K}}$$and$${\overline {\mathcal {B}_4/\Gamma }}$$are equivalent in the Grothendieck ring, but notK-equivalent. Along the way, we establish a number of results and techniques for dealing with singularities and canonical classes of Kirwan blowups and toroidal compactifications of ball quotients.more » « less
