Editing Binary logarithm (section)

===Combinatorics===
[[File:SixteenPlayerSingleEliminationTournamentBracket.svg|thumb|upright=1.2|A 16-player [[single elimination]] [[Bracket (tournament)|tournament bracket]] with the structure of a [[complete binary tree]]. The height of the tree (number of rounds of the tournament) is the binary logarithm of the number of players, rounded up to an integer.]]
Although the natural logarithm is more important than the binary logarithm in many areas of pure mathematics such as [[number theory]] and [[mathematical analysis]],<ref>{{citation|title=Taming the Infinite|first=Ian|last=Stewart|author-link=Ian Stewart (mathematician)|publisher=Quercus|year=2015|isbn=9781623654733|quote=in advanced mathematics and science the only logarithm of importance is the natural logarithm|page=120|url=https://books.google.com/books?id=u4HPBAAAQBAJ&pg=PT120}}.</ref> the binary logarithm has several applications in [[combinatorics]]:
*Every [[binary tree]] with {{mvar|n}} leaves has height at least {{math|log<sub>2</sub>{{hsp}}''n''}}, with equality when {{mvar|n}} is a [[power of two]] and the tree is a [[complete binary tree]].<ref>{{citation
 | last = Leiss | first = Ernst L.
 | isbn = 978-1-4200-1170-8
 | page = 28
 | publisher = CRC Press
 | title = A Programmer's Companion to Algorithm Analysis
 | url = https://books.google.com/books?id=E6BNGFQ6m_IC&pg=RA2-PA28
 | year = 2006}}.</ref> Relatedly, the [[Strahler number]] of a river system with {{mvar|n}} tributary streams is at most {{math|log<sub>2</sub>{{hsp}}''n'' + 1}}.<ref>{{citation
 | last1 = Devroye | first1 = L. | author1-link = Luc Devroye
 | last2 = Kruszewski | first2 = P.
 | issue = 5
 | journal = RAIRO Informatique Théorique et Applications
 | mr = 1435732
 | pages = 443–456
 | title = On the Horton–Strahler number for random tries
 | url = https://eudml.org/doc/92635
 | volume = 30
 | year = 1996| doi = 10.1051/ita/1996300504431 | doi-access = free
 }}.</ref>
*Every [[family of sets]] with {{mvar|n}} different sets has at least {{math|log<sub>2</sub>{{hsp}}''n''}} elements in its union, with equality when the family is a [[power set]].<ref>Equivalently, a family with {{mvar|k}} distinct elements has at most {{math|2<sup>''k''</sup>}} distinct sets, with equality when it is a power set.</ref>
*Every [[partial cube]] with {{mvar|n}} vertices has isometric dimension at least {{math|log<sub>2</sub>{{hsp}}''n''}}, and has at most  {{math|{{sfrac|1|2}} ''n'' log<sub>2</sub>{{hsp}}''n''}} edges, with equality when the partial cube is a [[hypercube graph]].<ref>{{citation
 | last = Eppstein | first = David | author-link = David Eppstein
 | arxiv = cs.DS/0402028
 | doi = 10.1016/j.ejc.2004.05.001
 | issue = 5
 | journal = European Journal of Combinatorics
 | mr = 2127682
 | pages = 585–592
 | title = The lattice dimension of a graph
 | volume = 26
 | year = 2005| s2cid = 7482443 }}.</ref>
*According to [[Ramsey's theorem]], every {{mvar|n}}-vertex [[undirected graph]] has either a [[Clique (graph theory)|clique]] or an [[Independent set (graph theory)|independent set]] of size logarithmic in {{mvar|n}}. The precise size that can be guaranteed is not known, but the best bounds known on its size involve binary logarithms. In particular, all graphs have a clique or independent set of size at least {{math|{{sfrac|1|2}} log<sub>2</sub>{{hsp}}''n'' (1 − ''o''(1))}} and almost all graphs do not have a clique or independent set of size larger than {{math|2 log<sub>2</sub>{{hsp}}''n'' (1 + ''o''(1))}}.<ref>{{citation
 | last1 = Graham | first1 = Ronald L. | author1-link = Ronald Graham
 | last2 = Rothschild | first2 = Bruce L. | author2-link = Bruce Lee Rothschild
 | last3 = Spencer | first3 = Joel H. | author3-link = Joel Spencer
 | page = 78
 | publisher = Wiley-Interscience
 | title = Ramsey Theory
 | year = 1980}}.</ref>
*From a mathematical analysis of the [[Gilbert–Shannon–Reeds model]] of random shuffles, one can show that the number of times one needs to shuffle an {{mvar|n}}-card deck of cards, using [[riffle shuffle]]s, to get a distribution on permutations that is close to uniformly random, is approximately {{math|{{sfrac|3|2}} log<sub>2</sub>{{hsp}}''n''}}. This calculation forms the basis for a recommendation that 52-card decks should be shuffled seven times.<ref>{{citation
 | last1 = Bayer | first1 = Dave | author1-link = Dave Bayer
 | last2 = Diaconis | first2 = Persi | author2-link = Persi Diaconis
 | issue = 2
 | journal = The Annals of Applied Probability
 | jstor = 2959752
 | mr = 1161056
 | pages = 294–313
 | title = Trailing the dovetail shuffle to its lair
 | volume = 2
 | year = 1992 | doi=10.1214/aoap/1177005705| doi-access = free
 }}.</ref>