On the speed of algebraically defined graph classes

DOI10.1016/J.AIM.2021.107593MaRDI QIDQ2227284zbMATH OpenOpenAlexFDO

Authors Lisa Sauermann

Publication date 15 February 2021

Published in Advances in Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1908.11575

zbMATH Keywords

intersection graphspeedWarren's theorem

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Structural characterization of families of graphs (05C75) Graph operations (line graphs, products, etc.) (05C76)

Abstract: The speed of a class of graphs counts the number of graphs on the vertex set $lbrace1,dots,nbrace$ inside the class as a function of $n$. In this paper, we investigate this function for many classes of graphs that naturally arise in discrete geometry, for example intersection graphs of segments or disks in the plane. While upper bounds follow from Warren's theorem (a variant of a theorem of Milnor and Thom), all the previously known lower bounds were obtained from ad hoc constructions for very specific classes. We prove a general theorem giving an essentially tight lower bound for the number of graphs on $lbrace1,dots,nbrace$ whose edges are defined using the signs of a given finite list of polynomials, assuming these polynomials satisfy some reasonable conditions. This in particular implies lower bounds for the speed of many different classes of intersection graphs, which essentially match the known upper bounds. Our general result also gives essentially tight lower bounds for counting containment orders of various families of geometric objects, including circle orders and angle orders. Some of the applications presented in this paper are new, whereas others recover results of Alon-Scheinerman, Fox, McDiarmid-M"{u}ller and Shi. For the proof of our result we use some tools from algebraic geometry and differential topology.

Recommendations

• Algorithms for classes of graphs with bounded expansion
• scientific article; zbMATH DE number 140151
• Speeding up Graph Algorithms via Switching Classes
• A note on the speed of hereditary graph properties
• The speed of hereditary properties of graphs
• scientific article; zbMATH DE number 3878984
• scientific article; zbMATH DE number 4068310
• scientific article; zbMATH DE number 876677
• scientific article; zbMATH DE number 437554
• Graph classes with structured neighborhoods and algorithmic applications

Cites work

• scientific article; zbMATH DE number 4200260 (Why is no real title available?)
• scientific article; zbMATH DE number 4029737 (Why is no real title available?)
• scientific article; zbMATH DE number 704831 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• scientific article; zbMATH DE number 3223507 (Why is no real title available?)
• A jump to the Bell number for hereditary graph properties
• Algebraic geometry I. Schemes. With examples and exercises
• Angle orders
• Circle orders and angle orders
• Circle orders, n-gon orders and the crossing number
• Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane
• Crossing patterns of segments
• Crossing patterns of semi-algebraic sets
• Degrees of freedom versus dimension for containment orders
• Efficient approximation algorithms for tiling and packing problems with rectangles
• Efficient graph representations
• Every planar graph is the intersection graph of segments in the plane (extended abstract)
• Integer realizations of disk and segment graphs
• Intersection graphs of L-shapes and segments in the plane
• Intersection graphs of curves in the plane
• Intersection graphs of rays and grounded segments
• Intersection graphs of segments
• Introduction to Smooth Manifolds
• Lower Bounds for Approximation by Nonlinear Manifolds
• On the Betti Numbers of Real Varieties
• On the size of hereditary classes of graphs
• Refining the hierarchies of classes of geometric intersection graphs
• The clique problem in ray intersection graphs
• The number of disk graphs
• The penultimate rate of growth for graph properties
• The speed of hereditary properties of graphs
• Triangle-free intersection graphs of line segments with large chromatic number
• Unit disk graphs

Cited in

(5)

• A structure theorem for pseudosegments and its applications
• Speeding up Graph Algorithms via Switching Classes
• A structure theorem for pseudo-segments and its applications
• Succinct permutation graphs
• Enumeration of intersection graphs of x-monotone curves

This page was built for publication: On the speed of algebraically defined graph classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2227284)