Cohomological aspects of hypergraphs
HTML articles powered by AMS MathViewer
- by F. R. K. Chung and R. L. Graham
- Trans. Amer. Math. Soc. 334 (1992), 365-388
- DOI: https://doi.org/10.1090/S0002-9947-1992-1089416-0
- PDF | Request permission
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
- Claude Berge, Hypergraphs, North-Holland Mathematical Library, vol. 45, North-Holland Publishing Co., Amsterdam, 1989. Combinatorics of finite sets; Translated from the French. MR 1013569
- Peter J. Cameron, Cohomological aspects of two-graphs, Math. Z. 157 (1977), no.ย 2, 101โ119. MR 505778, DOI 10.1007/BF01215145
- Peter J. Cameron, Automorphisms and cohomology of switching classes, J. Combinatorial Theory Ser. B 22 (1977), no.ย 3, 297โ298. MR 498227, DOI 10.1016/0095-8956(77)90079-x
- Ying Cheng and Albert L. Wells Jr., Switching classes of directed graphs, J. Combin. Theory Ser. B 40 (1986), no.ย 2, 169โ186. MR 838217, DOI 10.1016/0095-8956(86)90075-4
- F. R. K. Chung and R. L. Graham, Quasi-random hypergraphs, Random Structures Algorithms 1 (1990), no.ย 1, 105โ124. MR 1068494, DOI 10.1002/rsa.3240010108
- F. R. K. Chung and R. L. Graham, Quasi-random set systems, J. Amer. Math. Soc. 4 (1991), no.ย 1, 151โ196. MR 1077279, DOI 10.1090/S0894-0347-1991-1077279-1
- F. R. K. Chung, R. L. Graham, and R. M. Wilson, Quasi-random graphs, Combinatorica 9 (1989), no.ย 4, 345โ362. MR 1054011, DOI 10.1007/BF02125347
- P. Frankl, Intersection theorems and mod $p$ rank of inclusion matrices, J. Combin. Theory Ser. A 54 (1990), no.ย 1, 85โ94. MR 1051780, DOI 10.1016/0097-3165(90)90007-J
- R. L. Graham, S.-Y. R. Li, and W. C. W. Li, On the structure of $t$-designs, SIAM J. Algebraic Discrete Methods 1 (1980), no.ย 1, 8โ14. MR 563008, DOI 10.1137/0601002 R. L. Graham, D. E. Knuth and O. Patasknik, Concrete mathematics, Addison-Wesley, Reading, Mass., 1989.
- Ronald L. Graham, Bruce L. Rothschild, and Joel H. Spencer, Ramsey theory, 2nd ed., Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1990. A Wiley-Interscience Publication. MR 1044995
- J. E. Graver and W. B. Jurkat, The module structure of integral designs, J. Combinatorial Theory Ser. A 15 (1973), 75โ90. MR 329930, DOI 10.1016/0097-3165(73)90037-x
- Sze-tsen Hu, A cohomology theory with higher coboundary operators. I. (Construction of the groups.), Nederl. Akad. Wetensch., Proc. 52 (1949), 1144โ1150 = Indagationes Math. 11, 418โ424 (1949). MR 33524
- Sze-tsen Hu, A cohomology theory with higher coboundary operators. II. Verification of the axioms of Eilenberg-Steenrod, Nederl. Akad. Wetensch., Proc. 53 (1950), 70โ76 = Indagationes Math. 12, 1โ7 (1950). MR 33525
- Sze-Tsen Hu, A cohomology theory with higher coboundary operators. III. The homotopy axiom and the groups for spheres, Nederl. Akad. Wetensch. Proc. Ser. A. 55 = Indagationes Math. 14 (1952), 123โ129. MR 0047324
- William M. Kantor, On incidence matrices of finite projective and affine spaces, Math. Z. 124 (1972), 315โ318. MR 377681, DOI 10.1007/BF01113923
- Nathan Linial and Bruce L. Rothschild, Incidence matrices of subsetsโa rank formula, SIAM J. Algebraic Discrete Methods 2 (1981), no.ย 3, 333โ340. MR 627600, DOI 10.1137/0602037
- 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 427128, DOI 10.1137/0128070
- W. Mielants and H. Leemans, $Z_{2}$-cohomology of projective spaces of odd order, Combinatorics โ81 (Rome, 1981) Ann. Discrete Math., vol. 18, North-Holland, Amsterdam-New York, 1983, pp.ย 635โ651. MR 695848
- James R. Munkres, Elements of algebraic topology, Addison-Wesley Publishing Company, Menlo Park, CA, 1984. MR 755006
- J. J. Seidel, A survey of two-graphs, Colloquio Internazionale sulle Teorie Combinatorie (Roma, 1973) Atti dei Convegni Lincei, No. 17, Accad. Naz. Lincei, Rome, 1976, pp.ย 481โ511 (English, with Italian summary). MR 0550136
- J. J. Seidel and D. E. Taylor, Two-graphs, a second survey, Algebraic methods in graph theory, Vol. I, II (Szeged, 1978) Colloq. Math. Soc. Jรกnos Bolyai, vol. 25, North-Holland, Amsterdam-New York, 1981, pp.ย 689โ711. MR 642068
- Albert L. Wells Jr., Even signings, signed switching classes, and $(-1,\,1)$-matrices, J. Combin. Theory Ser. B 36 (1984), no.ย 2, 194โ212. MR 746549, DOI 10.1016/0095-8956(84)90025-X
- Richard M. Wilson, A diagonal form for the incidence matrices of $t$-subsets vs. $k$-subsets, European J. Combin. 11 (1990), no.ย 6, 609โ615. MR 1078717, DOI 10.1016/S0195-6698(13)80046-7
- Thomas Zaslavsky, Characterizations of signed graphs, J. Graph Theory 5 (1981), no.ย 4, 401โ406. MR 635702, DOI 10.1002/jgt.3190050409
Bibliographic Information
- © Copyright 1992 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 334 (1992), 365-388
- MSC: Primary 05C65; Secondary 18G99, 55N99, 57Q99, 60C05
- DOI: https://doi.org/10.1090/S0002-9947-1992-1089416-0
- MathSciNet review: 1089416