The Borsuk-Ulam theorem and bisection of necklaces
HTML articles powered by AMS MathViewer
- by Noga Alon and Douglas B. West PDF
- Proc. Amer. Math. Soc. 98 (1986), 623-628 Request permission
Abstract:
The Borsuk-Ulam theorem of topology is applied to a problem in discrete mathematics. A bisection of a necklace with $k$ colors of beads is a collection of intervals whose union captures half the beads of each color. Every necklace with $k$ colors has a bisection formed by at most $k$ cuts. Higher-dimensional generalizations are considered.References
-
S. N. Bhatt and C. E. Leiserson, How to assemble tree machines, Proc. 14th ACM Sympos. Theor. Computing, San Francisco, Assoc. Comp. Mach., 1981, pp. 99-104.
K. Borsuk, Drei Satze uber die $n$-dimensionale euklidische Sphare, Fund, Math. 20 (1933), 177-190.
- James Dugundji, Topology, Allyn and Bacon, Inc., Boston, Mass., 1966. MR 0193606
- Charles H. Goldberg and Douglas B. West, Bisection of circle colorings, SIAM J. Algebraic Discrete Methods 6 (1985), no. 1, 93–106. MR 772181, DOI 10.1137/0606010
- Charles R. Hobby and John R. Rice, A moment problem in $L_{1}$ approximation, Proc. Amer. Math. Soc. 16 (1965), 665–670. MR 178292, DOI 10.1090/S0002-9939-1965-0178292-5
- A. Liapounoff, Sur les fonctions-vecteurs complètement additives, Bull. Acad. Sci. URSS. Sér. Math. [Izvestia Akad. Nauk SSSR] 4 (1940), 465–478 (Russian, with French summary). MR 0004080
- Allan Pinkus, A simple proof of the Hobby-Rice theorem, Proc. Amer. Math. Soc. 60 (1976), 82–84 (1977). MR 425470, DOI 10.1090/S0002-9939-1976-0425470-0
- Noga Alon, Splitting necklaces, Adv. in Math. 63 (1987), no. 3, 247–253. MR 877785, DOI 10.1016/0001-8708(87)90055-7
Additional Information
- © Copyright 1986 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 98 (1986), 623-628
- MSC: Primary 05A20; Secondary 05A15, 54H25, 55M20, 68R05
- DOI: https://doi.org/10.1090/S0002-9939-1986-0861764-9
- MathSciNet review: 861764