In graph theory, the sphericity of a graph is a graph invariant defined to be the smallest dimension of Euclidean space required to realize the graph as an intersection graph of unit spheres. The sphericity of a graph is a generalization of the boxicity and cubicity invariants defined by F.S. Roberts in the late 1960s. [1] [2] The concept of sphericity was first introduced by Hiroshi Maehara in the early 1980s. [3]
Let be a graph. Then the sphericity of , denoted by , is the smallest integer such that can be realized as an intersection graph of unit spheres in -dimensional Euclidean space . [4]
Sphericity can also be defined using the language of space graphs as follows. For a finite set of points in some -dimensional Euclidean space, a space graph is built by connecting pairs of points with a line segment when their Euclidean distance is less than some specified constant. Then the sphericity of a graph is the minimum such that is isomorphic to a space graph in . [3]
Graphs of sphericity 1 are known as interval graphs or indifference graphs. Graphs of sphericity 2 are known as unit disk graphs.
The sphericity of certain graph classes can be computed exactly. The following sphericities were given by Maehara on page 56 of his original paper on the topic.
| Graph | Description | Sphericity | Notes |
|---|---|---|---|
| Complete graph | 0 | ||
| Complete graph | 1 | ||
| Path graph | 1 | ||
| Circuit graph | 2 | ||
| Complete m-partite graph on m sets of size 2 | 2 |
The most general known upper bound on sphericity is as follows. Assuming the graph is not complete, then where is the clique number of and denotes the number of vertices of [3]
A random variable is a mathematical formalization of a quantity or object which depends on random events. The term 'random variable' can be misleading as it is not actually random or a variable, but rather it is a mapping or a function from possible outcomes in a sample space to a measurable space, often to the real numbers.
In mathematics, mathematical physics and the theory of stochastic processes, a harmonic function is a twice continuously differentiable function where U is an open subset of that satisfies Laplace's equation, that is,
In mathematics, the orthogonal group in dimension , denoted , is the group of distance-preserving transformations of a Euclidean space of dimension that preserve a fixed point, where the group operation is given by composing transformations. The orthogonal group is sometimes called the general orthogonal group, by analogy with the general linear group. Equivalently, it is the group of orthogonal matrices, where the group operation is given by matrix multiplication. The orthogonal group is an algebraic group and a Lie group. It is compact.
In mathematics, the isoperimetric inequality is a geometric inequality involving the perimeter of a set and its volume. In -dimensional space the inequality lower bounds the surface area or perimeter of a set by its volume ,
In geometry, the Dehn invariant is a value used to determine whether one polyhedron can be cut into pieces and reassembled ("dissected") into another, and whether a polyhedron or its dissections can tile space. It is named after Max Dehn, who used it to solve Hilbert's third problem by proving that not all polyhedra with equal volume could be dissected into each other.
In mathematics, a volume form or top-dimensional form is a differential form of degree equal to the differentiable manifold dimension. Thus on a manifold of dimension , a volume form is an -form. It is an element of the space of sections of the line bundle , denoted as . A manifold admits a nowhere-vanishing volume form if and only if it is orientable. An orientable manifold has infinitely many volume forms, since multiplying a volume form by a function yields another volume form. On non-orientable manifolds, one may instead define the weaker notion of a density.
In mathematics, equivariant cohomology is a cohomology theory from algebraic topology which applies to topological spaces with a group action. It can be viewed as a common generalization of group cohomology and an ordinary cohomology theory. Specifically, the equivariant cohomology ring of a space with action of a topological group is defined as the ordinary cohomology ring with coefficient ring of the homotopy quotient :
In geometry, the Beckman–Quarles theorem states that if a transformation of the Euclidean plane or a higher-dimensional Euclidean space preserves unit distances, then it preserves all Euclidean distances. Equivalently, every homomorphism from the unit distance graph of the plane to itself must be an isometry of the plane. The theorem is named after Frank S. Beckman and Donald A. Quarles Jr., who published this result in 1953; it was later rediscovered by other authors and re-proved in multiple ways. Analogous theorems for rational subsets of Euclidean spaces, or for non-Euclidean geometry, are also known.
In probability theory and statistical mechanics, the Gaussian free field (GFF) is a Gaussian random field, a central model of random surfaces (random height functions). Sheffield (2007) gives a mathematical survey of the Gaussian free field.
In graph theory, boxicity is a graph invariant, introduced by Fred S. Roberts in 1969.
In mathematics, a quasi-isometry is a function between two metric spaces that respects large-scale geometry of these spaces and ignores their small-scale details. Two metric spaces are quasi-isometric if there exists a quasi-isometry between them. The property of being quasi-isometric behaves like an equivalence relation on the class of metric spaces.
In mathematics a translation surface is a surface obtained from identifying the sides of a polygon in the Euclidean plane by translations. An equivalent definition is a Riemann surface together with a holomorphic 1-form.
In mathematics, a polyadic space is a topological space that is the image under a continuous function of a topological power of an Alexandroff one-point compactification of a discrete space.
In geometry of normed spaces, the Holmes–Thompson volume is a notion of volume that allows to compare sets contained in different normed spaces. It was introduced by Raymond D. Holmes and Anthony Charles Thompson.
In geometry, a valuation is a finitely additive function on a collection of admissible subsets of a fixed set with values in an abelian semigroup. For example, the Lebesgue measure is a valuation on finite unions of convex bodies of Euclidean space Other examples of valuations on finite unions of convex bodies are the surface area, the mean width, and the Euler characteristic.
In the mathematical discipline of functional analysis, a differentiable vector-valued function from Euclidean space is a differentiable function valued in a topological vector space (TVS) whose domains is a subset of some finite-dimensional Euclidean space. It is possible to generalize the notion of derivative to functions whose domain and codomain are subsets of arbitrary topological vector spaces (TVSs) in multiple ways. But when the domain of a TVS-valued function is a subset of a finite-dimensional Euclidean space then many of these notions become logically equivalent resulting in a much more limited number of generalizations of the derivative and additionally, differentiability is also more well-behaved compared to the general case. This article presents the theory of -times continuously differentiable functions on an open subset of Euclidean space , which is an important special case of differentiation between arbitrary TVSs. This importance stems partially from the fact that every finite-dimensional vector subspace of a Hausdorff topological vector space is TVS isomorphic to Euclidean space so that, for example, this special case can be applied to any function whose domain is an arbitrary Hausdorff TVS by restricting it to finite-dimensional vector subspaces.
In mathematics, and especially differential geometry and mathematical physics, gauge theory is the general study of connections on vector bundles, principal bundles, and fibre bundles. Gauge theory in mathematics should not be confused with the closely related concept of a gauge theory in physics, which is a field theory which admits gauge symmetry. In mathematics theory means a mathematical theory, encapsulating the general study of a collection of concepts or phenomena, whereas in the physical sense a gauge theory is a mathematical model of some natural phenomenon.
A sparsity matroid is a mathematical structure that captures how densely a multigraph is populated with edges. To unpack this a little, sparsity is a measure of density of a graph that bounds the number of edges in any subgraph. The property of having a particular matroid as its density measure is invariant under graph isomorphisms and so it is a graph invariant.
In mathematics, and in particular algebraic geometry, K-stability is an algebro-geometric stability condition for projective algebraic varieties and complex manifolds. K-stability is of particular importance for the case of Fano varieties, where it is the correct stability condition to allow the formation of moduli spaces, and where it precisely characterises the existence of Kähler–Einstein metrics.
In graph theory, cubicity is a graph invariant defined to be the smallest dimension such that a graph can be realized as an intersection graph of unit cubes in Euclidean space. Cubicity was introduced by Fred S. Roberts in 1969 along with a related invariant called boxicity that considers the smallest dimension needed to represent a graph as an intersection graph of axis-parallel rectangles in Euclidean space.
