Oriented hypergraphs: Balanceability

Autor: Lucas J. Rusnak, Selena Li, Brian Xu, Eric Yan, Shirley Zhu
Rok vydání: 2022
Předmět:
Zdroj: Discrete Mathematics. 345:112832
ISSN: 0012-365X
DOI: 10.1016/j.disc.2022.112832
Popis: 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.
19 pages, 9 figures
Databáze: OpenAIRE
Externí odkaz: