Implicit representation conjecture for semi-algebraic graphs

DOI10.1016/J.DAM.2018.11.030MaRDI QIDQ1735676zbMATH OpenOpenAlexWikidataFDO

Authors Matthew Fitch

Publication date 28 March 2019

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

disk graphsimplicit representation conjecturesemi-algebraic graphs

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: The implicit representation conjecture concerns hereditary families of graphs. Given a graph in such a family, we want to assign some string of bits to each vertex in such a way that we can recover the information about whether 2 vertices are connected or not using only the 2 strings of bits associated with those two vertices. We then want to minimise the length of this string. The conjecture states that if the family is hereditary and small enough (it only has $2^{O(nln(n))}$ graphs of size $n$), then $O(ln(n))$ bits per vertex should be sufficient. The trivial bounds on this problem are that: (1) some families require at least $l{n}_2(n)$ bits per vertex ; (2) $(n-1)/2+l{n}_2(n)$ bits per vertex are sufficient for all families. In this paper, we will be talking about a special case of the implicit representation conjecture, where the family is semi-algebraic (which roughly means that the vertices are points in some euclidean space, and the edges are defined geometrically, or according to some polynomials). We will first prove that the `obvious' way of storing the information, where we store an approximation of the coordinates of each vertex, doesn't work. Then we will come up with a way of storing the information that requires $O(n^{1-epsilon})$ bits per vertex, where $epsilon$ is some small constant depending only on the family. This is a slight improvement over the trivial bound, but is still a long way from proving the conjecture.

Recommendations

• Implicit representations and factorial properties of graphs
• Graph parameters, implicit representations and factorial properties
• scientific article; zbMATH DE number 6851856
• Implicat Representation of Graphs
• Representation complexities of semialgebraic graphs

Cites work

• scientific article; zbMATH DE number 863501 (Why is no real title available?)
• Crossing patterns of semi-algebraic sets
• Efficient graph representations
• Implicat Representation of Graphs
• Integer realizations of disk and segment graphs
• Lower Bounds for Approximation by Nonlinear Manifolds
• Sphere and dot product representations of graphs
• Turán numbers for \(K_{s,t}\)-free graphs: topological obstructions and algebraic constructions
• Unit disk graph recognition is NP-hard

Cited in

(4)

• scientific article; zbMATH DE number 6851856 (Why is no real title available?)
• Implicit representation of sparse hereditary families
• Implicit representations and factorial properties of graphs
• Implicit Component-Graph: A Discussion

This page was built for publication: Implicit representation conjecture for semi-algebraic graphs

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