Sets of lattice points which contain a maximal number of edges
HTML articles powered by AMS MathViewer
- by G. F. Clements PDF
- Proc. Amer. Math. Soc. 27 (1971), 13-15 Request permission
Abstract:
How should one select an $l$-element subset of a rectangular array of lattice points (points with integral coordinates) in $n$-dimensional Euclidean space so as to include the largest possible number of edges (pairs of points differing in exactly one coordinate)? It is shown that the generalized Macaulay theorem due to the author and B. Lindström contains the (known) solution.References
- A. J. Bernstein, Maximally connected arrays on the $n$-cube, SIAM J. Appl. Math. 15 (1967), 1485–1489. MR 223260, DOI 10.1137/0115129
- G. F. Clements and B. Lindström, A generalization of a combinatorial theorem of Macaulay, J. Combinatorial Theory 7 (1969), 230–238. MR 246781
- L. H. Harper, Optimal assignments of numbers to vertices, J. Soc. Indust. Appl. Math. 12 (1964), 131–135. MR 162737
- G. Katona, A theorem of finite sets, Theory of graphs (Proc. Colloq., Tihany, 1966) Academic Press, New York, 1968, pp. 187–207. MR 0290982
- Joseph B. Kruskal, The number of simplices in a complex, Mathematical optimization techniques, Univ. California Press, Berkeley, Calif., 1963, pp. 251–278. MR 0154827
- J. B. Kruskal, The number of $s$-dimensional faces in a complex: An analogy between the simplex and the cube, J. Combinatorial Theory 6 (1969), 86–89. MR 236030
- John H. Lindsey II, Assignment of numbers to vertices, Amer. Math. Monthly 71 (1964), 508–516. MR 168489, DOI 10.2307/2312587
Additional Information
- © Copyright 1971 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 27 (1971), 13-15
- MSC: Primary 05.04
- DOI: https://doi.org/10.1090/S0002-9939-1971-0270923-7
- MathSciNet review: 0270923