Several new spectral properties of the normalized Laplacian defined for oriented hypergraphs are shown. The eigenvalue 1 and the case of duplicate vertices are discussed; two Courant nodal domain ...theorems are established; new quantities that bound the eigenvalues are introduced. In particular, the Cheeger constant is generalized and it is shown that the classical Cheeger bounds can be generalized for some classes of hypergraphs; it is shown that a geometric quantity used to study zonotopes bounds the largest eigenvalue from below, and that the notion of coloring number can be generalized and used for proving a Hoffman-like bound. Finally, the spectrum of the unnormalized Laplacian for Cartesian products of hypergraphs is discussed.
The independence number, coloring number and related parameters are investigated in the setting of oriented hypergraphs using the spectrum of the normalized Laplace operator. For the independence ...number, both an inertia–like bound and a ratio–like bound are shown. A Sandwich Theorem involving the clique number, the vector chromatic number and the coloring number is proved, as well as a lower bound for the vector chromatic number in terms of the smallest and the largest eigenvalue of the normalized Laplacian. In addition, spectral partition numbers are studied in relation to the coloring number.
The
p
-Laplacian for graphs, as well as the vertex Laplace operator and the hyperedge Laplace operator for the general setting of oriented hypergraphs, are generalized. In particular, both a vertex
p
...-Laplacian and a hyperedge
p
-Laplacian are defined for oriented hypergraphs, for all
p
≥ 1. Several spectral properties of these operators are investigated.
The family $D(k,m)$ of graphs having an orientation such that for every vertex $v \in V(G)$ either (outdegree) $\deg^+(v) \le k$ or (indegree) $\deg^-(v) \le m$ have been investigated recently in ...several papers because of the role $D(k,m)$ plays in the efforts to estimate the maximum directed cut in digraphs and the minimum cover of digraphs by directed cuts. Results concerning the chromatic number of graphs in the family $D(k,m)$ have been obtained via the notion of $d$-degeneracy of graphs. In this paper we consider a far reaching generalization of the family $D(k,m)$, in a complementary form, into the context of $r$-uniform hypergraphs, using a generalization of Hakimi's theorem to $r$-uniform hypergraphs and by showing some tight connections with the well known Ramsey numbers for hypergraphs.
A Claude Berge qui m’appris à voir les graphes non seulement comme objets “plaisans et délectables” mais comme sources infinies de variations chromatiques
Good
k-colorings have been defined by C. ...Berge who showed their existence in balanced hypergraphs. There is a simple generalization to oriented balanced hypergraphs: using the bi-coloring characterization of
0
,
±
1
-matrices of M. Conforti and G. Cornuejols, we show that oriented balanced hypergraphs have good
k-colorings for any
k. A stronger type of coloring is also shown to exist for oriented balanced hypergraphs.
The family D(k,m) of graphs having an orientation such that for every vertex
v ∈ V (G) either (outdegree) deg+(v) ≤ k or (indegree) deg−(v) ≤ m have been investigated
recently in several papers ...because of the role D(k,m) plays in the efforts to
estimate the maximum directed cut in digraphs and the minimum cover of digraphs
by directed cuts. Results concerning the chromatic number of graphs in the family
D(k,m) have been obtained via the notion of d-degeneracy of graphs. In this paper we
consider a far reaching generalization of the family D(k,m), in a complementary form,
into the context of r-uniform hypergraphs, using a generalization of Hakimi’s theorem
to r-uniform hypergraphs and by showing
Peer Reviewed
Oriented hypergraphs: Balanceability Rusnak, Lucas J.; Li, Selena; Xu, Brian ...
Discrete mathematics,
June 2022, 2022-06-00, Letnik:
345, Številka:
6
Journal Article
Recenzirano
Odprti dostop
An oriented hypergraph is an oriented incidence structure that extends the concepts of signed graphs, balanced hypergraphs, and balanced matrices. We introduce hypergraphic structures and techniques ...that generalize the circuit classification of the signed graphic frame matroid to any oriented hypergraphic incidence matrix via its locally-signed-graphic substructure. To achieve this, Camion's algorithm is applied to oriented hypergraphs to provide a generalization of reorientation sets and frustration that is only well-defined on balanceable oriented hypergraphs. A simple partial characterization of unbalanceable circuits extends the applications to representable matroids demonstrating that the difference between the Fano and non-Fano matroids is one of balance.
An oriented hypergraph is a hypergraph where each vertex-edge incidence is given a label of either +1 or −1. This generalizes signed graphs to a hypergraph setting and simultaneously provides a ...natural definition for a signed adjacency which is used to define the adjacency and Laplacian matrices. Many properties of these matrices are known, but there are no nontrivial families of oriented hypergraphs with their spectrum determined. In this paper we define and study hypergraph families that are analogous to cycles and paths in graphs and signed graphs. The adjacency and Laplacian eigenvalues for some of these families is determined.
An oriented hypergraph is an oriented incidence structure that allows for the generalization of graph theoretic concepts to integer matrices through its locally signed graphic substructure. The ...locally graphic behaviors are formalized in the subobject classifier of incidence hypergraphs. Moreover, the injective envelope is calculated and shown to contain the class of uniform hypergraphs — providing a combinatorial framework for the entries of incidence matrices. A multivariable all-minors characteristic polynomial is obtained for both the determinant and permanent of the oriented hypergraphic Laplacian and adjacency matrices arising from any integer incidence matrix. The coefficients of each polynomial are shown to be submonic maps from the same family into the injective envelope limited by the subobject classifier. These results provide a unifying theorem for oriented hypergraphic matrix-tree-type and Sachs-coefficient-type theorems. Finally, by specializing to bidirected graphs, the trivial subclasses for the degree-k monomials of the Laplacian are shown to be in one-to-one correspondence with k-arborescences.
An oriented hypergraph is a hypergraph where each vertex-edge incidence is given a label of +1 or −1, and each adjacency is signed the negative of the product of the incidences. An oriented ...hypergraph is balanced if the product of the adjacencies in each circle is positive.
We provide a combinatorial interpretation for entries of kth power of the oriented hypergraphic Laplacian via the number of signed weak walks of length k. Using closed weak walks we prove a new characterization of balance for oriented hypergraphs and matrices that generalizes Harary's Theorem for signed graphs.
PDF
