Graph amalgamation

Last updated

In graph theory, a graph amalgamation is a relationship between two graphs (one graph is an amalgamation of another). Similar relationships include subgraphs and minors. Amalgamations can provide a way to reduce a graph to a simpler graph while keeping certain structure intact. The amalgamation can then be used to study properties of the original graph in an easier to understand context. Applications include embeddings, [1] computing genus distribution, [2] and Hamiltonian decompositions.

Contents

Definition

Let and be two graphs with the same number of edges where has more vertices than . Then we say that is an amalgamation of if there is a bijection and a surjection and the following hold:

Note that while can be a graph or a pseudograph, it will usually be the case that is a pseudograph.

Properties

Edge colorings are invariant to amalgamation. This is obvious, as all of the edges between the two graphs are in bijection with each other. However, what may not be obvious, is that if is a complete graph of the form , and we color the edges as to specify a Hamiltonian decomposition (a decomposition into Hamiltonian paths, then those edges also form a Hamiltonian Decomposition in .

Example

Figure 1: An amalgamation of the complete graph on five vertices. Graph amalgamation of k5.png
Figure 1: An amalgamation of the complete graph on five vertices.

Figure 1 illustrates an amalgamation of . The invariance of edge coloring and Hamiltonian Decomposition can be seen clearly. The function is a bijection and is given as letters in the figure. The function is given in the table below.

Hamiltonian decompositions

One of the ways in which amalgamations can be used is to find Hamiltonian Decompositions of complete graphs with 2n + 1 vertices. [4] The idea is to take a graph and produce an amalgamation of it which is edge colored in colors and satisfies certain properties (called an outline Hamiltonian decomposition). We can then 'reverse' the amalgamation and we are left with colored in a Hamiltonian Decomposition.

In [3] Hilton outlines a method for doing this, as well as a method for finding all Hamiltonian Decompositions without repetition. The methods rely on a theorem he provides which states (roughly) that if we have an outline Hamiltonian decomposition, we could have arrived at it by first starting with a Hamiltonian decomposition of the complete graph and then finding an amalgamation for it.

Notes

  1. Gross, Tucker 1987
  2. Gross 2011
  3. 1 2 Hilton 1984
  4. Bahmanian, Amin; Rodger, Chris 2012

Related Research Articles

<span class="mw-page-title-main">Feynman diagram</span> Pictorial representation of the behavior of subatomic particles

In theoretical physics, a Feynman diagram is a pictorial representation of the mathematical expressions describing the behavior and interaction of subatomic particles. The scheme is named after American physicist Richard Feynman, who introduced the diagrams in 1948. The interaction of subatomic particles can be complex and difficult to understand; Feynman diagrams give a simple visualization of what would otherwise be an arcane and abstract formula. According to David Kaiser, "Since the middle of the 20th century, theoretical physicists have increasingly turned to this tool to help them undertake critical calculations. Feynman diagrams have revolutionized nearly every aspect of theoretical physics." While the diagrams are applied primarily to quantum field theory, they can also be used in other areas of physics, such as solid-state theory. Frank Wilczek wrote that the calculations that won him the 2004 Nobel Prize in Physics "would have been literally unthinkable without Feynman diagrams, as would [Wilczek's] calculations that established a route to production and observation of the Higgs particle."

<span class="mw-page-title-main">Graph theory</span> Area of discrete mathematics

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices which are connected by edges. A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics.

In quantum mechanics, the Hamiltonian of a system is an operator corresponding to the total energy of that system, including both kinetic energy and potential energy. Its spectrum, the system's energy spectrum or its set of energy eigenvalues, is the set of possible outcomes obtainable from a measurement of the system's total energy. Due to its close relation to the energy spectrum and time-evolution of a system, it is of fundamental importance in most formulations of quantum theory.

The Riesz representation theorem, sometimes called the Riesz–Fréchet representation theorem after Frigyes Riesz and Maurice René Fréchet, establishes an important connection between a Hilbert space and its continuous dual space. If the underlying field is the real numbers, the two are isometrically isomorphic; if the underlying field is the complex numbers, the two are isometrically anti-isomorphic. The (anti-) isomorphism is a particular natural isomorphism.

In mathematics, specifically abstract algebra, the isomorphism theorems are theorems that describe the relationship between quotients, homomorphisms, and subobjects. Versions of the theorems exist for groups, rings, vector spaces, modules, Lie algebras, and various other algebraic structures. In universal algebra, the isomorphism theorems can be generalized to the context of algebras and congruences.

<span class="mw-page-title-main">Loop quantum gravity</span> Theory of quantum gravity, merging quantum mechanics and general relativity

Loop quantum gravity (LQG) is a theory of quantum gravity, which aims to merge quantum mechanics and general relativity, incorporating matter of the Standard Model into the framework established for the pure quantum gravity case. It is an attempt to develop a quantum theory of gravity based directly on Einstein's geometric formulation rather than the treatment of gravity as a force. As a theory LQG postulates that the structure of space and time is composed of finite loops woven into an extremely fine fabric or network. These networks of loops are called spin networks. The evolution of a spin network, or spin foam, has a scale above the order of a Planck length, approximately 10−35 meters, and smaller scales are meaningless. Consequently, not just matter, but space itself, prefers an atomic structure.

In mathematics, a self-adjoint operator on an infinite-dimensional complex vector space V with inner product is a linear map A that is its own adjoint. If V is finite-dimensional with a given orthonormal basis, this is equivalent to the condition that the matrix of A is a Hermitian matrix, i.e., equal to its conjugate transpose A. By the finite-dimensional spectral theorem, V has an orthonormal basis such that the matrix of A relative to this basis is a diagonal matrix with entries in the real numbers. This article deals with applying generalizations of this concept to operators on Hilbert spaces of arbitrary dimension.

<span class="mw-page-title-main">Hypergraph</span> Generalization of graph theory

In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices.

In physics, an operator is a function over a space of physical states onto another space of physical states. The simplest example of the utility of operators is the study of symmetry. Because of this, they are very useful tools in classical mechanics. Operators are even more important in quantum mechanics, where they form an intrinsic part of the formulation of the theory.

<span class="mw-page-title-main">Graph (discrete mathematics)</span> Vertices connected in pairs by edges

In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called vertices and each of the related pairs of vertices is called an edge. Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges. Graphs are one of the objects of study in discrete mathematics.

<span class="mw-page-title-main">Canonical quantization</span> Process of converting a classical physical theory into one compatible with quantum mechanics

In physics, canonical quantization is a procedure for quantizing a classical theory, while attempting to preserve the formal structure, such as symmetries, of the classical theory, to the greatest extent possible.

The concept of system of imprimitivity is used in mathematics, particularly in algebra and analysis, both within the context of the theory of group representations. It was used by George Mackey as the basis for his theory of induced unitary representations of locally compact groups.

The time-evolving block decimation (TEBD) algorithm is a numerical scheme used to simulate one-dimensional quantum many-body systems, characterized by at most nearest-neighbour interactions. It is dubbed Time-evolving Block Decimation because it dynamically identifies the relevant low-dimensional Hilbert subspaces of an exponentially larger original Hilbert space. The algorithm, based on the Matrix Product States formalism, is highly efficient when the amount of entanglement in the system is limited, a requirement fulfilled by a large class of quantum many-body systems in one dimension.

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.

Chow's lemma, named after Wei-Liang Chow, is one of the foundational results in algebraic geometry. It roughly says that a proper morphism is fairly close to being a projective morphism. More precisely, a version of it states the following:

A Representation up to homotopy has several meanings. One of the earliest appeared in the `physical' context of constrained Hamiltonian systems. The essential idea is lifting a non-representation on a quotient to a representation up to strong homotopy on a resolution of the quotient. As a concept in differential geometry, it generalizes the notion of representation of a Lie algebra to Lie algebroids and nontrivial vector bundles. As such, it was introduced by Abad and Crainic.

Coherent states have been introduced in a physical context, first as quasi-classical states in quantum mechanics, then as the backbone of quantum optics and they are described in that spirit in the article Coherent states. However, they have generated a huge variety of generalizations, which have led to a tremendous amount of literature in mathematical physics. In this article, we sketch the main directions of research on this line. For further details, we refer to several existing surveys.

In the ADM formulation of general relativity one splits spacetime into spatial slices and time, the basic variables are taken to be the induced metric, , on the spatial slice, and its conjugate momentum variable related to the extrinsic curvature, ,. These are the metric canonical coordinates.

<span class="mw-page-title-main">Loop representation in gauge theories and quantum gravity</span> Description of gauge theories using loop operators

Attempts have been made to describe gauge theories in terms of extended objects such as Wilson loops and holonomies. The loop representation is a quantum hamiltonian representation of gauge theories in terms of loops. The aim of the loop representation in the context of Yang–Mills theories is to avoid the redundancy introduced by Gauss gauge symmetries allowing to work directly in the space of physical states. The idea is well known in the context of lattice Yang–Mills theory. Attempts to explore the continuous loop representation was made by Gambini and Trias for canonical Yang–Mills theory, however there were difficulties as they represented singular objects. As we shall see the loop formalism goes far beyond a simple gauge invariant description, in fact it is the natural geometrical framework to treat gauge theories and quantum gravity in terms of their fundamental physical excitations.

A Lie bialgebroid is a mathematical structure in the area of non-Riemannian differential geometry. In brief a Lie bialgebroid are two compatible Lie algebroids defined on dual vector bundles. They form the vector bundle version of a Lie bialgebra.

References