Publications and So Forth

of Thomas Zaslavsky

Best Viewed With Any Browser

(* Abstracts, announcements, summaries, and essentially expository works.)

Index

Topical List (on a separate page) (as of 2021).

Published Works

  1. [FUTA] "Facing up to arrangements: Face-count formulas for partitions of space by hyperplanes". Thesis (MIT, 1974) and Mem. Amer. Math. Soc., No. 154, Amer. Math. Soc., Providence, R.I., 1975. MR 50 #9603. Zbl 296.50010.
      Main results: the number of regions, or bounded regions, of an affine real hyperplane arrangement, is determined by the (semi)lattice of flats through the characteristic polynomial, as is the number of regions of a projective real arrangement.
  2. [CFCUS] "Counting the faces of cut-up spaces". Bull. Amer. Math. Soc., 81 (1975), 916–918. MR 53 #3901. Zbl 317.05012.
      Summary of [4 CATD].
      (Download published article in PDF: 230 kB. Paper reprints available.)
  3. [MDS] "Maximal dissections of a simplex". J. Combinatorial Theory Ser. A, 20 (1976), 244–257. MR 53 #3891. Zbl 334.05011.
      The hyperplanes are "apical", that is, determined by a point in one edge together with the opposite face. The results are generic. They turned out to depend on the bicircular matroid; see [14 BGLF].
  4. [CATD] "A combinatorial analysis of topological dissections". Advances in Math., 25 (1977), 267–285. MR 56 #5310. Zbl 406.05004.
      Topological generalization of [1 FUTA], including what I now call "topological hyperplanes" [75 DTH]: dissecting topological spaces by subspaces, how many regions are there? The answers are complicated and not as general as the question.
      (Paper reprints available.)
  5. *[AHMG] "Arrangements of hyperplanes; matroids and graphs". In: Proc. Tenth Southeastern Conf. on Combinatorics, Graph Theory and Computing (Boca Raton, 1979), Vol. II, pp. 895–911. Utilitas Math. Publ. Inc., Winnipeg, Man., 1979. MR 81h:05043. Zbl 434.05023.
      Summary of parts of [1 FUTA] and [19 IWN].
      (Download in PDF: 4 MB.)
  6. [GRS] "The geometry of root systems and signed graphs". Amer. Math. Monthly, 88 (Feb., 1981), no. 2, 88–105. MR 82g:05012. Zbl 466.05058.
      A friendly introduction to signed graphs through their hyperplanar representation.
      (Download in PDF: 520 kB. Paper reprints available.)
  7. [CMV] "Complementary matching vectors and the uniform matching extension property". European J. Combinatorics, 2 (1981), 91–103. MR 82j:05090a. Zbl 464.05049. Correction, ibid., 2(1981), 305. MR 82j:05090b. Zbl 478.05073.
      When is the matching vector/polynomial of a graph determined by that of its complement? Generalized to weighted graphs and solved.
      (Paper reprints available.)
  8. [Clad] (with F. R. McMorris) "The number of cladistic characters". Math. Biosciences, 54 (1981), 3–10. MR 82j:92008. Zbl 454.92003.
      A cladistic character is a nested partition class.
      (Download in PDF: 2.5 MB.)
  9. [CSG] "Characterizations of signed graphs". J. Graph Theory, 5 (1981), 401–406. MR 83a:05122. Zbl 471.05035.
      Characterizing the sets of positive circles of signatures of a graph.
      (Download in PDF: 430 kB. Paper reprints available.)
  10. [SA2] "The slimmest arrangements of hyperplanes: II. Basepointed geometric lattices and Euclidean arrangements". Mathematika, 28 (1981), 169–190. MR 86h:52010. Zbl 483.51012.
      Characterizes the geometric semilattices of given rank and number of atoms that have the smallest possible doubly indexed Whitney numbers of the first and second kinds; application to real affine hyperplane arrangements with the fewest possible faces.
      (Paper reprints available.)
  11. [SG] "Signed graphs". Discrete Appl. Math., 4 (1982), 47–74. MR 84e:05095a. Zbl 476.05080. Erratum, ibid., 5 (1983), 248. MR 84e:05095b. Zbl 503.05060.
      Basic theory of signed graphs and their matroids, with double covering graph, incidence and adjacency matrices, matrix-tree analog, examples.
      The erratum corrects Theorem 5.1 and Corollary 7D.3 (g); an error in (f) is corrected in [34 BG2, Theorem 2.1].
      (Download in PDF: 2.8 MB.)
  12. [SGC] "Signed graph coloring". Discrete Math., 39 (1982), 215–228. MR 84h:05050a. Zbl 487.05027.
      Signed coloring; the two chromatic polynomials; interpretation at negative arguments in terms of acyclic orientations. Examples are in [13 CISG].
      (Download in PDF: 1.5 MB.)
  13. [CISG] "Chromatic invariants of signed graphs". Discrete Math., 42 (1982), 287–312. MR 84h:05050b. Zbl 498.05030.
      Sequel to [12 SGC]. Many kinds of examples.
      Eqns. (2.2) and (2.3) should have λ/2 instead of λ on the right-hand side (thanks to Eckhard Steffen).
      (Download in PDF: 3.8 MB.)
  14. [BGLF] "Bicircular geometry and the lattice of forests of a graph". Quart. J. Math. Oxford (2), 33 (1982), 493–511. MR 84h:05050c. Zbl 519.05020.
      The set of all forests of a graph, suitably ordered, forms a geometric lattice in which corank is the number of trees in the forest.
      ( Paper reprints available.)
  15. *[VGM] "Voltage-graphic matroids". In: Matroid Theory and Its Applications (Proc. C.I.M.E., Varenna, Italy, 1980), ed. Adriano Barlotti, pp. 417–423. Liguori Editore, Naples, 1982. MR 87g:05003 (book). Zbl 1225.05002 (book).
      Summary of parts of [11-14 SG-SGC-CISG-BGLF], [31 BG1], [34], [45 BG3], [60 BG4].
      (Download in PostScript: 250 kB; PDF 85 kB.)
  16. [BDG] (with F. R. McMorris) "Bound graphs of a partially ordered set". J. Combin. Inform. System Sci., 7 (1982), 134–138. MR 84g:05123. Zbl 525.05060.
      Upper bound graph UB: edge xy if {x,y} has an upper bound. Lower bound graph LB: the dual definition. Double bound graph DB: UB intersect LB. Theorems characterize graphs that are UB's or DB's.
      An error in the characterization of DB's was corrected by Debra Diny, "The double bound graph of a partially ordered set". J. Combin. Inform. System Sci., 10 (1985), no. 1-2, 52–56. MR 90b:05114.
      (Download in PDF: 2.0 MB. Paper reprints available.)
  17. [SA1] "The slimmest arrangements of hyperplanes: I. Geometric lattices and projective arrangements". Geometriae Dedicata, 14 (1983), 243–259. MR 85g:52004. Zbl 537.05017.
      Characterizes the geometric lattices of given rank and number of atoms that have the smallest possible doubly indexed Whitney numbers of the first and second kinds (absolute values, for the first kind); application to homogeneous real hyperplane arrangements with the fewest possible faces.
  18. [UDS] "Uniform distribution of a subgraph in a graph". Combinatorial Mathematics (Proc. Colloq. Internat., Marseille-Luminy, 1981), ed. C. Berge et al. Ann. Discrete Math., 17 (1983), 657–664. MR 87f:05163. Zbl 525.05053.
      Uniform distribution means every induced subgraph contains the same number of copies of the specified subgraph.
      (Paper reprints available.)
  19. [IWN] (with Curtis Greene) "On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-Radon partitions, and orientations of graphs". Trans. Amer. Math. Soc., 280 (1983), no. 1, 97–126. MR 84k:05032. Zbl 539.05024.
      Extensive treatment of the geometrical and graph-theoretical (and signed-graphical) meaning of the Whitney numbers of the first kind of a geometric lattice.
      (Download in PDF: 900 kB. Paper reprints available.)
  20. [AvS] (with P. D. Seymour) "Averaging sets: A generalization of mean values and spherical designs". Advances in Math., 52 (1984), 213–240. MR 85m:05031. Zbl 596.05012.
      Principal corollary: spherical t-designs of all sufficiently large sizes exist in all dimensions. The main theorem is the generalization to arbitrary path-connected topological spaces (generalizing the sphere) and any finite-dimensional family of continuous functions (generalizing polynomials of degree at most t).
      (Paper reprints available.)
  21. [HC] "How colorful the signed graph?". Discrete Math., 52 (1984), 279–284. MR 86m:05045. Zbl 554.05026.
      The chromatic number of a signed graph is at most n. When is it n or n−1?
      (Download in PDF: 650 kB. Paper reprints available.)
  22. [MT] "Multipartite togs (analogs of two-graphs) and regular bitogs". Proc. Fifteenth Southeastern Conf. on Combinatorics, Graph Theory and Computing (Baton Rouge, 1984), Vol. III. Congressus Numerantium, 45 (1984), 281–293. MR 86d:05109. Zbl 625.05044.
      A bipartite analog of two-graphs.
      (Paper reprints available.)
  23. [GMGH] "Generalized matchings and generalized Hermite polynomials". Finite and Infinite Sets (Proc. Sixth Hungarian Colloq. on Combinatorics, Eger, 1981), ed. A. Hajnal, L. Lovasz, and V. T. Sós, Vol. II, pp. 851–865. Colloq. Math. Soc. Janos Bolyai, 37. Soc. Math. Janos Bolyai, Budapest, and North-Holland, Amsterdam, 1984. MR 87e:05120. Zbl 612.05051.
      Generalized matchings are multiple copies of a specified complete graph.
      (Paper reprints available.)
  24. [Asymp] (with Attila Maté and Paul Nevai) "Asymptotic expansions of ratios of coefficients of orthogonal polynomials with exponential weights". Trans. Amer. Math. Soc., 287 (1985), no. 2, 495–505. MR 86b:42024. Zbl 536.42023 (547.42012).
      I contributed a minor combinatorial calculation.
      (Download in PDF: 270 kB.)
  25. [XAH] Extremal arrangements of hyperplanes". Discrete Geometry and Convexity (Proc., New York, 1982). Ann. New York Acad. Sci., 440 (1985), 69–87. MR 87m:51053. Zbl 572.51015.
      Includes summary of [10 SA2] and [17 SA1] and new results, especially spherical analogs of hyperplanar theorems.
      (Paper reprints available.)
  26. [BGMB] "The biased graphs whose matroids are binary". J. Combinatorial Theory Ser. B, 42 (1987), 337–347. MR 88h:05082. Zbl 667.05015.
      The matroids of a biased graph are the frame ("bias") G, lift L, and extended lift L0 matroids.
      (Paper reprints available.)
      An error in Cor. 4.3 (leading to an error in [33 SBM]): In the last statement, omit "G(Φ) = L(Φ)". That is true when Φ has no loops, but may not be if Φ has a loop e (because Theorem 3(3) applies with unbalanced block e, but (E-e,e) is not a 2-separation). (Thanks to Stefan van Zwam, 25 July 2007.)
  27. [BDSG] "Balanced decompositions of a signed graph". J. Combinatorial Theory Ser. B, 43 (1987), 1–13. MR 89c:05058. Zbl 624.05056.
      A failed attempt to generalize the Tutte and Nash-Williams theorems to signed graphs.
      (Paper reprints available.)
  28. *[muCh] "The Möbius function and the characteristic polynomial". Chapter 7, pp. 114–138, of Combinatorial Geometries, ed. Neil White. Encyclopedia of Math. and its Appl., Vol. 29. Cambridge Univ. Press, Cambridge, 1987. MR 88g:05048 (book). Zbl 632.05017.
      (Download in PDF: 3.8 megabytes.
  29. [VLI] "Vertices of localized imbalance in a biased graph". Proc. Amer. Math. Soc., 101 (1987), no. 1, 199–204. MR 88f:05103. Zbl 622.05054.
      A balancing vertex is a vertex in an unbalanced biased graph whose deletion leaves a balanced graph.
      (Download in PDF: 160 kB.)
  30. [Togs] "Togs (generalizations of two-graphs)". In: Optimization, Design of Experiments and Graph Theory (Proc. Symp., Bombay, 1986), ed. M.N. Gopalan and G.A. Patwardhan, pp. 314–334. Indian Inst. of Technology, Bombay, 1988. MR 90h:05112. Zbl 689.05035.
      (Download in PDF: 275 kB; dvi: 108 kB; compressed PS: 166 kB. Paper reprints available.)
  31. [BG1] "Biased graphs. I. Bias, balance and gains". J. Combinatorial Theory Ser. B, 47 (1989), 32–52. MR 90k:05138. Zbl 714.05057.
      Definition and basic properties of biased graphs; biased graphs derived from gain graphs. Continued in [34 BG2], [45 BG3], [60 BG4], [102 BG6], [72 BG7], and unpublished [BG5], [BG8].
      (Download in PDF: 1.9 MB. Paper reprints available.)
  32. [MEGS] "Matroids determine the embeddability of graphs in surfaces". Proc. Amer. Math. Soc., 106 (1989), no. 4, 1131–1135. MR 90a:05075. Zbl 674.05025.
      The surfaces in which a graph can embed are determined by its matroid. A synthesis of previous work (by others) on embeddability under 1- and 2-point amalgamation.
      (Download in PDF: 150 kB. Paper reprints available.)
  33. [SBM] "Biased graphs whose matroids are special binary matroids". Graphs and Combinatorics, 6 (1990), 77–93. MR 91f:05097. Zbl 786.05020.
      The special binary matroids are those in the traditional excluded-minor theorems, i.e., the Fano plane, its dual, and the matroids and dual matroids of the Kuratowski graphs, and also the matroids of all complete graphs. The matroids of a biased graph are the frame ("bias") matroid G, lift matroid L, and extended (or "complete") lift matroid L0.
      (Download in PDF: 1400 kB. Paper reprints available.)
      Stefan van Zwam (25 July 2007) pointed out an error. The graphs <+Kno> = a balanced Kn with a negative loop at every vertex, were overlooked in the last statement of Lemma 1H (due to an oversight in [26 BGMB, Cor. 4.3]) and thus in Props. 2A and 5A.
    • A corrected last statement of Lemma 1H is: ``If Ω has no two vertex-disjoint negative circles, then G(Ω) = M iff L(Ω) = M.''
    • In Prop. 2A, Ω = <+K3o> should be added to the list for G(K4).
    • In Prop. 5A, Ω = <+Km-1o> should be added to the list for G(Km).
  34. [BG2] "Biased graphs. II. The three matroids". J. Combinatorial Theory Ser. B, 51 (1991), 46–72. MR 91m:05056. Zbl 763.05096.
      The frame (here called "bias") matroid G and the lift and complete lift matroids L and L0. Multiple definitions; basic properties; comparison of the frame and lift matroids and intermediate matroids; remarks on infinitary versions.
      (Download part a and part b in PDF: 2.2+.7 MB. Paper reprints available.)
  35. [1/7] (with Jeffrey C. Lagarias) Advanced Problem 6661, "The curious behavior of 1/7". Amer. Math. Monthly, 98 (June-July 1991), no. 6, 559.
      Submitted as a solved problem. The first complete solution of this often-raised question. The solution by K. Ford, ibid., 100 (Feb. 1993), no. 2, 191–194, is elementary and elegant.
      (Download PDF in PDF: 40 kB.)
  36. [OSG] "Orientation of signed graphs". European J. Combinatorics, 12 (1991), no. 4, 361–375. MR 93a:05065. Zbl 761.05095.
      Oriented signed graphs are identical to the bidirected graphs introduced by Edmonds. Basic theory; oriented matroid theory; geometrical interpretation of acyclic orientations as regions of the associated hyperplane arrangement; the hyperplane arrangement as a cross-section of the double-covering-graph arrangement.
      (Download in PDF: 1.4 MB. Paper reprints available.)
  37. [OESG] "Orientation embedding of signed graphs". J. Graph Theory, 16 (1992), no. 5, 399–422. MR 93i:05056. Zbl 778.05033.
      Unpublished corrigenda in PostScript or dvi format.
      Orientation embedding means topological embedding in a surface so that positive circles preserve orientation and negative circles reverse it. Main theorem: the minimal surface of a signed graph with a 1-separation is determined by the two halves of the separation.
      (Paper reprints available.)
  38. [STF] "Strong Tutte functions of matroids and graphs". Trans. Amer. Math. Soc., 334 (1992), no. 1, 317–347. MR 93a:05047. Zbl 781.05012.
      A strong Tutte function satisfies a parametrized deletion-contraction law, with parameters that may depend on the element being deleted and contracted, and also a multiplicative law. Main result: classification of all such functions (taking values in any field) on all minor-closed classes of matroids. Applications to graphs; special types of strong Tutte functions; dualities.
      (Download in PDF: 750 kB. Paper reprints available.)
  39. [PPSG] "The projective-planar signed graphs". Discrete Math., 113 (1993), 223–247. MR 94d:05047. Zbl 779.05018.
      Forbidden minors for orientation embeddability of a signed graph in the projective plane. (There are 6 of them, and 8 forbidden topological subgraphs.)
      (Paper reprints available.)
  40. [CROC] (with Patrick Solé) "The covering radius of the cycle code of a graph". Discrete Appl. Math., 45 (1993), 63–70. MR 94d:94029. Zbl 778.94008.
      (Paper reprints available.)
  41. [MOC] (with Patrick Solé) "Maximality of the cycle code of a graph". Discrete Math., 128 (1994), 401–405. MR 94m:05164. Zbl 794.05114.
      (Paper reprints available.)
  42. [FrM] "Frame matroids and biased graphs". European J. Combinatorics, 15 (1994), 303–307. MR 95a:05021. Zbl 797.05027.
      A frame matroid is a submatroid of a matroid in which there is a basis whose generated lines contain the whole matroid. Main theorem: a finitary frame matroid is the same as the bias matroid of a biased graph. (Hence the recommended name "frame matroid of a biased graph" as synonym for "bias matroid".)
      (Download in PDF: 170 kB. Paper reprints available.)
  43. [CAS] (with Patrick Solé) "A coding approach to signed graphs". SIAM J. Discrete Math., 7 (1994), 544–553. MR 95k:94041. Zbl 811.05034.
      The covering radius of the code is the frustration index of the signed graph.
      (Paper reprints available.)
  44. [SCN] "The signed chromatic number of the projective plane and Klein bottle and antipodal graph coloring". J. Combinatorial Theory Ser. B, 63 (1995), 136–145. MR 95j:05099. Zbl 822.05028.
      The maximum chromatic number and zero-free chromatic number of a signed graph that is orientation embedded in either of these surfaces. Antipodal graph coloring is coloring that is antipodally symmetric, of an ordinary graph that is embedded with antipodal symmetry in the sphere or torus.
      (Download in PDF: 450 kB. Paper reprints available.)
  45. [BG3] "Biased graphs. III. Chromatic and dichromatic invariants". J. Combinatorial Theory Ser. B, 64 (1995), 17–88. MR 96g:05139. Zbl 857.05088.
      The chromatic, dichromatic, and (4-variable) polychromatic polynomials of a biased graph. Equivalence to characteristic, corank-nullity, and other polynomials of the frame ("bias") matroid and to chromatic polynomials defined by coloring in gain graphs. Connection to lift-matroid polynomials. Expansion formulas. Detailed treatment of examples including bicircular matroids (from contrabalanced bias) and generalized Dowling geometries.
      (Download in PDF: 2.4 MB.)
  46. [PEG] "The order upper bound on parity embedding of a graph". J. Combinatorial Theory Ser. B, 68 (1996), 149–160. MR 98f:05055. Zbl 856.05030.
      The demigenus (i.e., minimal surface), under orientation embedding, of the all-negative complete graph with loops.
      (Download in PDF: 410 kB. Paper reprints available.)
  47. [SGE] "Is there a matroid theory of signed graph embedding?" Ars Combinatoria, 45 (1997), 129–141. MR 97m:05084. Zbl 933.05067.
      Orientation embedding of a signed graph is related to the lift matroid.
      (Download in PDF: 1860 kB. Paper reprints available.)
  48. [PESG] "The largest parity demigenus of a simple graph". J. Combinatorial Theory Ser. B, 70 (1997), 325–345. MR 99e:05043. Zbl 890.05024.
      The demigenus (i.e., minimal surface), under orientation embedding, of the all-negative complete graph without loops.
      (Download in PDF: 430 kB. Paper reprints available.)
  49. [AvId] Problem 10606, "Avoiding the identity". Amer. Math. Monthly, 104 (Aug.-Sept., 1997), no. 7, 664.
      Submitted as a solved problem. Solution by Stephen M. Gagola, ibid., 106 (June-July 1999), no. 6, 590–591.
      (Download problem and solution in PDF: 100 + 80 kB.)
  50. [TPOS] (with Phil Hanlon) "Tractable partially ordered sets derived from root systems and biased graphs". Order, 14 (1997-98), 229–257. MR 2000a:06016. Zbl 912.06003.
      (Download prepublication version in dvi: 125 kB; compressed PS: 180 kB.)
      (Download in PDF: 275 kB. Paper reprints available.)
  51. [SABG] "Signed analogs of bipartite graphs". Discrete Math., 179 (1998), 205–216. MR 2000b:05067. Zbl 890.05060.
      (Download prepublication version in PostScript: 245 kB.)
      (Download in PDF: 700 kB. Paper reprints available.)
  52. *[MBSG] "A mathematical bibliography of signed and gain graphs and allied areas". Electronic J. Combinatorics, Dynamic Surveys in Combinatorics (1998), Number DS8. MR 2000m:05001a. Zbl 898.05001.
      Edition 6a (iv + 124 pp.): 1998 July 20.
      Edition 7 (vi + 151 pp.): 1999 September 22.
      Edition 8 (vi + 340 pp.): 2012 September 6.
      Edition 9 (vi + 518 pp.): 2018 December 21.
      For the most recent update see the Home Page of Signed, Gain, and Biased Graphs.
  53. *[GSG] "Glossary of signed and gain graphs and allied areas". Electronic J. Combinatorics, Dynamic Surveys in Combinatorics (1998), Number DS9. MR 2000m:05001b. Zbl 898.05002.
      Edition 1: 1998 July 21 (25 pp.).
      Edition 2: 1998 September 18 (41 pp.).
  54. [SSF] "Supersolvable frame-matroid and graphic-lift lattices". European J. Combinatorics, 22 (2001), no. 1, 119–133. MR 2001k:05051. Zbl 890.05060.
      Biased/signed/gain graphs with supersolvable frame ("bias") or lift matroids are generalized simplicial extensions.
      (Download prepublication version in dvi: 80 kB; PostScript: 470 kB; compressed PS: 130 kB. Paper reprints available.)
      Correction to the description of modular flats, and a better proof, by Lori Koban, "Comments on 'Supersolvable frame-matroid and graphic-lift lattices' by T. Zaslavsky [European Journal of Combinatorics 22 (2001) 119]". European J. Combinatorics, 25 (2004), no. 1, 141–144.
  55. [LDB] "The largest demigenus of a bipartite signed graph". Discrete Math., 232 (2001), 189–193. MR 2001m:05100. Zbl 982.05041.
      The demigenus (i.e., minimal surface) for orientation embedding of a bipartite signed graph with all possible positive and negative edges.
      (Download prepublication version in dvi: 20 kB; PostScript: 170 kB. Paper reprints available.)
  56. [PDS] "Perpendicular dissections of space". Discrete Comput. Geom., 27 (2002), 303–351. MR 2003i:52026. Zbl 1001.52011.
      Euclidean space is dissected by hyperplanes that are perpendicular to the lines determined by a finite set of reference points. A hyperplane is specified by a pair of reference points and a "Pythagorean gain". The number of regions into which these hyperplanes cut the space is (generically) independent of the reference points, depending only on the gains.
      (Download corrected postpublication version with the missing reference (45 pp., with 10 figures) in PDF: 450 kB; PostScript: 850 kB.)
      (Download prepublication version (45 pp., with 10 figures) in dvi: 200 kB; PostScript: 850 kB; compressed PS: 350 kB. Paper reprints available.)
      (Download reference, accidentally omitted from published paper: PDF: 25 kB; PostScript: 65 kB.)
  57. [MHH] (with Matthias Beck) "A shorter, simpler, stronger proof of the Meshalkin–Hochberg–Hirsch bounds on componentwise antichains". J. Combinatorial Theory Ser. A, 100 (2002), 196–199. MR 2003h:05183. Zbl 1028.05111.
      A very short, efficient, and general proof of a generalization of Sperner's theorem on antichains of sets.
      (arXiv:math.CO/0112068. Paper reprints available.)
  58. [MPG] (with Matthias Beck) "A Meshalkin theorem for projective geometries". J. Combinatorial Theory Ser. A, 102 (2003), 433–441. MR 2004h:51007. Zbl 1018.05100.
      The proof of [57 MHH], applied to the lattice of flats of a projective geometry.
      (arXiv:math.CO/0112069. Paper reprints available.)
  59. [IDP] "Faces of a hyperplane arrangement enumerated by ideal dimension, with application to plane, plaids, and Shi". Geometriae Dedicata, 98 (2003), 63–80. MR 2004f:52025. Zbl 1041.52021.
      The "ideal dimension" of a face is the dimension of the infinite part of the projective closure.
      (Download prepublication version in PostScript: 400 kB; compressed PS: 180 kB. Paper reprints available.)
  60. [BG4] "Biased graphs. IV: Geometrical realizations". J. Combinatorial Theory Ser. B, 89 (2003), no. 2, 231–297. MR 2005b:05057. Zbl 1031.05034.
      The geometry of biased graphs: many kinds of linear, projective, and affine representations of the frame and lift matroids. Especially, canonical representations and, for many biased graphs, a kind of uniqueness of representation in terms of possible gain functions. Reexamined by a synthetic treatment in [BG6].
      (Download prepublication version (62 pp., with 7 figures) in PostScript: 1000 kB; compressed PS: 450 kB; PDF (no figures): 500 kB.)
  61. [Dice] (with Matthias Beck and Richard Ehrenborg) Problem 11099, "Magic squares and nontransitive dice". Amer. Math. Monthly, 111 (Aug.-Sept., 2004), no. 11, 625–626.
      Inconsistent dice made from magic squares.
      Submitted as a solved problem. Solution by Michael R. Avidon and John H. Lindsey II, ibid., 113 (2006), no. 5, 464–465.
      (Download problem in PDF: 200 kB.)
  62. [PQC] "Periodicity in quasipolynomial convolution". Electronic J. Combinatorics, 11 (2) (2004-2005), Article R11 and comment (correction), 6+1 pp. MR 2005m:39038, MR2195421. Zbl 1062.05012.
      The periods of the coefficients of a convolution. The null space of a circulant matrix.
      (Download corrected article (6 pp.) in PostScript: 290 kB; PDF: 160 kB.)
  63. [CBA] (with Konstantin Rybnikov) "Criteria for balance in abelian gain graphs, with an application to piecewise-linear geometry". Discrete Comput. Geom., 34 (2005), no. 2, 251–268. MR 2006f:05086. Zbl 1074.05047.
      A homological criterion for balance. Application to generalizing Voronoi's lifting theorem from tilings to PL immersions.
      (arXiv:math.CO/0210052. Or, download in PostScript: 485 kB; PDF: 240 kB. Paper reprints available.)
  64. [CCB] (with Konstantin Rybnikov) "Cycle and circle tests of balance in gain graphs: Forbidden minors and their groups". J. Graph Theory, 51 (2006), no. 1, 1–21. MR 2006i:05078. Zbl 1085.05033.
      Graph-theoretic study of when the naive criterion for balance of a gain graph (that all members of a binary cycle basis be balanced) is valid.
      (arXiv:math.CO/0209316. Or, download in PostScript: 425 kB; PDF: 210 kB. Paper reprints available.)
  65. *[QAX] "Quasigroup associativity and biased expansion graphs". Electron. Res. Announc. Amer. Math. Soc., 12 (2006), 13–18 (electronic). MR 2006i:20081. Zbl 1113.05044.
      Summary of [82 AMQ].
      (Download in PostScript: 260 kB; PDF: 150 kB.)
  66. [UGS] (with Matthias Beck and Xueqin Wang) "A unifying generalization of Sperner's theorem". In: Ervin Györi, Gyula O.H. Katona, and Lászlo Lovász, eds., More Sets, Graphs and Numbers: A Salute to Vera Sós and András Hajnal. Bolyai Soc. Math. Stud., Vol. 15, pp. 9–24. Springer, Berlin, and János Bolyai Mathematical Society, Budapest, 2006. MR 2008c:05184. Zbl 1094.05055.
      Unifies Erdos's, Meshalkin's, and Griggs et al.'s generalizations and the LYM refinements in a single master theorem. Based in part on a simplification of the necessary Harper-Rota lemma.
      (arXiv:math.CO/0112067.
  67. [HIB] (with Ethan D. Bolker) "A simple algorithm that proves half-integrality of bidirected network programming". Networks, 48 (2006), no. 1, 36–38. MR 2007b:05098. Zbl 1100.05046.
      Based on minimal integral flows on a matroid circuit of a signed graph.
      (Download prepublication version in PostScript: 200 kB; PDF: 100 kB. Paper reprints available.)
  68. [IOP] (with Matthias Beck) "Inside-out polytopes". Advances in Math., 205 (2006), no. 1, 134–162. MR 2007e:52017. Zbl 1107.52009.
      Part of the boundary is made up of forbidden hyperplanes inside the polytope. Enumerative applications include graph and signed-graph coloring, compositions of an integer, and antimagic squares. More applications in [69 NNZ], [70 MML], [77 SLS].
      (arXiv:math.CO/0309330. Or, download prepublication version in PostScript: 650 kB; PDF: 375 kB. Paper reprints available.)
  69. [NNZ] (with Matthias Beck) "The number of nowhere-zero flows on graphs and signed graphs". J. Combinatorial Theory Ser. B, 96 (2006), no. 6, 901–918. MR 2007k:05084. Zbl 1119.05105.
      Basic counting theory of nowhere-zero flows (a) on graphs with bounded integral values, (b) on signed graphs with values in a finite abelian group, (c) on signed graphs with bounded integral values. Application of the theory of [68 IOP].
      (arXiv:math.CO/0309331. Or, download prepublication version in PostScript: 450 kB; PDF: 250 kB. Paper reprints available.)
  70. [MML] (with Matthias Beck) "An enumerative geometry for magic and magilatin labellings". Ann. Combinatorics, 10 (2006), no. 4, 395–413. MR 2007m:05010. Zbl 1116.05071.
      Label a finite point set by positive integers so the sum on each of a fixed class of subsets is the same. The labelling is magic if by distinct integers, magilatin if by integers that are distinct within each subset. The number of such labellings with either a given upper bound t or a specified magic sum t is a quasipolynomial function of t. Examples: magic squares, semimagic squares, latin squares (whose 3×3 examples are completely solved in [77 SLS]). Generalized to linear forms. This is an application of the theory of [68 IOP].
      (arXiv:math/0506315. Or, download prepublication version in PostScript: 450 kB; PDF: 250 kB. Paper reprints available.)
  71. [SOA] (with David Forge) "Lattice point counts for the Shi arrangement and other affinographic hyperplane arrangements". J. Combinatorial Theory Ser. A, 114 (2007), no. 1, 97–109. MR 2275583 (2007i:52026). Zbl 1105.52014.
      Counting bounded lattice points not covered by an affinographic hyperplane arrangement is equivalent to bounded integral proper coloring of an integral gain graph. Generalization to rooted integral gain graphs. Also, a modular analog.
      (arXiv:math/0609051. Download prepublication version in PostScript: 400 kB; PDF: 235 kB. Paper reprints available.)
  72. [BG7] "Biased graphs. VII. Contrabalance and antivoltages". J. Combinatorial Theory Ser. B, 97 (2007), no. 6, 1019–1040. MR 2354716 (2008h:05025). Zbl 1125.05048.
      Antivoltages are gains that totally defy Kirchhoff's voltage law. They are related to the linear representation theory of bicircular (and bicircular lift) matroids, which are the frame (and lift) matroids of contrabalanced biased graphs; they correspond to the forest (and spanning forest) lattices (cf. [14 BGLF]). Main results: Bounds on the size of a cyclic group within which antivoltages do not exist, and a theory about the number of integral antivoltages.
      (Download prepublication version in PostScript: 500 kB; PDF: 270 kB.)
  73. [TFS] "Totally frustrated states in the chromatic theory of gain graphs". European J. Combinatorics, 30 (2009), 133–156. MR 2460223 (2009k:05100). Zbl 1125.05048.
      A totally frustrated state is a generalization of a proper coloring, where the color set can be any set permuted by the gain group. The properties of the number of totally frustrated states are partly analogous to those of the chromatic polynomial. These properties generalize to an abstract partition function that lives in the edge ring.
      (Download prepublication version from arXiv:math/0609048 or from here in PostScript: 500 kB; PDF: 300 kB.)
  74. [ECR] (with Pascal Berthomé, Raul Cordovil, David Forge, and Véronique Ventos) "An elementary chromatic reduction for gain graphs and special hyperplane arrangements". Electronic J. Combinatorics, 16 (1) (2009), Article R121, 31 pp. (electronic). MR 2546324 (2010k:05253). Zbl 1188.05076.
      Deletion-contraction applied to identity-gain edges allows computation of the zero-free chromatic polynomial and modular and integral chromatic functions of the Shi and Linial gain graphs, based upon the Catalan gain graph and intermediate graphs. This gives characteristic and lattice-point-counting polynomials for the Catalan, Shi, and Linial hyperplane arrangements.
      (Download prepublication version from arXiv:1001.4216 or from here in PostScript: 500 kB; PDF: 300 kB.)
  75. [DTH] (with David Forge) "On the division of space by topological hyperplanes". Combinatorial Geometries and Applications: Oriented Matroids and Matroids (Marseille-Luminy, 2005). European J. Combinatorics, 30 (2009), no. 8, 1835–1845. MR 2552666 (2011a:52043). Zbl 1179.52030.
      A topological hyperplane (or topoplane) is a wiggly hyperplane in Rn. In an arrangement, the intersections with each topoplane H of the other topoplanes must be (relative) topoplanes. However, two intersecting topoplanes need not cross. Well known example: The arrangement of affine topoplanes derived from a projective pseudohyperplane arrangement representing an oriented matroid. How different is this example from a general topoplane arrangement? Some answers are given.
      (Download prepublication version from arXiv:math/0609047 or from here in PostScript: 350 kB; PDF: 200 kB.)
      (Download slides of a talk at the Fields Institute, 19 August 2008, in PostScript: 200 kB; PDF: 120 kB.)
  76. [PAR] (with B.D. Acharya, Germina K.A., Kumar Abhishek, and S.B. Rao) "Point- and arc-reaching sets of vertices in a digraph". Indian J. Math., 51 (2009), no. 3, 597–609. MR 2573808 (2011b:05082). Zbl 1194.05053.
      Vertex sets from which every vertex, or every tail vertex of an arc, is reachable by a directed walk. Emphasis on minimal such sets in infinite digraphs.
      (Download prepublication version from arXiv:1001.4213 or from here in PDF: 150 kB.)
  77. [SLS] (with Matthias Beck) "Six little squares and how their numbers grow". J. Integer Sequences, 13 (2010), Article 10.6.2, 45 pp. MR 2659218 (2011j:05052). Zbl 1230.05062.
      Exact formulas for the numbers of 3×3 magic, semimagic, and magilatin squares, counted either by magic sum or by maximum allowed entry value. Exemplifies the theory of [70 MML].
      (Download prepublication version from arXiv:1004.0282 or from here in PostScript: 650 kB; PDF: 325 kB.)
      Here is a link to the SLS Web page, with access to the Maple and LattE files of computations and a supplementary write-up.
  78. *[MTS] "Matrices in the theory of signed simple graphs". In: B.D. Acharya, G.O.H. Katona, and J. Nesetril, eds., Advances in Discrete Mathematics and Applications: Mysore, 2008 (Proc. Int. Conf. Discrete Math., ICDM-2008, Mysore, India, 2008), pp. 207–229. Ramanujan Math. Soc. Lect. Notes Ser., No. 13. Ramanujan Math. Soc., Mysore, India, 2010. MR 2766941 (2012d:05017). Zbl 1231.05120.
      Matrices include the adjacency matrix, incidence matrix, Kirchhoff matrix, and line-graph adjacency matrix.
      See [MTSO] for the lecture notes and slides.
      (Download prepublication version from arXiv:1303.3083 or from here in PostScript: 500 kB; PDF: 260 kB.)
  79. [QRS] (with Seth Chaiken and Christopher R.H. Hanusa) "Nonattacking queens in a rectangular strip". Ann. Combinatorics, 14 (2010), no. 4, 419–441. MR 2776757 (2012d:05034). Zbl 1233.05022.
      Place m identical chess pieces in a rectangular strip of fixed height m and variable width n, one per row, nonattacking. The number of ways to do so is a polynomial if n is large. Application of [71 SOA], also going into more detail on computational methods.
      Examples: Formulas for small numbers of queens, bishops, knights, and nightriders with one in each row of the rectangle.
      The polynomials, though (possibly) not the complete formulas, for queens have been known since 1874 (3 rows, Pauls), 1890 (4 rows, Tarry), and 1992 (5-7 rows, Kotesovec). See Kotesovec's Web page http://web.telecom.cz/vaclav.kotesovec/math.htm#kap12. This page also has polynomials for other chess pieces subject to a different rule than ours, namely, purely non-attacking placements with any number of pieces per row.
      (Download prepublication version from arXiv:1105.5087 or from here in PostScript: 500 kB; PDF: 225 kB. Paper reprints available.)
  80. [DKP] (with Christopher R.H. Hanusa) "Determinants in the Kronecker product of matrices: The incidence matrix of a complete graph". Linear and Multilinear Algebra, 59 (2011), no. 4, 399–411. MR 2802522 (2012f:15007). Zbl 1218.15003.
      A formula for the least common multiple of all subdeterminants (the lcmd) in an integral matrix that is the Kronecker product of a complete-graph incidence matrix and a matrix A with two columns, in terms of lcmd(A) and products of 2 × 2 determinants derived from A.
      (Download prepublication version from arXiv:0811.1930 or from here in PDF: 200 kB; PostScript: 400 kB.)
  81. [CPL] (with K.A. Germina and Shahul Hameed K) "On products and line graphs of signed graphs, their eigenvalues and energy". Linear Algebra Appl., 435 (2011), 2432–2450. MR 2811128 (2012j:05254). Zbl 1222.05223.
      The eigenvalues and energy, and the Laplacian (or Kirchhoff) eigenvalues and energy, of signed graphs that are products, especially Cartesian products, or line graphs of other signed graphs. Examples include both the ordinary Laplacian and "signless Laplacian" eigenvalues and energy of an unsigned graph. Particular examples: planar, cylindrical, and toroidal grids with product signatures, their line graphs, and the line graphs of Kn, +Kn, and −Kn.
      (Download prepublication version from arXiv:1010.3884 or from here in PDF: 250 kB.)
  82. [AMQ] "Associativity in multiary quasigroups: The way of biased expansions". Aequationes Math., 83 (2012), no. 1, 1–66. MR 2885498. Zbl 1235.05059.
      Theorems: An n-ary quasigroup (n ≥ 3) whose factorization graph is 3-connected is isotopic to an iterated group. An n-ary quasigroup (n ≥ 3) whose residual ternary quasigroups all are iterated group isotopes is itself an iterated group isotope. Proofs via the generalization to biased expansion graphs (cf. [BG5]). E.g., a biased expansion of a 3-connected graph other than a triangle is a group expansion; a 2-connected biased expansion such that every 4-node minor is a group expansion is itself a group expansion; a biased expansion of multiplicity at most 3 is a group expansion.
      (35 years from problem formulation to publication!)
      Summarized in [65 QAX]. A brief summary is in the slides [Maas12].
      (Download prepublication version from arXiv:math/0411268, or from here in PostScript: 1100 kB; PDF: 600 kB. Paper reprints available.)
  83. [6SP] "Six signed Petersen graphs, and their automorphisms". Recent Trends in Graph Theory and Combinatorics (Cochin, 2010), Discrete Math., 312 (2012), no. 9, 1558–1583. MR 2899889. Zbl 1239.05086.
      Signed Petersen graphs. Mostly about switching isomorphism classes, of which there are six. Frustration index, automorphism and (in great detail) switching automorphism groups, chromatic numbers, coloration counts, clusterability.
      Final version of [6SP-s].
      (arXiv:1303.3347. Or, from here in PDF: 450 kB.)
  84. [SGGM] "Signed graphs and geometry". Set Valuations, Signed Graphs and Geometry (IWSSG-2011, Int. Workshop, Mananthavady, Kerala, 2011). J. Combin. Inform. System Sci., 37 (2012), no. 2-4, 95–143. Zbl 1301.05162.
      Definitions, theorems, and examples about the fundamentals of signed graphs and their geometrical properties: closure and rank, vectors and incidence matrix, hyperplane arrangement and coloring, and line graphs and angle representations. Largely but not entirely expository. Illustrated!
      Revised and enlarged from lecture notes of the International Workshop on Set-Valuations, Signed Graphs, Geometry and Their Applications (IWSSG-2011), Mary Matha Arts and Sciences College, Mananthavady, Kerala, India, 2-6 September 2011.
      (Download the slides from the lectures in PDF: 385 kB).
      (Download prepublication version from arXiv:1303.2770. Or, from here in PDF: 475 kB.)
  85. [D2S] (with E. Sampathkumar and M.A. Sriraj) "Directionally 2-signed graphs and bidirected graphs". Set Valuations, Signed Graphs and Geometry (IWSSG-2011, Int. Workshop, Mananthavady, Kerala, 2011). J. Combin. Inform. System Sci., 37 (2012), no. 2-4, 373–377. Zbl 1301.05161.
      The directionally 2-signed graphs introduced by Sampathkumar and Sriraj as a particular case of directionally n-signed graphs turn out to be equivalent to bidirected graphs. This leads to a cute new property of bidirected graphs.
      (arXiv:1303.3084. Or, from here in PDF: 225 kB.)
  86. [AMDC] (with A.M. Mathai) "On adjacency matrices and descriptors of signed cycle graphs". Set Valuations, Signed Graphs and Geometry (IWSSG-2011, Int. Workshop, Mananthavady, Kerala, 2011). J. Combin. Inform. System Sci., 37 (2012), no. 2-4, 359–372. Zbl 1301.05157.
      The eigenvalues and eigenvectors of A(Cn,σ). Two of the latter can distinguish all signatures of a circle, up to isomorphism.
      (arXiv:1303.3082. Or, from here in PDF: 250 kB.)
  87. [XBal] (with Devlin Mallory, Abigail Raz, and Christino Tamon) "Which exterior powers are balanced?". Electronic J. Combin., 20 (2013), no. 2, article P43, 14 pp. MR 3084585. Zbl 1266.05047.
      We define exterior powers of a signed graph and determine when such a power is balanced.
      (arXiv:1301.0973. Or, from here in PDF: 300 kB.)
  88. [IfG] (with B.D. Acharya, Germina K.A., Rency Kurian, and Viji Paul) "Interference in graphs". Int. Workshop on Set-Valuations, Signed Graphs, Geometry and Their Appl. (IWSSG-2011, Mananthavady, Kerala, 2011). J. Combin. Inform. System Sci., 38 (2013), 1–18. Zbl 1306.05209.
      An interference on a graph I is an injection f: V(I) → P(X) with the property that f(u) and f(v) are not disjoint, if uv is in E(I). A main problem is min |X|, which for I = Kn or Kr,s [or any complete multipartite graph] connects to problems of extremal set theory.
      We especially study the graphs G for which the neighborhood function N is an interference, that is, where I = Kn with f(u) = NG(u) for G an arbitrary graph on the same vertex set, and complemented neighborhood interference. We also study the graphs G for which the line graph neighborhood function NL, or its complement, is an interference.
      (arXiv:1404.1992. Download prepublication version in PDF: 320 kB.)
  89. [QQs1] (with Seth Chaiken and Christopher R.H. Hanusa) "A q-queens problem. I. General theory". Electronic J. Combin., 21 (2014), no. 3, Paper P3.33, 28 pp. MR 3262270. Zbl 1298.05021.
      Given q identical chess pieces to place in an n × n square, or kn × ln rectangle, or an n-fold inflated polygon, how many nonattacking placements are there, as a function of n? The function is a quasipolynomial of degree 2q. The coefficient of a power of n is a polynomial function of q.
      For detailed analyses of special pieces, see Part V.
      Exact formulas for few bishops, queens, and nightriders, inferred from extensive data, are online at Vaclav Kotesovec's Web page http://web.telecom.cz/vaclav.kotesovec/math.htm#kap12. Our series establishes the validity of some of those formulas and finds some new formulas.
      (arXiv:1303.1879. Or, from here in PDF: 500 kB.)
  90. [QQs2] (with Seth Chaiken and Christopher R.H. Hanusa) "A q-queens problem. II. The square board". J. Algebraic Combinatorics, 41 (2015), no. 3, 619–642. MR 3328174. Zbl 1314.05008.
      Applying Part I to the square board we can provide some detailed information about the counting function that was impossible for arbitrary boards. Letting q = n we have a (very difficult) formula for the n-Queens Problem.
      (arXiv:1402.4880. Or, from here in PDF: 500 kB.)
  91. [CLC] (with Daniel C. Slilaty) "Characterization of line-consistent signed graphs". Discussiones Mathematicae Graph Theory, 35 (2015), no. 3, 589–594. doi:10.7151/dmgt.1825. MR 3368992. Zbl 1317.05081.
      A signed graph implies a vertex signing of its line graph. A simpler proof of Acharya, Acharya, and Sinha's criterion for when the line graph is consistently signed. Also, observations about the structure of those signed graphs.
      (arXiv:1404.1651. Download prepublication version in PDF: 200 kB.)
  92. [HPT] (with David Forge) "Lattice points in orthotopes and a huge polynomial Tutte invariant of weighted gain graphs". J. Combinatorial Theory Ser. B, 118 (2016), 186–227. MR 3471850. Zbl 1332.05065.
      The chromatic functions of [71 SOA] are evaluations of special cases of extremely general Tutte invariants, of weighted gain graphs, that are polynomials in (potentially) hugely infinite numbers of variables. The weighted gain graphs have lattice-ordered gain groups and vertex weights from an abelian semigroup upon which the gain group acts. This allows for general notions of list colorations and their counting functions. With gains and weights in Zd we count lattice points in an orthotope of n × d matrices but not in certain subspaces; taking d = 1, we count lattice points in an arbitrary integral orthotope in Zn that are not in any specified affinographic hyperplanes, thus generalizing the work of [71 SOA] on hypercubes.
      (arXiv:1306.6132. Download submitted version in PostScript: 600 kB; PDF: 350 kB.)
  93. [CNV] "Consistency in the naturally vertex-signed line graph of a signed graph". Bull. Malaysian Mathematical Sciences Soc., 39 (2016), suppl. 1, 307–314. MR 3509082. Zbl 1339.05174.
      A constructive characterization of the signed graphs whose vertex-signed line graph is consistent, based on Acharya, Acharya, and Sinha's descriptive criterion.
      (arXiv:1404.1652. Download prepublication version in PDF: 230 kB.)
  94. [MFGO] (with Suresh Dara, S.M. Hegde, Venkateshwarlu Deva, and S.B. Rao) "The dynamics of the forest graph operator". Discussiones Mathematicae Graph Theory, 36 (2016), no. 4, 899–913. MR 3557209. Zbl 1350.05144.
      The operator transforms a graph to its adjacency graph of maximal forests. For infinite graphs, what are fixed points or cycles of the operator? What are the characteristics of the graph of maximal forests?
      (Download prepublication version from arXiv:1602.06622, or from here in PDF: 230 kB.)
  95. [IIF] (with Beifang Chen and Jue Wang) "Resolution of irreducible integral flows on a signed graph". Discrete Math., 340 (2017), no. 6, 1271–1286. MR 3624612. Zbl 1369.05098.
      Irreducible flows on a signed graph are much more interesting than those on an ordinary graph. They may have many self-intersections, which are resolved by lifting to the double covering of the signed graph.
      (arXiv:1701.04494. Download in PostScript: 300 kB; PDF: 130 kB.)
  96. *[FIS] "Forbidden induced subgraphs". Proc. Int. Conf. Current Trends in Graph Theory and Computation (CTGTC-2016, New Delhi). Electronic Notes in Discrete Math., 63 (2017), 3–10. MR 3754785. Zbl 1441.05162.
      A light survey of a variety of partial orderings of graphs, with a selection of graph classes that are well suited to the induced subgraph ordering and their characterizations by forbidden induced subgraphs and by vertex orderings.
      (Download prepublication version from arXiv:1610.04690, or from here in PDF: 225 kB.)
  97. *[NC] "Negative circles in signed graphs: A problem collection". Proc. Int. Conf. Current Trends in Graph Theory and Computation (CTGTC-2016, New Delhi). Electronic Notes in Discrete Math., 63 (2017), 41–47. MR 3754789. Zbl 1383.05152.
      A list of problems regarding negative, or positive, circles in a signed graph. Expanded in [98 NPC].
      (Download prepublication version from arXiv:1610.04691, or from here in PDF: 210 kB.)
  98. [NPC] "Negative (and positive) circles in signed graphs: A problem collection". Proc. Int. Conf. Current Trends in Graph Theory and Computation (CTGTC-2016, New Delhi). AKCE Int. J. Graphs Combinatorics, 15 (2018), no. 1, 31–48. MR 3803228. Zbl 1390.05085.
      A collection of problems and some propositions about negative and positive circles in a signed graph, touching upon frustration, structure, existence, packing and covering, counting, and their effect on eigenvalues. And a few problems about cycles in a signed digraph. Greatly expanded from [97 NC].
      (Download prepublication version from arXiv:1701.07963, or from here in PDF: 330 kB.)
  99. [MTG] (with Richard Behr and Vaidy Sivaraman) "Mock threshold graphs". Discrete Math., 341 (2018), no. 8, 2159–2178. MR 3810267. Zbl 1388.05073.
      A mock threshold graph is like a threshold graph, but not quite. It is constructed from the null graph by adding vertices, one at a time, that are adjacent, or non-adjacent, to 0 or 1 existing vertices. We characterize mock threshold graphs by forbidden induced subgraphs (there are 318 + 2·∞ of them). We also characterize the mock threshold graphs that are claw-free, line graphs, chordal, etc.
    100.   (Download prepublication version from arXiv:1602.06622, or from here in PDF: 850 kB.)
  100. [QQs6] (with Seth Chaiken and Christopher R.H. Hanusa) "A q-queens problem. VI. The bishops' period". Ars Math. Contemporanea, 16 (2019), no. 2, 549–561. MR 3963222. Zbl 1416.05131.
      The counting quasipolynomial for any number of bishops (greater than 2) has period 2. This proof uses convex polytopes, hyperplane arrangements, and signed graphs.
      (arXiv:1405.3001. Download prepublication version in PDF: 350 kB.)
  101. [QQs3] (with Seth Chaiken and Christopher R.H. Hanusa) "A q-queens problem. III. Nonattacking partial queens". Australasian J. Combinatorics, 74 (2019), no. 2, 305–331. MR 3949476. Zbl 1419.05015.
      A partial queen has move directions that are a subset of those of the queen. We determine high-order coefficients of the counting quasipolynomial and exact formulas for up to three identical partial queens (and that is not trivial). A striking fact is that for up to three partial queens, the number of combinatorially distinct types of configuration appears to depend only on the number of moves, not the actual directions. (Proved in [QQs7].)
      (Download prepublication version from arXiv:1402.4886, or from here in PDF: 500 kB.)
  102. [BG6] (with Rigoberto Flórez) "Biased graphs. VI. Synthetic geometry". European J. Combinatorics, 81 (2019), 119–141. MR 3953388. Zbl 1420.05030.
      The synthetic projective geometry of embedding a biased-graphic frame or lift matroid. Successor to the analytic treatment in [60 BG4].
      (Download prepublication version from arXiv:1608.06021, or from here in PDF: 600 kB.)
  103. [TCTR] (with Ouahiba Bessouf and Abdelkader Khelladi) "Transitive closure and transitive reduction in bidirected graphs". Czechoslovak Math. J., 69(2) (2019), 295–315. MR 3959945.
      Generalizes transitive closure from digraphs (oriented graphs) to bidirected graphs (oriented signed graphs). Transitive reduction means finding a minimal subgraph whose transitive closure includes the original graph.
      (Download prepublication version from arXiv:1610.00179, or from here in PDF: 450 kB)
  104. [DNCV] (with Alex Schaefer) "The dimension of the negative cycle vectors of signed graphs". Ars Math. Contemporanea, 16(2) (2019), 625–639. MR 3963226. Zbl 1416.05133.
      The vector has the number of negative circles of each length in a signed simple graph. The vectors of all signatures on a fixed graph have a dimension. What is it?
      (Download prepublication version from arXiv:1706.09041, or from here in PDF: 300 kB.)
  105. [QQs4] (with Seth Chaiken and Christopher R.H. Hanusa) "A q-queens problem. IV. Attacking configurations and their denominators". Discrete Math., 343(2) (2020), article 111649, 16 pp. MR 4040032. Zbl 1429.05010.
      We investigate riders (chess and fairy chess pieces whose moves have unlimited length) with 2, 3, and 4 or more move directions, finding upper (2 moves) and lower (3 or more moves) bounds on periods.
      (Download prepublication version from arXiv:1807.04741.)
  106. [BGPP] (with Rigoberto Flórez) "Projective planarity of matroids of 3-nets and biased graphs". Australasian J. Combinatorics, 76(2) (2020), 299–338. MR 4055697. Zbl 1439.05046.
      When can an abstract 3-net, or equivalently a biased expansion of K3, be embedded affinely or triangularly in a specific projective plane? Solved in terms of the associated quasigroup and a ternary coordinate ring for the plane.
      (Download prepublication version from arXiv:1708.00095, or from here in PDF: 600 kB.)
  107. [SCD] (with Simon Joyce, Alex Schaefer, and Douglas B. West) "Strongly connectable digraphs and non-transitive dice". AKCE Int. J. Graphs Combinatorics, 17(1) (2020), 480–485. MR 4145439.
      A digraph without opposed edges extends to a strongly connected digraph on the same vertices if and only if it has no complete directed cut.
      (Download preliminary version from arXiv:1508.00313, or from here in PDF: 200 kB.)
  108. [QQs7] (with Christopher R.H. Hanusa) "A q-queens problem. VII. Combinatorial types of nonattacking chess riders". Australasian J. Combinatorics, 77(3) (2020), 326–335. MR 4224499. Zbl 1444.05010.
      The number of combinatorially different types of nonattacking configuration of 3 identical riders having r moves is given by a formula in terms of r, regardless of the actual moves. The number for q identical riders with 3 moves is also independent of the moves, although we do not have a formula.
      (Download prepublication version from arXiv:1906.08981.)
  109. [QQs5] (with Seth Chaiken and Christopher R.H. Hanusa) "A q-queens problem. V. Some of our favorite pieces: Queens, bishops, rooks, and nightriders". J. Korean Math. Soc., 57(6) (2020), 1407–1433. MR 4169349. Zbl 1456.05005.
      We determine the counting quasipolynomial and its period for very few partial queens and partial nightriders.
      Exact formulas for few bishops, queens, and nightriders, inferred from extensive data, are online at Vaclav Kotesovec's Web page http://web.telecom.cz/vaclav.kotesovec/math.htm#kap12. Our papers prove the validity of several of his formulas and some new ones.
      (Download prepublication version from arXiv:1609.00853.)
  110. [SDist] (with Shahul Hameed K, Shijin T V, Soorya P, and Germina K A) "Signed distance in signed graphs". Linear Algebra Appl., 608 (2021), 236–247 [2020]. MR 4143538. Zbl 1458.05054.
      In a signed graph shortest paths may be positive, negative, or both. This leads to two matrices. A structural question: when do both signed distances agree? Characterized for bipartite graphs.
      (Download from arXiv:2005.06202.)
  111. [NSS] (with Reza Naserasr and Éric Sopena) "Homomorphisms of signed graphs: An update". European J. Combinatorics, 91 (2021), article 103222, 20 pp. [2020]. MR 4161815. Zbl 1458.05098.
      The purpose is to clarify and uniformize concepts, terminology, and notation with rigorous definitions, results, proofs, and research problems.
      (Download prepublication version from arXiv:1909.05982.)
  112. [CPGL] (with Deepa Sinha and Bableen Kaur) "The characteristic polynomial of a graph containing loops". Discrete Appl. Math., 300 (2021), 97–106. MR 4264159.
      If G is a simple graph with loops and G' is the graph without loops, there are formulas involving induced subgraphs relating their characteristic polynomials. The paper also discusses additive unitary Cayley graphs and signed additive unitary Cayley graphs.
      (Download prepublication version from arXiv:2005.06903.)
  113. [PSG2] (with Mukti Acharya and Joseph Varghese Kureethara) "Characterizations of some parity signed graphs". Australasian J. Combinatorics, 81(1) (2021), 89–100. MR 4312564.
      Parity signature means a cut with nearly equally many vertices on each side. All such are characterized for paths, circles, and some other graphs. The smallest such cut is studied.
      (Download prepublication version from arXiv:2006.03584.)
  114. [2HC] (with Vaidy Sivaraman) "Two Hamiltonian cycles". Discrete Math., 345 (2022), article 112797, 3 pp. MR 4366290. Zbl 1484.05118.
      A line graph walks into a bar and decomposes into Hamilton cycles. What is the root graph? Solved for 2 cycles.
      (Download from arXiv:2106.10368.)
  115. [TGS] (with Francesco Belardo and Zoran Stanić) "Total graph of a signed graph". Ars Mathematica Contemporanea, 3 (2023) [2022], #P1.02, 17 pp. MR 4518838. Zbl 1504.05119.
      The total graph extends the line graph in combinatorial and spectral variants to a signing of the total graph so as to have interesting spectral properties. Balance and frustration of line and total graphs. Spectra of iterated and product total graphs.
      (Download from arXiv:1908.02001.)
  116. [WPD] "Whitney numbers of partial Dowling lattices". Trans. Combinatorics, 13 (2024), no. 2, 169–178. MR 4683434. Zbl .
      The Whitney numbers of the first kind of a group (or biased) expansion of a graph are polynomial functions of the order of the group.
      (Download from arXiv:2209.01775.)

Papers Submitted

  1. [SDL] (with Roshni T Roy, Germina K A, and Shahul Hameed K) "Signed distance Laplacian matrices for signed graphs". Linear Multilinear Algebra, 72(2024), no.1, 106–117.
      Extension of [110 SDist]. Proofs via generalization to weighted signed graphs. Characterizes singularity and rank in terms of balance. Finds some spectra.
      (Download prepublication version from arXiv:2010.04204.)
  2. [MGS] (with Laura Anderson and Ting Su) "Matroids of gain signed graphs". Discrete & Computational Geom., to appear.
      Combining signs with gains is necessary to give a graphic interpretation of many interesting affine hyperplane arrangements. We do this for gains in the additive group of a field or any abelian group. Elementary graphical properties and the main cryptomorphisms of the matroid.
      (Download prepublication version from arXiv:2206.00237.)
  3. [VVS] (with Shahul Hameed K, Albin Mathew, and Germina K A) "Vector valued switching in signed graphs". Commun. Combinatorics Optimization, in press.
      Switching a signed graph over {−1, 0, 1}k. Questions: min k to achieve balance, etc. Examples and open questions.
      (Download prepublication version from arXiv:2208.00149.)
  4. [PR1] (with Rigoberto Flórez) "Projective rectangles". Submitted.
      A projective rectangle is a projective plane on a diet. Basic properties, projective subplanes, Desarguesian properties, orthogonal array version. Cf. [PR].
      (arXiv:2307.04079.)
  5. [RSB] (with Michael J. Gottstein) "The Rhodes semilattice of a biased graph". Aequationes Mathematicae, to appear.
      Rhodes introduced a semilattice associated with a group, for the study of semigroups. We show that it is essentially gain-graphic and generalize it to all gain graphs (in two ways) and biased graphs. We propose several ways to complete the semilattice to a lattice.
      (arXiv:2309.02700. Download in PDF: 500 kB.)
  6. [ACO] (with Jagdeep Singh and Vaidy Sivaraman) "Apex graphs and cographs". Submitted.
      For a graph type T, G is an apex-T-graph if some G−v is T. (1) Finitely many forbidden induced subgraphs for T imply the same for apex-T. (2) We find them all for T = cographs.
      (arXiv:2310.02551.)
  7. [Cob] (with Daniel Slilaty) "Cobiased graphs: Single-element extensions and elementary quotients of graphic matroids". Electronic J. Combinatorics, to appear.
      Cobias is dual (in the graphic matroid) to bias: it means selecting bonds, called cobalanced bonds, so no tribond contains exactly two cobalanced bonds. It is an effective way to represent extension and quotient matroids.
  8. [WNeg] (with Michael J. Gottstein) "Weakly negative circles versus best clustering in signed graphs". In preparation.
      A circle is weakly negative if it has exactly one negative edge. If no two weakly negative circles have a common edge, there is a nice structure.

Papers in Some State of Preparation

  1. [GLSP1] "Geometric lattices of structured partitions: I. Gain-graphic matroids and group-valued partitions". Manuscript, 1985 et seq., to be expanded.
      A structured partition is a set partition whose blocks have structure.
      (Download nearly complete preliminary draft in PostScript: 475 kB.)
  2. [GLSP2] "Geometric lattices of structured partitions: II. Lattices of group-valued partitions based on graphs and sets". Manuscript, 1985 et seq., to be expanded.
      Examples that generalize Dowling lattices.
      (Download preliminary draft in PostScript: 375 kB.)
  3. [GLSP3] "Geometric lattices of structured partitions: III. Composed and sequenced partitions". In preparation.
      A composed or sequenced partition has a weak composition of the elements of each block. Portions have appeared in [56 PDS].
  4. [UTG] "Universal gains for biased graphs". In preparation.
      Gains from topology. Universal gains for a biased graph.
      (Download preliminary draft in dvi: 30 kB; PostScript: 238 kB.)
  5. [BG5] "Biased graphs. V. Group and biased expansions". In preparation.
      Fundamentals of expansions [not related to expander graphs]. Matroid theory, generalizing the theory of Dowling geometries.
      (Download incomplete working draft in PostScript: 500 kB.)
  6. [BG8] "Biased graphs. VIII. A cornucopia of examples". In preparation.
      Sign bias, Hamiltonian bias, etc.
      (Download incomplete working version in PostScript: 310 kB.)
  7. [WTF] (with Joanna Ellis-Monaghan) "Tutte functions of matroids". In preparation.
      The classifying modules and algebras for parametrized Tutte functions on arbitrary minor-closed classes of matroids, with or without various kinds of multiplicativity requirements.
  8. [Pet] "Petersen signed graphs". In preparation.
      Signed graphs based on the Petersen graph. (Within the limits of this paper, where graphs are simple, for most purposes there are exactly six.) Many aspects are treated. Expository in flavor but many results are new, especially those concerning properties of the Petersen signed graphs. (This article may appear in several parts, if and when. See [83 6SP] for automorphisms.)
      (Download current incomplete draft version in PDF: 500 kB.)
  9. [FVC] "Frustration vs. clusterability in two-mode signed networks (signed bipartite graphs)". Under revision. (15 pp.)
      Comparison of two ways to measure instability in a signed bipartite graph, the frustration index and the majority biclusterability indices. There are many open questions of some interest if uncertain significance.
      (Download submitted version in PDF: 200 kB.)
  10. [CVS] "The canonical vertex signature and the cosets of the complete binary cycle space". Under revision. (7 pp.)
      A combinatorial structural analysis of the class of T-joins within Kn, for any even vertex set T, that is, the class of simple graphs with given odd- and even-degree vertices; equivalently, the signed complete graphs with the same "canonical" vertex signature.
      (Download submitted version in PostScript: 250 kB; PDF: 150 kB.)
  11. [LPE] "The least possible eigenvalue of a super line multigraph". Under revision. (5 pp.)
      The multiplicity of the largest possible eigenvalue of the super line (multi)graph of a bidirected graph. As a special case, the multiplicity of the least possible eigenvalue of the super line multigraph of an ordinary graph is determined by the number of bipartite components.
  12. [Sm] (with R.B. Bapat, Richard Behr, and Vaidy Sivaraman) "Smock: Special mock threshold graphs". In preparation.
      Complete description of a restricted variant of mock threshold graphs [99 MTG].
  13. [SConn] (with Ouahiba Bessouf and Abdelkader Khelladi) "New concept of connection in signed graphs". Under revision.
      Sign connection means that any two vertices are connected by both a positive and a negative walk. Many properties. Examples: signed graphs with only negative circles; signed graphs with only negative edges, where sign connection becomes "parity connection": any two vertices are joined by both an odd walk and an even walk.
      (Download preliminary version from arXiv:1708.01689, or from here in PDF: 400 kB.)
  14. [PR2] (with Rigoberto Flórez) "Projective rectangles: Incidence graphs and higher structure". In preparation.
      A projective rectangle is a projective plane on a diet. Nontrivial projective rectangles contain hidden higher-dimensional structure. Based on [PR1].
  15. [PR3] (with Rigoberto Flórez) "Projective rectangles: Harmonic conjugation". In preparation.
      A projective rectangle is a projective plane on a diet. Construction by harmonic conjugation within a harmonic matroid. Based on [PR1].

Manuscripts; Informal Expository Papers

  1. [VGG] "Voltage-graphic geometry and the forest lattice". In: Report on the XVth Denison-OSU Math Conference (Granville, Ohio, 1980), pp. 85–89. Dept. of Math., Ohio State University, Columbus, Ohio, 1980.
      Summary of parts of [14 BGLF], [34 BG2], and [45 BG3].
      (Download in updated PostScript: 230 kB; updated PDF: 120 kB; PDF of original: 360 kB)
  2. [SGE(D)] "Is there a theory of signed graph embedding?" In: Report on the XVIth Denison-OSU Math conference (Granville, Ohio, 1981), pp. 79–82. Dept. of Math., Ohio State University, Columbus, Ohio, 1981.
      Summary of part of [47 SGE].
  3. [Circ] (with P. D. Seymour) "A circumambulation of spherical designs (A vector mean value theorem)". In: Report of the Special OSU-Denison Maths Conference held in honor of Professor Hans Zassenhaus (Columbus, Ohio, 1982), pp. 38–40. Dept. of Math., Ohio State University, Columbus, Ohio, 1982.
      Summary of [20 AvS].
  4. [LGSC] "Line graphs of switching classes". In: Report of the XVIIIth O.S.U. Denison Maths Conference (Granville, Ohio, 1984), pp. 2–4. Dept. of Math., Ohio State Univ., Columbus, Ohio, 1984.
    5.   (Download in PostScript: 125 kB; PDF: 70 kB.)
      (Modernized version in PostScript: 175 kB; PDF: 100 kB).
  5. [DSG] "The demigenus of a signed graph". In: Report on the XXth Ohio State-Denison Mathematics Conference (Granville, Ohio, 1988). Dept. of Math., Ohio State Univ., Columbus, Ohio, 1988.
      Summary of parts of [32 MEGS], [37 OESG], [39 PPSG], and [47 SGE].
  6. [PTI] "Parametrized Tutte invariants". Extended abstract for Cornell-MSI Workshop on Combinatorics and Discrete Geometry (July, 1991).
      Summary of [38 STF].
  7. [DGLC] "Dowling geometries are line closed". Unpublished note, 2001. (2 pp.)
    Duplicates published, more general work.
      (Download in PostScript: 160 kB.)
  8. [NDP] "A new distribution problem of balls into urns, Stanley's chromatic symmetric function, and gain graphs". Unpublished manuscript, 2007. (8 pp.)
    Obsolete: Already known and done better.
      (Download in PDF: 140 kB.)
  9. [WCZ] "What about the chromatic zeros of a signed graph?" Research problem, presented to the Workshop on Zeros of Graph Polynomials, Programme on Combinatorics and Statistical Mechanics, Isaac Newton Institute, Cambridge, Eng., January 21-25, 2008. (1 p.)
      Suggests extending known results about ordinary graphs to the two chromatic polynomials of a signed graph.
      (Download in PostScript: 150 kB; PDF: 50 kB.)
  10. [OMGO] "Other matroids of graphs (Outline)". Unpublished manuscript, 2008. (14 pp.)
      Outline of talk at AMS sectional meeting, Baton Rouge, La., special session on matroid theory, 29 March 2008.
      There are many ways to form a matroid on the edge set of a graph besides the usual polygon and bond matroids. I survey them, and outline in some depth the frame (bias) and lift matroids of signed, gain, and biased graphs.
      (Download in PostScript: 300 kB; PDF: 150 kB.)
  11. [LMQO] "Local multiary quasigroups and topological biased graphs". Extended abstract. In: Abstracts of International Conference "Geometry in Odessa – 2008" (Odessa, 2008), pp. 202–203.
      Talk for the conference Geometry in Odessa 2008.
      Can continuous and differentiable local multiary quasigroups be modelled effectively by topological and differentiable biased graphs so as to prove theorems?
      (Download in PostScript: 150 kB; PDF: 50 kB.)
      (Download slides of my talk, "The graph theory of local multiary quasigroups", in PDF: 130 kB; or PostScript: 200 kB.)
  12. [MTSO] "Matrices in the theory of signed simple graphs (Outline)". In: International Conference on Discrete Mathematics (ICDM 2008) and Graph Theory Day – IV (Proc. [Lecture Notes], Mysore, 2008), pp. 187–198. University of Mysore, Mysore, India, 2008.
      Short version of [78 MTS].
      (Download in PostScript: 300 kB; PDF: 150 kB.)
      (Download slides from the talk in PostScript: 260 kB; or PDF: 125 kB.)
  13. "Lattice points and kindly chess queens". Slides of a talk at CombinaTexas 10, Houston, 2009.
      (Download in PDF: 100 kB.)
  14. "Tutte functions of matroids". Slides of a talk at AMS sectional meeting, Univ. of Kentucky, 2010.
      See [STF].
      (Download in PDF: 100 kB.)
  15. "Balance and clustering in signed graphs". Slides from lectures at the C.R. Rao Advanced Institute of Mathematics, Statistics and Computer Science, Univ. of Hyderabad, India, 26 July 2010.
      (Download in PDF: 170 kB.)
  16. "Consistent vertex-signed graphs". Slides from a lecture at the C.R. Rao Advanced Institute of Mathematics, Statistics and Computer Science, Univ. of Hyderabad, India, 28 July 2010.
      (Download in PDF: 135 kB.)
  17. "Non-attacking chess pieces: The bishop". Slides from a lecture at the C.R. Rao Advanced Institute of Mathematics, Statistics and Computer Science, Univ. of Hyderabad, India, 29 July 2010.
      (Download in PDF: 170 kB.)
    "Non-attacking chess pieces: The dance of bishops". Improved slides.
      (Download in PDF: 160 kB; PS: 310 kB.)
  18. "Line graphs, eigenvalues, and root systems". Slides from a lecture at the C.R. Rao Advanced Institute of Mathematics, Statistics and Computer Science, Univ. of Hyderabad, India, 2 August 2010.
      (Download in PDF: 130 kB.)
  19. [6SP-s] "Six signed Petersen graphs". Summary. Talk at the International Conference on Recent Trends in Graph Theory and Combinatorics (ICRTGC-2010), Cochin, India, August 12-15, 2010. (4 pp.)
      There are six switching isomorphism classes of signed Petersen graphs; and properties of the graphs. (Data in tables is not totally correct.) Predecessor of [83 6SP].
      (Download in PDF: 150 kB.)
  20. [Pala] "Reference notes for lectures on signed graphs and geometry". Lectures at the Workshop on Signed Graphs, Set-Valuations and Geometry, CMS Pala Campus, Pala, Kerala, India, 16-18 August 2010. (16 pp.)
      Very concise notes on definitions, theorems, and examples about fundamentals, closure and rank, vectors and incidence matrix, hyperplane arrangement, coloring, and significant examples. Predecessor of [SGGM].
      (Download in PDF: 250 kB.)
    Expanded lecture notes, from Mary Matha College, Mananthavady, Kerala, India, 2-6 September 2011. (23 pp.)
      (Download in PDF: 375 kB. Slides (compressed from lecture notes) in PDF: 400 kB.)
  21. [Maas12] "Dowling Geometries of Multiary Quasigroups". Slides for lecture at the Workshop on Matroid Theory, Maastricht, 29 July-2 August 2012.
      Brief introduction to [82 AMQ].
      (Download in PDF: 100 kB.)
  22. [GGLN] "Lectures on Gain Graphs and Hyperplane Arrangements". Notes from a graduate course in 2019. Not yet entirely refined.
      Assumes elementary background on hyperplane arrangements, e.g., from R.P. Stanley, "Lectures on Hyperplane Arrangements" (Park City).
      (Download in PDF: 600 kB.)

Return to my home page.