Balancing permuted copies of multigraphs and integer matrices

DOI10.1016/J.JCTA.2023.105756MaRDI QIDQ6162862zbMATH OpenOpenAlexFDO

Authors Coen del Valle, Peter Dukes

Publication date 26 June 2023

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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

zbMATH Keywords

combinatorial matrix theorygraph decompositionpermutation

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial aspects of block designs (05B05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph designs and isomorphic decomposition (05C51) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Eigenvalues, singular values, and eigenvectors (15A18)

Abstract: Given a square matrix $A$ over the integers, we consider the $mathbbZ$-module $M_A$ generated by the set of all matrices that are permutation-similar to $A$. Motivated by analogous problems on signed graph decompositions and block designs, we are interested in the completely symmetric matrices $aI+bJ$ belonging to $M_A$. We give a relatively fast method to compute a generator for such matrices, avoiding the need for a very large canonical form over $mathbbZ$. We consider several special cases in detail. In particular, the problem for symmetric matrices answers a question of Cameron and Cioabv{a} on determining the eventual period for integers $lambda$ such that the $lambda$-fold complete graph $lambda{K}_n$ has an edge-decomposition into a given (multi)graph.

Recommendations

• Maximising the permanent and complementary permanent of (0,1)-matrices with constant line sum
• Commuting decompositions of complete graphs
• Balanced \(0,\pm 1\) matrices. I: Decomposition
• A graph theoretic upper bound on the permanent of a nonnegative integer matrix. II. The extremal case
• Circulant blocks and rotational graphs

Cites work

• A graph partition problem
• A linear algebraic approach to directed designs
• An existence theory for loopy graph decompositions
• Asymptotic Existence of Resolvable Graph Designs
• Diagonal forms of incidence matrices associated with \(t\)-uniform hypergraphs
• scientific article; zbMATH DE number 3458752 (Why is no real title available?)
• scientific article; zbMATH DE number 3503285 (Why is no real title available?)
• Progress towards Nash-Williams' conjecture on triangle decompositions
• Signed hypergraph designs and diagonal forms for some incidence matrices
• Smith normal forms of incidence matrices
• The module structure of integral designs
• The Smith normal form

Cited in

(1)

• Combinatorics of balanced carries

This page was built for publication: Balancing permuted copies of multigraphs and integer matrices

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