Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



The Borsuk-Ulam theorem and bisection of necklaces

Authors: Noga Alon and Douglas B. West
Journal: Proc. Amer. Math. Soc. 98 (1986), 623-628
MSC: Primary 05A20; Secondary 05A15, 54H25, 55M20, 68R05
MathSciNet review: 861764
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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.
  • [2] K. Borsuk, Drei Satze uber die $ n$-dimensionale euklidische Sphare, Fund, Math. 20 (1933), 177-190.
  • [3] J. Dugundji, Topology, Allyn and Bacon, Boston, Mass., 1966, pp. 347-349. MR 0193606 (33:1824)
  • [4] C. H Goldberg and D. B. West, Bisection of circle colorings, SIAM J. Algebraic Discrete Methods 6 (1985), 93-106. MR 772181 (86c:05010)
  • [5] C. R. Hobby and J. R. Rice, A moment problem in $ {L_1}$ approximation, Proc. Amer. Math. Soc. 16 (1965), 665-670. MR 0178292 (31:2550)
  • [6] A. Liapounoff, Sur les fonctions vecteurs completement additives, Izv. Akad. Nauk SSSR 4 (1940), 465-478. MR 0004080 (2:315e)
  • [7] A. Pinkus, A simple proof of the Hobby-Rice theorem, Proc. Amer. Math. Soc. 60 (1976), 82-84. MR 0425470 (54:13425)
  • [8] N. Alon, Splitting necklaces, Adv. in Math. (to appear). MR 877785 (88f:05010)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 05A20, 05A15, 54H25, 55M20, 68R05

Retrieve articles in all journals with MSC: 05A20, 05A15, 54H25, 55M20, 68R05

Additional Information

Article copyright: © Copyright 1986 American Mathematical Society

American Mathematical Society