ترغب بنشر مسار تعليمي؟ اضغط هنا

An Oriented Hypergraphic Approach to Algebraic Graph Theory

166   0   0.0 ( 0 )
 نشر من قبل Nathan Reff
 تاريخ النشر 2015
  مجال البحث
والبحث باللغة English




اسأل ChatGPT حول البحث

An oriented hypergraph is a hypergraph where each vertex-edge incidence is given a label of $+1$ or $-1$. We define the adjacency, incidence and Laplacian matrices of an oriented hypergraph and study each of them. We extend several matrix results known for graphs and signed graphs to oriented hypergraphs. New matrix results that are not direct generalizations are also presented. Finally, we study a new family of matrices that contains walk information.



قيم البحث

اقرأ أيضاً

An oriented hypergraph is an oriented incidence structure that generalizes and unifies graph and hypergraph theoretic results by examining its locally signed graphic substructure. In this paper we obtain a combinatorial characterization of the coeffi cients of the characteristic polynomials of oriented hypergraphic Laplacian and adjacency matrices via a signed hypergraphic generalization of basic figures of graphs. Additionally, we provide bounds on the determinant and permanent of the Laplacian matrix, characterize the oriented hypergraphs in which the upper bound is sharp, and demonstrate that the lower bound is never achieved.
Restrictions of incidence-preserving path maps produce an oriented hypergraphic All Minors Matrix-tree Theorems for Laplacian and adjacency matrices. The images of these maps produce a locally signed graphic, incidence generalization, of cycle covers and basic figures that correspond to incidence-k-forests. When restricted to bidirected graphs the natural partial ordering of maps results in disjoint signed boolean lattices whose minor calculations correspond to principal order ideals. As an application, (1) the determinant formula of a signed graphic Laplacian is reclaimed and shown to be determined by the maximal positive-circle-free elements, and (2) spanning trees are equivalent to single-element order ideals.
The graph reconstruction conjecture asserts that every finite simple graph on at least three vertices can be reconstructed up to isomorphism from its deck - the collection of its vertex-deleted subgraphs. Kocays Lemma is an important tool in graph re construction. Roughly speaking, given the deck of a graph $G$ and any finite sequence of graphs, it gives a linear constraint that every reconstruction of $G$ must satisfy. Let $psi(n)$ be the number of distinct (mutually non-isomorphic) graphs on $n$ vertices, and let $d(n)$ be the number of distinct decks that can be constructed from these graphs. Then the difference $psi(n) - d(n)$ measures how many graphs cannot be reconstructed from their decks. In particular, the graph reconstruction conjecture is true for $n$-vertex graphs if and only if $psi(n) = d(n)$. We give a framework based on Kocays lemma to study this discrepancy. We prove that if $M$ is a matrix of covering numbers of graphs by sequences of graphs, then $d(n) geq mathsf{rank}_mathbb{R}(M)$. In particular, all $n$-vertex graphs are reconstructible if one such matrix has rank $psi(n)$. To complement this result, we prove that it is possible to choose a family of sequences of graphs such that the corresponding matrix $M$ of covering numbers satisfies $d(n) = mathsf{rank}_mathbb{R}(M)$.
118 - Chih-Hao Fu , Yi-Jian Du , Bo Feng 2012
One important discovery in recent years is that the total amplitude of gauge theory can be written as BCJ form where kinematic numerators satisfy Jacobi identity. Although the existence of such kinematic numerators is no doubt, the simple and explici t construction is still an important problem. As a small step, in this note we provide an algebraic approach to construct these kinematic numerators. Under our Feynman-diagram-like construction, the Jacobi identity is manifestly satisfied. The corresponding color ordered amplitudes satisfy off-shell KK-relation and off-shell BCJ relation similar to the color ordered scalar theory. Using our construction, the dual DDM form is also established.
121 - Lu Chen , Tobias Fritz 2021
According to the algebraic approach to spacetime, a thoroughgoing dynamicism, physical fields exist without an underlying manifold. This view is usually implemented by postulating an algebraic structure (e.g., commutative ring) of scalar-valued funct ions, which can be interpreted as representing a scalar field, and deriving other structures from it. In this work, we point out that this leads to the unjustified primacy of an undetermined scalar field. Instead, we propose to consider algebraic structures in which all (and only) physical fields are primitive. We explain how the theory of emph{natural operations} in differential geometry---the modern formalism behind classifying diffeomorphism-invariant constructions---can be used to obtain concrete implementations of this idea for any given collection of fields. For concrete examples, we illustrate how our approach applies to a number of particular physical fields, including electrodynamics coupled to a Weyl spinor.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا