The DOI matches its Crossref record; 6 of the 6 references it cites were found in a registry or an index.
Bisection of Circle Colorings
Abstract
Consider $2n$ beads of k colors arranged on a necklace, using $2a$, beads of color i. A bisection is a set of disjoint strings (“intervals”) of beads whose union captures half the beads of each color. We prove that any arrangement with k colors has a bisection using at most $\lceil k / 2 \rceil $ intervals. In addition, if k is odd, an endpoint of one interval can be specified arbitrarily. The result is best possible. For fixed k, there is a polynomial-time algorithm to find such a bisection; it runs in $O ( n^{k - 2} )$ for $k\geqq 3$. We consider continuous and linear versions of the problem and use them to obtain applications in geometry, VLSI circuit design, and orthogonal functions.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“A well-known theorem of Goldberg and West states that two thieves can always split a necklace containing an even number of beads from each of k types fairly by at most k cuts.”
From Necklace Bisection with One Cut Less than Needed (2008) · cites this paper as [6]
In the citing paper
“As noted in [4], this also allows us to satisfy the jewel thieves when some colors appear an odd number of times.For whatever partition of the”
From The Borsuk-Ulam Theorem and Bisection of Necklaces (1986) · cites this paper as [4]
In the citing paper
“Every necklace with fc colors has a bisection formed by at most k cuts.”
From The Borsuk-Ulam Theorem and Bisection of Necklaces (1986) · cites this paper as [4]
Citations
Cites
Villani, V (2011) · Springer eBooks · doi:10.1007/978-3-642-11102-0 · Cited by 564
Some Unsolved Problems in Plane Geometry
Klee, V. L. (1979) · Mathematics Magazine · doi:10.1080/0025570x.1979.11976769 · Cited by 48
Inscribed Squares in Plane Curves
Jerrard, R. (1961) · Transactions of the American Mathematical Society · doi:10.1090/s0002-9947-1961-0120604-3 · Cited by 31
A layout strategy for VLSI which is provably good (Extended Abstract)
Leighton, F. T. (1982) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/800070.802180 · Cited by 28
On the enumeration of cross-sections
James, I. M., & Thomas, E. (1966) · Topology · doi:10.1016/0040-9383(66)90012-7 · Cited by 15
How to assemble tree machines (Extended Abstract)
Bhatt, S. N., & Leiserson, C. E. (1982) · Proceedings of the fourteenth annual ACM symposium on Theory of computing · doi:10.1145/800070.802179
Research works printed but not linked: 1
- 10.2307/2690274 · doi:10.2307/2690274
Cited by
Alon, N. (1987) · Advances in Mathematics · doi:10.1016/0001-8708(87)90055-7 · Cited by 136
The Chromatic Number of Kneser Hypergraphs
Alon, N., Frankl, P., & Lovász, L. (1986) · Transactions of the American Mathematical Society · doi:10.1090/s0002-9947-1986-0857448-8 · Cited by 127
The Borsuk-Ulam Theorem and Bisection of Necklaces
Alon, N., & West, D. B. (1986) · Proceedings of the American Mathematical Society · doi:10.1090/s0002-9939-1986-0861764-9 · Cited by 88
Self-citationThe discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
Loera, J. A. D., Goaoc, X., Meunier, F., & Mustafa, N. H. (2019) · Bulletin of the American Mathematical Society · doi:10.1090/bull/1653 · Cited by 85
Consensus-halving via theorems of Borsuk-Ulam and Tucker
Simmons, F. W., & Su, F. E. (2003) · Mathematical Social Sciences · doi:10.1016/s0165-4896(02)00087-2 · Cited by 74
Equipartition of mass distributions by hyperplanes
Ramos, E. A. (1996) · Discrete & Computational Geometry · doi:10.1007/bf02717729 · Cited by 62
Computing Parametric Rational Generating Functions with a Primal Barvinok Algorithm
Köppe, M., & Verdoolaege, S. (2008) · The Electronic Journal of Combinatorics · doi:10.37236/740 · Cited by 58
The complexity of splitting necklaces and bisecting ham sandwiches
Filos-Ratsikas, A., & Goldberg, P. W. (2019) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3313276.3316334 · Cited by 36
Embedding an arbitrary binary tree into the star graph
Bagherzadeh, N., Dowd, M., & Nassif, N. (1996) · IEEE Transactions on Computers · doi:10.1109/12.494105 · Cited by 33
Roldán-Pensado, E., & Soberón, P. (2021) · Bulletin of the American Mathematical Society · doi:10.1090/bull/1725 · Cited by 32
Fair Division and Generalizations of Sperner- and KKM-type Results
Asada, M., Frick, F., Pisharody, V., Polevy, M., Stoner, D., Tsang, L. H., & Wellner, Z. (2018) · SIAM Journal on Discrete Mathematics · doi:10.1137/17m1116210 · Cited by 31
Hardness Results for Consensus-Halving
Filos-Ratsikas, A., Frederiksen, S. K. S., Goldberg, P. W., & Zhang, J. (2016) · doi:10.4230/lipics.mfcs.2018.24 · Cited by 23
Consensus Halving for Sets of Items
Goldberg, P. W., Hollender, A., Igarashi, A., Manurangsi, P., & Suksompong, W. (2020) · Mathematics of Operations Research · doi:10.1287/moor.2021.1249 · Cited by 23
Splitting multidimensional necklaces
de Longueville, M., & Živaljević, R. T. (2008) · Advances in Mathematics · doi:10.1016/j.aim.2008.02.003 · Cited by 22
Some Combinatorial and Algorithmic Applications of the Borsuk–Ulam Theorem
Roy, S., & Steiger, W. (2007) · Graphs and Combinatorics · doi:10.1007/s00373-007-0716-1 · Cited by 22
Capalbo, M., & Kosaraju, S. R. (1999) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/301250.301446 · Cited by 21
Measure Partitions Using Hyperplanes with Fixed DirectionsPreprint
(n.d.) · Cited by 20
A Topological Characterization of Modulo- p Arguments and Implications for Necklace Splitting
Filos-Ratsikas, A., Hollender, A., Sotiraki, K., & Zampetakis, M. (2021) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611976465.155 · Cited by 19
Discrete Splittings of the Necklace
Meunier, F. (2008) · Mathematics of Operations Research · doi:10.1287/moor.1080.0311 · Cited by 18
Non-constructive proofs in Combinatorics
Alon, N. (2002) · Cited by 18
A New Efficient Algorithm for Embedding an Arbitrary Binary Tree into Its Optimal Hypercube
Heun, V., & Mayr, E. W. (1996) · Journal of Algorithms · doi:10.1006/jagm.1996.0018 · Cited by 18
Efficient Splitting of Measures and NecklacesPreprint
Alon, N., & Graur, A. (2020) · arXiv (Cornell University) · doi:10.4230/lipics.icalp.2021.14 · Cited by 18
Paintshop, odd cycles and necklace splitting
Meunier, F., & Sebö, A. (2008) · Discrete Applied Mathematics · doi:10.1016/j.dam.2008.06.017 · Cited by 17
Computing solutions of the paintshop–necklace problem
Meunier, F., & Neveu, B. (2012) · Computers & Operations Research · doi:10.1016/j.cor.2012.01.014 · Cited by 16
Simplotopal maps and necklace splitting
Meunier, F. (2014) · Discrete Mathematics · doi:10.1016/j.disc.2014.01.008 · Cited by 15
Multilabeled Versions of Sperner's and Fan's Lemmas and Applications
Meunier, F., & Su, F. E. (2019) · SIAM Journal on Applied Algebra and Geometry · doi:10.1137/18m1192548 · Cited by 14
Blagojević, P. V. M., & Soberón, P. (2017) · Bulletin of the London Mathematical Society · doi:10.1112/blms.12109 · Cited by 13
Constant inapproximability for PPA
Deligkas, A., Fearnley, J., Hollender, A., & Melissourgos, T. (2022) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3519935.3520079 · Cited by 12
Discrete Geometry on Colored Point Sets in the Plane—A Survey
Kanō, M., & Urrutia, J. (2020) · Graphs and Combinatorics · doi:10.1007/s00373-020-02210-8 · Cited by 12
Schröder, H., Sýykoa, O., & Vrt’o, I. (1999) · Lecture notes in computer science · doi:10.1007/3-540-47849-3_33 · Cited by 12
Combinatorial Necklace Splitting
Pálvölgyi, D. (2009) · The Electronic Journal of Combinatorics · doi:10.37236/168 · Cited by 11
Two's company, three's a crowd: Consensus-halving for a constant number of agents
Deligkas, A., Filos-Ratsikas, A., & Hollender, A. (2022) · Artificial Intelligence · doi:10.1016/j.artint.2022.103784 · Cited by 11
On the Complexity of Modulo-q Arguments and the Chevalley - Warning TheoremPreprint
Göös, M., Kamath, P., Sotiraki, K., & Zampetakis, M. (2019) · arXiv (Cornell University) · doi:10.4230/lipics.ccc.2020.19 · Cited by 11
Size‐Ramsey Numbers of Structurally Sparse Graphs
Draganić, N., Kaufmann, M., Correia, D. M., Petrova, K., & Steiner, R. (2026) · Random Structures and Algorithms · doi:10.1002/rsa.70059 · Cited by 10
The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich
Filos-Ratsikas, A., & Goldberg, P. W. (2022) · SIAM Journal on Computing · doi:10.1137/20m1312678 · Cited by 10
Cyclic cutwidths of the two-dimensional ordinary and cylindrical meshes
Schröder, H., Sýkora, O., & Vrt’o, I. (2004) · Discrete Applied Mathematics · doi:10.1016/j.dam.2003.10.006 · Cited by 10
Optimal Cache-Oblivious Mesh Layouts
Bender, M. A., Kuszmaul, B. C., Teng, S., & Wang, K. (2009) · Theory of Computing Systems · doi:10.1007/s00224-009-9242-2 · Cited by 10
A Topological Characterization of Modulo-$p$ Arguments and Implications for Necklace SplittingPreprint
Filos-Ratsikas, A., Hollender, A., Sotiraki, K., & Zampetakis, M. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2003.11974 · Cited by 10
Consensus-Halving: Does It Ever Get Easier?
Filos-Ratsikas, A., Hollender, A., Sotiraki, K., & Zampetakis, M. (2023) · SIAM Journal on Computing · doi:10.1137/20m1387493 · Cited by 9
Splitting necklaces and measurable colorings of the real line
Alon, N., Grytczuk, J., Lasoń, M., & Michałek, M. (2008) · Proceedings of the American Mathematical Society · doi:10.1090/s0002-9939-08-09699-8 · Cited by 8
Embedding Graphs with Bounded Treewidth into Their Optimal Hypercubes
Heun, V., & Mayr, E. W. (2002) · Journal of Algorithms · doi:10.1006/jagm.2002.1217 · Cited by 8
Efficient Embeddings into Hypercube-like Topologies
Heun, V. (2003) · The Computer Journal · doi:10.1093/comjnl/46.6.632 · Cited by 8
The Complexity of Finding Fair Independent Sets in Cycles
Haviv, I. (2022) · Computational Complexity · doi:10.1007/s00037-022-00233-6 · Cited by 7
LONG INDUCED CYCLES IN THE HYPERCUBE AND COLOURINGS OF GRAPHS
Wojciechowski, J. (1990) · Cited by 7
An approach to emulating separable graphs
Obrenić, B. (1994) · Theory of Computing Systems · doi:10.1007/bf01187092 · Cited by 7
Lifting Methods in Mass Partition Problems
Soberón, P., & Takahashi, Y. (2022) · International Mathematics Research Notices · doi:10.1093/imrn/rnac224 · Cited by 6
Obstacles for splitting multidimensional necklaces
Lasoń, M. (2015) · Proceedings of the American Mathematical Society · doi:10.1090/s0002-9939-2015-12611-1 · Cited by 6
Two's Company, Three's a Crowd: Consensus-Halving for a Constant Number of Agents
Deligkas, A., Filos-Ratsikas, A., & Hollender, A. (2021) · ACM Conference on Economics and Computation (EC) · doi:10.1145/3465456.3467625 · Cited by 6
Efficient Dynamic Embeddings of Binary Trees into Hypercubes
Heun, V., & Mayr, E. W. (2002) · Journal of Algorithms · doi:10.1006/jagm.2002.1218 · Cited by 6
Necklace Bisection with One Cut Less than Needed
Simonyi, G. (2008) · The Electronic Journal of Combinatorics · doi:10.37236/891 · Cited by 5
Splitting Multidimensional Necklaces and Measurable Colorings of Euclidean Spaces
Grytczuk, J., & Lubawski, W. (2015) · SIAM Journal on Discrete Mathematics · doi:10.1137/130948239 · Cited by 5
More Variations on Shuffle Squares
Grytczuk, J., Pawlik, B., & Pleszczyński, M. (2023) · Symmetry · doi:10.3390/sym15111982 · Cited by 5
Embedding graphs with bounded treewidth into optimal hypercubes
Heun, V., & Mayr, E. W. (1996) · Lecture notes in computer science · doi:10.1007/3-540-60922-9_14 · Cited by 5
Polytopal complexes: maps, chain complexes and… necklaces
Meunier, F. (2008) · Electronic Notes in Discrete Mathematics · doi:10.1016/j.endm.2008.06.037 · Cited by 5
A Tight Lower Bound on the Size of Planar Permutation Networks
Klawe, M. M., & Leighton, T. (1992) · SIAM Journal on Discrete Mathematics · doi:10.1137/0405045 · Cited by 5
A general method for efficient embeddings of graphs into optimal hypercubes
Heun, V., & Mayr, E. W. (1996) · Lecture notes in computer science · doi:10.1007/3-540-61626-8_29 · Cited by 4
Measure partitions using hyperplanes with fixed directions
Карасев, Р., Roldán-Pensado, E., & Soberón, P. (2016) · Israel Journal of Mathematics · doi:10.1007/s11856-016-1303-z · Cited by 2
Bondy, J. A. (1989) · Annals of the New York Academy of Sciences · doi:10.1111/j.1749-6632.1989.tb22483.x · Cited by 2
Coloring games and algebraic problems on matroidsPreprint
Lasoń, M. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1501.00224 · Cited by 2
An FPT Algorithm for Splitting a Necklace Among Two Thieves
Borzechowski, M., Schnider, P., & Weber, S. (2025) · Algorithmica · doi:10.1007/s00453-025-01346-4 · Cited by 1
High-dimensional envy-free partitions
Soberón, P., & Yu, C. (2026) · Combinatorial Theory · doi:10.5070/c66165698 · Cited by 1
Dębski, M., Grytczuk, J., Pawlik, B., Przybyło, J., & Śleszyńska-Nowak, M. (2024) · Annals of Combinatorics · doi:10.1007/s00026-024-00736-9 · Cited by 1
Constant Inapproximability for PPA
Deligkas, A., Fearnley, J., Hollender, A., & Melissourgos, T. (2025) · SIAM Journal on Computing · doi:10.1137/22m1536613 · Cited by 1
Soberón, P. (2026) · Proceedings of the American Mathematical Society · doi:10.1090/proc/17658 · Cited by 1
A tight lower bound on the size of planar permutation networks
Klawe, M. M., & Leighton, T. (1990) · Lecture notes in computer science · doi:10.1007/3-540-52921-7_77 · Cited by 1
An FPT Algorithm for Splitting a Necklace Among Two ThievesPreprint
Borzechowski, M., Schnider, P., & Weber, S. (2023) · arXiv (Cornell University) · doi:10.4230/lipics.isaac.2023.15 · Cited by 1
Dynamic Necklace SplittingPreprint
Advani, R., Asudeh, A., Dehghankar, M., & Sintos, S. (2025) · arXiv (Cornell University) · doi:10.4230/lipics.icdt.2026.19 · Cited by 1
SPLITTING NECKLACES AND A GENERALIZATION OF THE BORSUK-ULAM ANTIPODAL THEOREM
Wojciechowski, J. (1996)
Unfairly Splitting Separable NecklacesPreprint
Schnider, P., Stalder, L., & Weber, S. (2024) · arXiv (Cornell University) · doi:10.4230/lipics.stacs.2025.71
Card-Based Zero-Knowledge Proofs for Necklace Splitting Problem
Ikeda, S., & Shinagawa, K. (2026) · Lecture notes in computer science · doi:10.1007/978-981-92-6840-5_21
Metadata
- Authors
- Goldberg, C. H., & West, D. B.
- ORCID
- West, Douglas B.
- Venue
- SIAM Journal on Algebraic Discrete Methods
- Published
- 1985-01
- Volume
- 6
- Issue
- 1
- Pages
- 93-106
- ISSN
- 0196-5212 (ISSN-L)
- 2168-345X
- OpenAlex
- W2016462171
- Semantic Scholar
- 6b74516001b73a690e4c4ef01ac024254f312f4e
- Cited by
- 69
- References
- 4
- Citations by year
- 2026: 4 · 2025: 3 · 2024: 2 · 2023: 3 · 2022: 5 · 2021: 3 · 2020: 4 · 2019: 4 · 2018: 1 · 2017: 1 · 2016: 2 · 2015: 3 · 2014: 1 · 2012: 1
- FWCI
- 1.58
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- SIAM Journal on Algebraic and Discrete Methods (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Mathematics › Discrete Mathematics and Combinatorics › Advanced Combinatorial Mathematics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Advanced Graph Theory Research
- Keywords
- interval bisection, polynomial-time algorithms, VLSI design, orthogonal functions, combinatorial geometry
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.