Publications and So Forth

of Thomas Zaslavsky

Best Viewed With Any Browser

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

Arranged by topic (with links to the full bibliographic data on this page).

Index

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.
    1a.   Selections reprinted in J.P.S. Kung, ed., A Source Book in Matroid Theory, Birkhauser, Boston, 1986, pp. 309-331 with editorial commentary pp. 278-282. MR 88e:05028 (book). Zbl. 597.05019 (book).
  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].
      (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 [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], including what I now call "topological hyperplanes" [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] and [19].
  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 kilobytes. 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.
      (Paper reprints available.)
  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, 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].
      (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]. Many kinds of examples.
      (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". 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).
      Summary of parts of [11-14], [31], [34], [45], [60].
      (Download in PostScript: 250 kilobytes; PDF (no figures): 130 kilobytes.)
  16. [BGP] (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 Diny MR 90b:05114.
  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), 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 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), 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] and [17] 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.
      An error in Cor. 4.3 (leading to an error in [33]): 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.)
      (Paper reprints available.)
  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), 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 dvi: 108 kilobytes; compressed PS: 166 kilobytes. 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 [BG2], [BG3], [BG4], [BG7], and unpublished [BG5], [BG8].
      (Paper reprints available.)
  32. [MEGS] "Matroids determine the embeddability of graphs in surfaces". Proc. Amer. Math. Soc., 106 (1989), 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 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") G, lift L, and extended lift L0 matroids.
      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, 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).
      (Paper reprints available.)
  34. [BG2] "Biased graphs. II. The three matroids". J. Combinatorial Theory Ser. B, 51 (1991), 46-72. MR 91m:05056. Zbl. 763.05096.
      The bias (better name: "frame") matroid and the lift and complete lift matroids. Multiple definitions; basic properties; comparison of the frame and lift matroids and intermediate matroids; remarks on infinitary versions.
      (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), 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), 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), 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.
      (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 kilobytes; compressed PS: 180 kilobytes.)
      (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 kilobytes.)
      (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.
      (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.
    1998 July 21 (25 pp.). Edition 2: 1998 September 18 (41 pp.).
      (For the most recent update see the Home Page of Signed, Gain, and Biased Graphs.)
  54. [SSF] "Supersolvable frame-matroid and graphic-lift lattices". European J. Combinatorics, 22 (2001), 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 kilobytes; PostScript: 470 kilobytes; compressed PS: 130 kilobytes. Paper reprints available.)
  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 kilobytes; PostScript: 170 kilobytes. 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 kilobytes; PostScript: 850 kilobytes.)
      (Download prepublication version (45 pp., with 10 figures) in dvi: 200 kilobytes; PostScript: 850 kilobytes; compressed PS: 350 kilobytes. Paper reprints available.)
      (Download reference, accidentally omitted from published paper: PDF: 25 kilobytes; PostScript: 65 kilobytes.)
  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 [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". Geom. 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 kilobytes; compressed PS: 180 kilobytes. 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.
      (Download prepublication version (62 pp., with 7 figures) in PostScript: 1000 kilobytes; compressed PS: 450 kilobytes; PDF (no figures): 500 kilobytes.)
  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. 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. 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 [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 Society Mathematical Studies, 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 [NNZ], [MML], [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 [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 [SLS]). Generalized to linear forms. This is an application of the theory of [IOP].
      (arXiv math.CO/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 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.CO/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 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. [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.
      (arXiv math.CO/0609048. Download prepublication version 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).
      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 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.
      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.
      (arXiv math.CO/0609047. Download prepublication version 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.
      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 in PDF: 150 kB.)

Papers Submitted

  1. [AMQ] "Associativity in multiary quasigroups: The way of biased expansions". Submitted. (45 pp.)
      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 are all iterated group isotopes is itself an iterated group isotope. A multiary quasigroup of at most 3 elements is isotopic to an iterated group. Proofs via biased expansion graphs (cf. [BG5]).
      (arXiv math.GM/0411268. Or, download prepublication version in PostScript: 825 kB; PDF: 950 kB.)
  2. [QRS] (with Seth Chaiken and Christopher R.H. Hanusa) "Nonattacking queens in a rectangular strip". Ann. Combinatorics, accepted. (19 pp.)
      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 [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 in PostScript: 500 kB; PDF: 225 kB.)
  3. [HPT] (with David Forge) "Colorations, orthotopes, and a huge polynomial Tutte invariant of weighted gain graphs". Submitted. (30 pp.)
      The chromatic functions of [71] are evaluations of special cases of extremely general Tutte invariants, of weighted gain graphs, that are polynomials in 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 [SOA] on hypercubes.
      (Download prepublication version in PostScript: 600 kB; PDF: 350 kB.)
  4. *[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 (Proc. Int. Conf. Discrete Math., ICDM-2008, Mysore, India, 2008), to appear. (20 pp.)
      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 in PostScript: 500 kB; PDF: 260 kB.)
  5. [LPE] "The least possible eigenvalue of a super line multigraph". Submitted. (5 pp.)
      The multiplicity of the largest possible eigenvalue of the super line graph of a bidirected graph depends on the rank of the frame matroid. 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.
      (Download prepublication version in PostScript: 250 kB; PDF: 100 kB.)
  6. [DKP] (with Christopher R.H. Hanusa) "Determinants in the Kronecker product of matrices: The incidence matrix of a complete graph". Linear and Multilinear Algebra, accepted.
      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.
      (arXiv 0811.1930. Download prepublication version (15 pp.) in PDF: 200 kB;. PostScript: 400 kB.)
  7. [CLC] "Construction of line-consistent signed graphs". Submitted.
      A signed graph implies a vertex signing of its line graph. A new proof of Acharya, Acharya, and Sinha's criterion for when the line graph is consistently signed.
      Download prepublication version in PostScript: 250 kB; PDF: 150 kB.
  8. [FVC] "Frustration vs. clusterability in two-mode signed networks (signed bipartite graphs)". Submitted.
      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 in PDF: 200 kB.)

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 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.
  4. [UTG] "Universal and topological 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. Matroid theory, generalizing the theory of Dowling geometries.
      (Download incomplete working draft in PostScript: 500 kB.)
  6. [BG6] (with Rigoberto Flórez) "Biased graphs. VI. Synthetic geometry". In preparation.
      (1) The synthetic geometry of a biased graph. (2) When a given 3-net can be embedded in a given projective plane.
      (Download incomplete working version in PostScript: 320 kB.)
  7. [BG8] "Biased graphs. VIII. A cornucopia of examples". In preparation.
      Sign bias, Hamiltonian bias, etc.
      (Download incomplete working version in PostScript: 310 kB.)
  8. [QQ] (with Seth Chaiken and Christopher R.H. Hanusa) "A q-queens problem". In preparation.
      Given q identical chess pieces to place in an n × n square (or kn × ln rectangle, etc.), how many nonattacking placements are there, as a function of n?
  9. [WTF] (with Joanna Ellis-Monaghan) "Weak 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.
  10. [IIF] (with Beifang Chen and Jue Wang) "Resolution of irreducible integral flows on a signed graph". In preparation.
      Irreducible flows on a signed graph are much more interesting than those on an ordinary graph.
      (Download working version in PostScript: 300 kB; PDF: 130 kB.)
  11. [SLS] (with Matthias Beck) "Six little squares and how their numbers grow". Submitted.
      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].
      (Download 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.
  12. [LMQ] "The graph theory of local multiary quasigroups". In preparation.
      Can continuous and differentiable local multiary quasigroups be modelled effectively by topological and differentiable biased graphs so as to prove theorems?
      See [LMQO] for the abstract and slides.
  13. [GMG] (with Nathan Reff) "Graphic matrices over a group". In preparation.
      The matrix coefficients are in the group ring or group algebra of a group, especially the two-element group.
  14. [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.)
      (Download current incomplete draft version in PDF: 500 kB.)

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], [34], and [45].
      (Download in PostScript: 230 kilobytes; PDF (no figures): 120 kilobytes.)
  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].
  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].
  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 kilobytes; PDF: 70 kilobytes.)
      (Modernized version in PostScript: 175 kilobytes; PDF: 100 kilobytes.)
  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], [37], [39], and [47].
  6. [PTI] "Parametrized Tutte invariants". Extended abstract for Cornell-MSI Workshop on Combinatorics and Discrete Geometry (July, 1991).
      Summary of [38].
  7. [DGLC] "Dowling geometries are line closed". Unpublished note, 2001. (2 pp.)
      (Download in PostScript: 160 kilobytes.)
  8. [NDP] "A new distribution problem of balls into urns, Stanley's chromatic symmetric function, and gain graphs." Unpublished manuscript, 2007. (8 pp.)
      (Download in PostScript: 160 kilobytes.)
  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 kilobytes; PDF: 150 kilobytes.)
  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 kilobytes; PDF: 50 kilobytes.)
      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 [MTS].
      (Download in PostScript: 300 kilobytes; PDF: 150 kilobytes.)
      (Download slides from the talk in PostScript: 260 kB; or PDF: 125 kB.)
  13. "Lattice points and kindly chess queens". Talk at CombinaTexas 10, Houston, 2009.
      (Download slides from the talk in PDF: 100 kB.)

Return to my home page.