Publications and So Forth

of Thomas Zaslavsky

Best Viewed With Any Browser

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

Published Works

(* Abstracts, announcements, summaries, and essentially expository works.)
  1. "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 from [1] 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. "Counting the faces of cut-up spaces". Bull. Amer. Math. Soc., 81 (1975), 916-918. MR 53 #3901. Zbl. 317.05012.
    Summary of [4].
  3. "Maximal dissections of a simplex". J. Combinatorial Theory Ser. A, 20 (1976), 244-257. MR 53 #3891. Zbl. 334.05011.
  4. "A combinatorial analysis of topological dissections". Advances in Math., 25 (1977), 267-285. MR 56 #5310. Zbl. 406.05004.
    Topological generalization of [1]: dissecting topological spaces by subspaces, how many regions are there? The answers are complicated and not as general as the question.
  5. * "Arrangements of hyperplanes; matroids and graphs". 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. "The geometry of root systems and signed graphs". Amer. Math. Monthly, 88(Feb., 1981), no. 2, 88-105. MR 82g:05012. Zbl. 466.05058.
  7. "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.
  8. (with F. R. McMorris) "The number of cladistic characters". Math. Biosciences, 54 (1981), 3-10. MR 82j:92008. Zbl. 454.92003.
  9. "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.
  10. "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.
  11. "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].
  12. "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].
  13. "Chromatic invariants of signed graphs". Discrete Math., 42 (1982), 287-312. MR 84h:05050b. Zbl. 498.05030.
    Sequel to [12]. Many kinds of examples.
  14. "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.
  15. * "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. (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. "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. "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.
  19. (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.
  20. (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).
  21. "How colorful the signed graph?". Discrete Math., 52 (1984), 279-284. MR 86m:05045. Zbl. 554.05026.
  22. "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.
  23. "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.
  24. (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).
  25. "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.
  26. "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.)
  27. "Balanced decompositions of a signed graph". J. Combinatorial Theory Ser. B, 43 (1987), 1-13. MR 89c:05058. Zbl. 624.05056.
  28. * "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.
    29. Download in PDF: 3.8 megabytes.)
  29. "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.
  30. "Togs (generalizations of two-graphs)". 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.)
  31. "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], [45], 60, [72], and unpublished [BG5], [72], [BG8].
  32. "Matroids determine the embeddability of graphs in surfaces". Proc. Amer. Math. Soc., 106 (1989), 1131-1135. MR 90a:05075. Zbl. 674.05025.
  33. "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).
  34. "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.
  35. (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.
    Solution by K. Ford, ibid., 100 (Feb. 1993), no. 2, 191-194. Elementary and elegant.
  36. "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.
  37. "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.
  38. "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.
  39. "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.)
  40. (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.
  41. (with Patrick Solé) "Maximality of the cycle code of a graph". Discrete Math., 128 (1994), 401-405. MR 94m:05164. Zbl. 794.05114.
  42. "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".)
  43. (with Patrick Solé) "A coding approach to signed graphs". SIAM J. Discrete Math., 7 (1994), 544-553. MR 95k:94041. Zbl. 811.05034.
  44. "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.
  45. "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.
  46. "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) of the all-negative complete graph with loops.
  47. "Is there a matroid theory of signed graph embedding?" Ars Combinatoria, 45 (1997), 129-141. MR 97m:05084. Zbl. 933.05067.
  48. "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) of the all-negative complete graph without loops.
  49. 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.
  50. (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.)
  51. "Signed analogs of bipartite graphs". Discrete Math., 179 (1998), 205-216. MR 2000b:05067. Zbl. 890.05060.
    (Download prepublication version in PostScript: 245 kilobytes.)
  52. * "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. * "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. "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.)
  55. "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.)
  56. "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.)
    (Download reference, accidentally omitted from published paper: PDF: 25 kilobytes; PostScript: 65 kilobytes.)
  57. (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, general proof of a generalization of Sperner's theorem on antichains of sets.
    (arXiv math.CO/0112068.)
  58. (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] applied to the lattice of flats of a projective geometry.
    (arXiv math.CO/0112069.)
  59. "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.)
  60. "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. (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.
  62. "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 kilobytes; PDF: 160 kilobytes.)
  63. (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 reprint available.)
  64. (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 reprint available.)
  65. * "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 kilobytes; PDF: 150 kilobytes.)
  66. (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. (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 in PostScript: 200 kilobytes; PDF: 100 kilobytes. Paper reprint available.)
  68. (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], [70], [SLS].
    (arXiv math.CO/0309330. Or, download in PostScript: 650 kilobytes; PDF: 375 kB. Paper reprint available.)
  69. (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].
    (arXiv math.CO/0309331. Or, download in PostScript: 450 kilobytes; PDF: 250 kilobytes.)
  70. (with Matthias Beck) "An enumerative geometry for magic and magilatin labellings". Ann. Combin., 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 [68].
    (arXiv math.CO/0506315. Or, download in PostScript: 450 kilobytes; PDF: 250 kilobytes. Paper reprint available.)
  71. (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 in PostScript: 400 kilobytes; PDF: 235 kilobytes. Paper reprint available.)
  72. "Biased graphs. VII. Contrabalance and antivoltages". J. Combinatorial Theory Ser. B, 97 (2007), no. 6, 1019--1040. 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]). 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 kilobytes; PDF: 270 kilobytes.)

Papers Submitted

  1. (with David Forge) "On the division of space by topological hyperplanes". European J. Combinatorics, to appear. (12 pp.)
    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 in PostScript: 350 kilobytes; PDF: 200 kilobytes.)
  2. "Associativity in multary 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 multary 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 in PostScript: 825 kilobytes; PDF: 950 kilobytes.)
  3. "Totally frustrated states in the chromatic theory of gain graphs". European J. Combinatorics, to appear. (24 pp.)
    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 in PostScript: 500 kilobytes; PDF: 300 kilobytes.)
  4. (with Seth Chaiken and Christopher R.H. Hanusa) "Nonattacking queens in a rectangular strip". Submitted. (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 [71], also going into more detail on computational methods.
    (Download in PostScript: 500 kilobytes; PDF: 225 kilobytes.)
  5. (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 [71] on hypercubes.
    Download in PostScript: 600 kilobytes; PDF: 350 kilobytes.)
  6. (with Pascal Berthomé, Raul Cordovil, David Forge, and Véronique Ventos) "An elementary chromatic reduction for gain graphs and special hyperplane arrangements". Submitted. (24 pp.)
    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 kilobytes; PDF: 275 kilobytes.)
  7. "What about the chromatic zeros of a signed graph?" Submitted. (1 p.)
    Suggests extending known results about ordinary graphs to the two chromatic polynomials of a signed graph.
    (Download in PostScript: 150 kilobytes; PDF: 50 kilobytes.)

Papers in Some State of Preparation (partial list)

  1. "Geometric lattices of structured partitions: I. Gain-graphic matroids and group-valued partitions". Manuscript, 1985 et seq., to be expanded. (23 pp.)
    (Download in PostScript: 475 kilobytes.)
  2. "Geometric lattices of structured partitions: II. Lattices of group-valued partitions based on graphs and sets". Manuscript, 1985 et seq., to be expanded. (15 pp.)
    (Download in PostScript: 375 kilobytes.)
  3. "Geometric lattices of structured partitions: III. Composed and sequenced partitions". In preparation.
  4. "Universal and topological gains for biased graphs". In preparation. (10 pp.)
    (Download preliminary draft in dvi: 30 kilobytes; PostScript: 238 kilobytes.)
  5. "Biased graphs. V. Group and biased expansions". In preparation. (20 pp.)
    Fundamentals of expansions. Matroid theory, generalizing the theory of Dowling geometries.
    (Download incomplete working draft in PostScript: 500 kilobytes.)
  6. (with Rigoberto Flórez) "Biased graphs. VI. Synthetic geometry". In preparation. (10 pp.)
  7. "Biased graphs. VIII. A cornucopia of examples". In preparation. (10 pp.)
    Sign bias, Hamiltonian bias, etc.
    (Download incomplete working version in PostScript: 310 kilobytes.)
  8. (with Seth Chaiken and Christopher R.H. Hanusa) "A q-queens problem". In preparation. (6 pp.)
  9. (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. (with Beifang Chen and Jue Wang) "Resolution of irreducible integral flows on a signed graph". In preparation. (9 pp.)
    Irreducible flows on a signed graph are much more interesting than those on an ordinary graph.
    (Download working version in PostScript: 300 kilobytes; PDF: 130 kilobytes.)
  11. (with Matthias Beck) "Six little squares and how their numbers grow". In preparation. (36 pp.)
    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 kilobytes; PDF: 325 kilobytes.)
    Here is a link to the SLS Web page, with access to Maple and LattE files of computations and a supplementary write-up.

Manuscripts; Informal Expository Papers

  1. "Voltage-graphic geometry and the forest lattice". 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. "Is there a theory of signed graph embedding?" 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. (with P. D. Seymour) "A circumambulation of spherical designs (A vector mean value theorem)". 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. "Line graphs of switching classes". 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. "The demigenus of a signed graph". 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. "Parametrized Tutte invariants". Extended abstract for Cornell-MSI Workshop on Combinatorics and Discrete Geometry (July, 1991).
    Summary of [38].
  7. "Dowling geometries are line closed". Unpublished note, 2001. (2 pp.)
    (Download in PostScript: 160 kilobytes.)
  8. "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. "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.)
  10. "Local multary quasigroups and topological biased graphs". Extended abstract. (2 pp.)
    Talk for the conference Geometry in Odessa 2008.
    Can continuous and differentiable local multary quasigroups be modelled effectively by topological and differentiable biased graphs so as to prove theorems?
    Download in PostScript: 150 kilobytes; PDF: 50 kilobytes.)
  11. "Matrices in the theory of signed simple graphs (Outline)". Unpublished manuscript, 2008. (10 pp.)
    Outline of talk at ICDM-2008, Mysore, India, June 2008.
    Matrices include the adjacency matrix, incidence matrix, Kirchhoff matrix, and line-graph adjacency matrix.
    (Download in PostScript: 300 kilobytes; PDF: 150 kilobytes.)

Return to my home page.