Biased graphs. VII: Contrabalance and antivoltages. (English) Zbl 1125.05048
Summary: We develop linear representation theory for bicircular matroids, a chief example being a matroid associated with forests of a graph, and bicircular lift matroids, a chief example being a matroid associated with spanning forests. (These are bias and lift matroids of contrabalanced biased graphs.) The theory is expressed largely in terms of antivoltages (edge labellings that defy Kirchhoff’s voltage law) with values in the multiplicative or additive group of the scalar field. We emphasize antivoltages with values in cyclic groups and finite vector spaces since they are crucial for representing the matroids over finite fields; and integer-valued antivoltages with bounded breadth since they are crucial in constructions. We find bounds for the existence of antivoltages and we solve some examples. Other results: The number of antivoltages in an abelian group is a polynomial function of the group order, and the number of integral antivoltages with bounded breadth is a polynomial in the breadth bound. We conclude with an application to complex representation. There are many open questions.
MSC:
| 05C22 | Signed and weighted graphs |
| 05B35 | Combinatorial aspects of matroids and geometric lattices |
Keywords:
Antivoltage; Bicircular matroid; Bicircular lift matroid; Forest matroid; Spanning forest matroid; Biased graph; Gain graph; Contrabalance; Bias matroid; Frame matroid; Matroid representation; Transversal matroidReferences:
| [1] | Beck, Matthias; Zaslavsky, Thomas, Inside-out polytopes, Adv. Math., 205, 1, 134-162 (2006), MR 2007e:52017 · Zbl 1107.52009 |
| [2] | Chartrand, Gary; Harary, Frank, Planar permutation graphs, Ann. Inst. H. Poincaré Sect. B (N.S.), 3, 433-438 (1967), MR 37#2626 · Zbl 0162.27605 |
| [3] | Gagola, S. M., Solution to Problem 10606, Avoiding the identity, Amer. Math. Monthly, 106, 6, 590-591 (June-July 1999) |
| [4] | Klee, Victor, The greedy algorithm for finitary and cofinitary matroids, (Motzkin, T. S., Combinatorics. Combinatorics, Proc. Sympos. Pure Math., vol. 19 (1971), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI), 137-152, MR 48#10865 · Zbl 0229.05031 |
| [5] | Matthews, L. R., Bicircular matroids, Quart. J. Math. Oxford (2), 28, 213-227 (1977), MR 58#21732 · Zbl 0386.05022 |
| [6] | Orlik, Peter; Terao, Hiroaki, Arrangements of Hyperplanes, Grundlehren Math. Wiss., vol. 300 (1992), Springer-Verlag: Springer-Verlag Berlin, MR 94e:52014 · Zbl 0757.55001 |
| [7] | Oxley, J. G., Matroid Theory (1992), Oxford Univ. Press: Oxford Univ. Press Oxford, MR 94d:05033 · Zbl 0784.05002 |
| [8] | Piff, M. J.; Welsh, D. J.A., On the vector representation of matroids, J. London Math. Soc. (2), 2, 284-288 (1970), MR 41#3308 · Zbl 0213.29102 |
| [9] | Robertson, N.; Seymour, P. D., Graph minors—A survey, (Anderson, I., Surveys in Combinatorics 1985. Surveys in Combinatorics 1985, London Math. Soc. Lecture Note Ser., vol. 103 (1985), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 153-171, MR 87e:05130 · Zbl 0764.05069 |
| [10] | Robertson, N.; Seymour, P. D., Graph minors. XX. Wagner’s conjecture, J. Combin. Theory Ser. B, 92, 2, 325-357 (2004), MR 2005m:05204 · Zbl 1061.05088 |
| [11] | Simões-Pereira, J. M.S., On subgraphs as matroid cells, Math. Z., 127, 315-322 (1972), MR 47#6522 · Zbl 0226.05016 |
| [12] | Simões-Pereira, J. M.S., On matroids on edge sets of graphs with connected subgraphs as circuits II, Discrete Math., 12, 55-78 (1975), MR 54#7298 · Zbl 0307.05129 |
| [13] | Zaslavsky, Thomas, Bicircular geometry and the lattice of forests of a graph, Quart. J. Math. Oxford Ser. (2), 33, 493-511 (1982), MR 84h:05050c · Zbl 0519.05020 |
| [14] | Thomas Zaslavsky, Geometric lattices of structured partitions. I: Gain-graphic matroids and group valued partitions, manuscript, 1985; Thomas Zaslavsky, Geometric lattices of structured partitions. I: Gain-graphic matroids and group valued partitions, manuscript, 1985 |
| [15] | Zaslavsky, Thomas, Biased graphs. IV. Geometrical realizations, J. Combin. Theory Ser. B, 89, 231-297 (2003), MR 2005b:05057 · Zbl 1031.05034 |
| [16] | Zaslavsky, Thomas, Frame matroids and biased graphs, European J. Combin., 15, 303-307 (1994), MR 95a:05021 · Zbl 0797.05027 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
