article

Some combinatorial Lemmas in topology

Author:

H. W. KuhnAuthors Info & Claims

IBM Journal of Research and Development, Volume 4, Issue 5

Pages 518 - 524

https://doi.org/10.1147/rd.45.0518

Published: 01 November 1960 Publication History

Abstract

For many years it has been known that a combinatorial result, called the Sperner Lemma, provides an elegant proof of the Brouwer Fixed Point Theorem. Although the proof is elementary, its complete formal exposition depends upon the somewhat complicated operation of subdividing a simplex. Also, the proof does not show whether the Sperner Lemma can be derived from the Brouwer Fixed Point Theorem.

This central result of this paper is a combinatorial proposition, analogous to the Sperner Lemma, and applying to the n-cube, for which subdivision is a trivial operation. This Cubical Sperner Lemma follows immediately from the Brouwer Fixed Point Theorem and thus opens the possibility of other applications of topology to combinatorial problems. The question of such a topological proof is raised for another cubical analogue of the Sperner Lemma, due to Ky Fan, and for the Tucker Lemma, which is related to the antipodal point theorems. The Cubical Sperner Lemma of this paper implies the Tucker Lemma in 2-dimensions; this suggests that other connections joining these combinatorial results remain to be discovered.

References

[1]

B. Knaster, K. Kuratowski, and S. Maeurkiewice, Fundamental Math. 14, 132 (1929).

Crossref

Google Scholar

[2]

E. Sperner, Abh. math. Sem. Hamburg, 6, 265 (1928).

Crossref

Google Scholar

[3]

The simplical decomposition of the cube described in the lemma has been used previously by A. W. Tucker. It appears as Problem 3, p. 140, of Introductions to Topology by S. Lefschete, Princeton University Press, 1949.

Google Scholar

[4]

S. Kakutani, Duke Math. J. 8, 457 (1941).

Google Scholar

[5]

A. W. Tucker, Proceedings, Canadian Math. Congress, p. 285 (Montreal 1945).

Google Scholar

[6]

S. Lefschetz, Princeton University Press, 1949.

Google Scholar

Cited By

View all

Kissi MPont MLevine JTierny J(2024)A Practical Solver for Scalar Data Topological SimplificationIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2024.345634531:1(97-107)Online publication date: 10-Sep-2024
https://dl.acm.org/doi/10.1109/TVCG.2024.3456345
Le Guillou EWill MGuillou PLukasczyk JFortin PGarth CTierny J(2024)TTK is Getting MPI-ReadyIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2024.339021930:8(5875-5892)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TVCG.2024.3390219
Guillou PVidal JTierny J(2024)Discrete Morse Sandwich: Fast Computation of Persistence Diagrams for Scalar Data – An Algorithm and a BenchmarkIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2023.323800830:4(1897-1915)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1109/TVCG.2023.3238008
Show More Cited By

Recommendations

Combinatorial PCPs with Efficient Verifiers

The PCP theorem asserts the existence of proofs that can be verified by a verifier that reads only a very small part of the proof. The theorem was originally proved by Arora and Safra (J. ACM 45(1)) and Arora et al. (J. ACM 45(3)) using sophisticated ...
Combinatorial PCPs with Efficient Verifiers
FOCS '09: Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science

The PCP theorem asserts the existence of proofs that can be verified by a verifier that reads only a very small part of the proof. The theorem was originally proved by Arora and Safra (J. ACM 45(1)) and Arora et al. (J. ACM 45(3)) using sophisticated ...
Combinatorial PCPs with Short Proofs

The Probabilistically Checkable Proof (PCP) theorem (Arora and Safra in J ACM 45(1):70---122, 1998; Arora et al. in J ACM 45(3):501---555, 1998) asserts the existence of proofs that can be verified by reading a very small part of the proof. Since the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IBM Journal of Research and Development

IBM Journal of Research and Development Volume 4, Issue 5

November 1960

105 pages

ISSN:0018-8646

Issue’s Table of Contents

Publisher

IBM Corp.

United States

Publication History

Published: 01 November 1960

Received: 22 July 1960

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

45
Total Citations
View Citations
2
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kissi MPont MLevine JTierny J(2024)A Practical Solver for Scalar Data Topological SimplificationIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2024.345634531:1(97-107)Online publication date: 10-Sep-2024
https://dl.acm.org/doi/10.1109/TVCG.2024.3456345
Le Guillou EWill MGuillou PLukasczyk JFortin PGarth CTierny J(2024)TTK is Getting MPI-ReadyIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2024.339021930:8(5875-5892)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TVCG.2024.3390219
Guillou PVidal JTierny J(2024)Discrete Morse Sandwich: Fast Computation of Persistence Diagrams for Scalar Data – An Algorithm and a BenchmarkIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2023.323800830:4(1897-1915)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1109/TVCG.2023.3238008
Dixon PPavan AWoude JVinodchandran NLeonardi SGupta A(2022)Pseudodeterminism: promises and lowerboundsProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520043(1552-1565)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520043
Huchette JVielma J(2019)A Combinatorial Approach for Small and Strong Formulations of Disjunctive ConstraintsMathematics of Operations Research10.1287/moor.2018.094644:3(793-820)Online publication date: 1-Aug-2019
https://dl.acm.org/doi/10.1287/moor.2018.0946
Singh KShen QYong S(2018)Mesh-Based Affine Abstraction of Nonlinear Systems with Tighter Bounds2018 IEEE Conference on Decision and Control (CDC)10.1109/CDC.2018.8618714(3056-3061)Online publication date: 17-Dec-2018
https://dl.acm.org/doi/10.1109/CDC.2018.8618714
Hošek R(2018)Construction and Shape Optimization of Simplicial Meshes in d-Dimensional SpaceDiscrete & Computational Geometry10.1007/s00454-017-9963-y59:4(972-989)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.1007/s00454-017-9963-y
López-Rubio EMuñoz-Pérez J(2015)Probability density function estimation with the frequency polygon transformInformation Sciences: an International Journal10.1016/j.ins.2014.12.014298:C(136-158)Online publication date: 20-Mar-2015
https://dl.acm.org/doi/10.1016/j.ins.2014.12.014
Baek JAdams ADolson J(2013)Lattice-Based High-Dimensional Gaussian Filtering and the Permutohedral LatticeJournal of Mathematical Imaging and Vision10.1007/s10851-012-0379-246:2(211-237)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1007/s10851-012-0379-2
Harrison J(2013)The HOL Light Theory of Euclidean SpaceJournal of Automated Reasoning10.1007/s10817-012-9250-950:2(173-190)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1007/s10817-012-9250-9
Show More Cited By

Abstract

References

Cited By

Recommendations

Combinatorial PCPs with Efficient Verifiers

Combinatorial PCPs with Efficient Verifiers

Combinatorial PCPs with Short Proofs

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations