The maximal subgroups and the complexity of the flow semigroup of finite (di)graphs

DOI10.1142/S0218196717500412MaRDI QIDQ4596405zbMATH OpenOpenAlexFDO

Authors Gábor Horváth, Chrystopher L. Nehaniv, Károly Podoski

Publication date 1 December 2017

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1705.09577

zbMATH Keywords

complete invariants for graphsflow semigroup of digraphsinvariants for digraphsKrohn-Rhodes complexitypermutation groupsRhodes's conjecture

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) General theory for finite permutation groups (20B05) Symmetric groups (20B30) Semigroups of transformations, relations, partitions, etc. (20M20)

Abstract: The flow semigroup, introduced by John Rhodes, is an invariant for digraphs and a complete invariant for graphs. After collecting together previous partial results, we refine and prove Rhodes's conjecture on the structure of the maximal groups in the flow semigroup for finite, antisymmetric, strongly connected digraphs. Building on this result, we investigate and fully describe the structure and actions of the maximal subgroups of the flow semigroup acting on all but $k$ points for all finite digraphs and graphs for all $kgeq1$. A linear algorithm (in the number of edges) is presented to determine these so-called `defect $k$ groups' for any finite (di)graph. Finally, we prove that the complexity of the flow semigroup of a 2-vertex connected (and strongly connected di)graph with $n$ vertices is $n-2$, completely confirming Rhodes's conjecture for such (di)graphs.

Recommendations

• Flows on regular semigroups
• Lengths of words in transformation semigroups generated by digraphs
• Structural aspects of semigroups based on digraphs
• Computing maximal subsemigroups of a finite semigroup
• scientific article; zbMATH DE number 3898926

Cites work

• A note on finding the bridges of a graph
• Graph puzzles, homotopy, and the alternating group
• Graph theory
• scientific article; zbMATH DE number 3179521 (Why is no real title available?)
• scientific article; zbMATH DE number 1261512 (Why is no real title available?)
• scientific article; zbMATH DE number 830463 (Why is no real title available?)
• scientific article; zbMATH DE number 894528 (Why is no real title available?)
• scientific article; zbMATH DE number 3284302 (Why is no real title available?)
• Lower bounds for complexity of finite semigroups
• Structural aspects of semigroups based on digraphs

Cited in

(3)

• Flows on regular semigroups
• Structural aspects of semigroups based on digraphs
• Optimisation via encodings: a renormalisation group perspective

Describes a project that uses

Uses Software

• Algorithm 447

This page was built for publication: The maximal subgroups and the complexity of the flow semigroup of finite (di)graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4596405)