Another algebraic proof of Bondy's theorem on induced subsets
\textit{J. A. Bondy} proved in 1972 [J. Comb. Theory, Ser. A 12, 201-202 (1972; Zbl 0226.05010) and ibid., Ser. B 12, 201-202 (1972; Zbl 0211.56901)] that for any family of at most \(n\) distinct subsets of an \(n\)-element set there is an element in that ground set that we can delete from all sets of the family such that the remaining sets are still all distinct. Several proofs of this simple fact are known. The author of the present paper presents another simple proof that even gives a more general statement: For any family of at most \(\left\lceil {n\over d}\right\rceil\) subsets of an \(n\)-element set with pairwise Hamming distance at least \(d\) there is an element in that ground set that we can delete from all elements of the family such that the remaining sets still have pairwise Hamming distance at least \(d\).
- Intersection patterns of linear subspaces with the hypercube
- Characterizing extremal digraphs for identifying codes and extremal cases of Bondy's theorem on induced subsets
- Inclusionwise minimal completely separating systems
- Another Proof That $\mathcal{BPP}\subseteq \mathcal{PH}$ (and More)
- Rounds in combinatorial search
- Two proofs of Bondy's theorem on induced subsets and two related questions
- Identifying codes in triangle-free graphs of bounded maximum degree
This page was built for publication: Another algebraic proof of Bondy's theorem on induced subsets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1971019)
