Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Cohomological aspects of hypergraphs

Authors: F. R. K. Chung and R. L. Graham
Journal: Trans. Amer. Math. Soc. 334 (1992), 365-388
MSC: Primary 05C65; Secondary 18G99, 55N99, 57Q99, 60C05
MathSciNet review: 1089416
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: By a $ k$-graph we will mean a collection of $ k$-element subsets of some fixed set $ V$. A $ k$-graph can be regarded as a $ (k - 1)$-chain on $ {2^V}$, the simplicial complex of all subsets of $ V$, over the coefficient group $ \mathbb{Z}/2$, the additive group of integers modulo $ 2$. The induced group structure on the $ (k - 1)$-chains leads to natural definitions of the coboundary $ \delta $ of a chain, the cochain complex of $ C = \{ {C^k},\delta \} $ and the usual cohomology groups $ {H^k}(C;\mathbb{Z}/2)$. In particular, it is possible to construct what could be called "higher-order" coboundary operators $ {\delta ^{(i)}}$, where $ {\delta ^{(i)}}$ increases dimension by $ i$ (rather than just $ 1$).

In this paper we will develop various properties of these $ {\delta ^{(i)}}$, and in particular, compute the corresponding cohomology groups for $ {2^V}$ over $ \mathbb{Z}/2$. It turns out that these groups depend in a rather subtle way on the arithmetic properties of $ i$.

References [Enhancements On Off] (What's this?)

  • [B89] C. Berge, Hypergraphs, North-Holland, Amsterdam, 1989. MR 1013569 (90h:05090)
  • [C77] P. J. Cameron, Cohomological aspects of two-graphs, Math. Z. 157 (1977), 101-119. MR 0505778 (58:21779)
  • [C78] -, Automorphisms and cohomology of switching classes, J. Combin. Theory Ser. (B) 22 (1977), 297-298. MR 0498227 (58:16382)
  • [CW86] Y. Cheng and A. L. Wells, Jr., Switching classes of directed graphs, J. Combin. Theory Ser. (B) 40 (1986), 169-186. MR 838217 (87g:05104)
  • [CG90] F. R. K. Chung and R. L. Graham, Quasi-random hypergraphs, Random Structures and Algorithms 1 (1990), 105-124. MR 1068494 (91h:05089)
  • [CG91] -, Quasi-random set systems, J. Amer. Math. Soc. 4 (1991), 151-196. MR 1077279 (91m:05138)
  • [CGW89] F. R. K. Chung, R. L. Graham and R. M. Wilson, Quasi-random graphs, Combinatorica 9 (1989), 345-362. MR 1054011 (91e:05074)
  • [F90] P. Frankl, Intersection theorems and $ \bmod \,p$ rank of inclusion matrices, J. Combin. Theory Ser. (A) 54 (1990), 85-94. MR 1051780 (91b:05006)
  • [GLL80] R. L. Graham, S. Y. R. Li and W. C. Li, On the structure of $ t$-designs, SIAM J. Algebraic and Discrete Method 1 (1980), 8-14. MR 563008 (83b:05042)
  • [GKP89] R. L. Graham, D. E. Knuth and O. Patasknik, Concrete mathematics, Addison-Wesley, Reading, Mass., 1989.
  • [GRS90] R. L. Graham, B. L. Rothschild and J. H. Spencer, Ramsey theory, (2nd ed.), Wiley, New York, 1990. MR 1044995 (90m:05003)
  • [GJ73] J. E. Grover and W. B. Jurkat, The module structure of integral designs, J. Combin. Theory Ser. (A) 15 (1973), 75-90. MR 0329930 (48:8270)
  • [H49] S. T. Hu, A cohomology theory with higher coboundary operators. I (Construction of the groups), Nederl. Akad. Wetensch. Proc. 52 (1949), 1144-1150. MR 0033524 (11:452a)
  • [H50] -, A cohomology theory with higher coboundary operators. II (Verification of the axioms of Eilenberg-Steenrod), Nederl. Akad. Wetensch. Proc. 53 (1950), 70-76. MR 0033525 (11:452b)
  • [H52] -, A cohomology theory with higher coboundary operators. III (The homotopy axiom and the groups for spheres), Nederl. Akad. Wetensch. Proc. 55 (1952), 123-129. MR 0047324 (13:860a)
  • [K72] W. M. Kantor, On incidence matrices of finite projective and affine spaces, Math. Z. 124 (1972), 315-318. MR 0377681 (51:13850)
  • [LR81] N. Linial and B. L. Rothschild, Incidence matrices of subsets -- a rank formula, SIAM J. Algebraic and Discrete Methods 2 (1981), 333-340. MR 627600 (82h:05011)
  • [MS75] C. L. Mallows and N. J. A. Sloane, Two-graphs, switching classes and Euler graphs are equal in number, SIAM J. Appl. Math. 28 (1975), 876-880. MR 0427128 (55:164)
  • [ML83] W. Mielants and H. Leemans, $ {\mathbb{Z}_2}$-cohomology of projective spaces of odd order, Combinatorics '81 (Rome, 1981), North-Holland Math. Stud., 78, North-Holland, Amsterdam, 1983, pp. 635-651. MR 695848 (84h:51030)
  • [M84] J. R. Munkres, Elements of algebraic topology, Benjamin/Cummings, Menlo Park, Calif., 1984. MR 755006 (85m:55001)
  • [S76] J. J. Seidel, A survey of two-graphs, Colloquio Internazionale sulle Teorie Combinatorie, vol. 1, Accademia Nazionale dei Lincei, Rome, 1976, pp. 481-511. MR 0550136 (58:27659)
  • [ST81] J. J. Seidel and D. E. Taylor, Two-graphs, a second survey, Algebraic Methods in Graph Theory (L. Lovász and V. T. Soś, eds.), North-Holland, Amsterdam, 1981. MR 642068 (83f:05070)
  • [We84] A. L. Wells, Jr., Even signings, signal switching classes and $ ( - 1,1)$-matrices, J. Combin. Theory Ser. (B) 36 (1984), 194-212. MR 746549 (85i:05206)
  • [Wi$ ^{{\ast}}$] R. M. Wilson, A diagonal form for the incidence matrices of $ t$-subsets vs. $ k$-subsets, European J. Combin. 11 (1990), 609-615. MR 1078717 (91i:05010)
  • [Z81] T. Zaslavsky, Characterization of signed graphs, J. Graph. Theory 5 (1981), 401-406. MR 635702 (83a:05122)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05C65, 18G99, 55N99, 57Q99, 60C05

Retrieve articles in all journals with MSC: 05C65, 18G99, 55N99, 57Q99, 60C05

Additional Information

Article copyright: © Copyright 1992 American Mathematical Society

American Mathematical Society