In mathematics, a **power of three** is a number of the form 3^{n} where n is an integer – that is, the result of exponentiation with number three as the base and integer n as the exponent.

The powers of three give the place values in the ternary numeral system.^{ [1] }

In graph theory, powers of three appear in the Moon–Moser bound 3^{n/3} on the number of maximal independent sets of an n-vertex graph,^{ [2] } and in the time analysis of the Bron–Kerbosch algorithm for finding these sets.^{ [3] } Several important strongly regular graphs also have a number of vertices that is a power of three, including the Brouwer–Haemers graph (81 vertices), Berlekamp–van Lint–Seidel graph (243 vertices), and Games graph (729 vertices).^{ [4] }

In enumerative combinatorics, there are 3^{n} signed subsets of a set of n elements. In polyhedral combinatorics, the hypercube and all other Hanner polytopes have a number of faces (not counting the empty set as a face) that is a power of three. For example, a 2-cube, or square, has 4 vertices, 4 edges and 1 face, and 4 + 4 + 1 = 3^{2}. Kalai's 3^{d} conjecture states that this is the minimum possible number of faces for a centrally symmetric polytope.^{ [5] }

In recreational mathematics and fractal geometry, inverse power-of-three lengths occur in the constructions leading to the Koch snowflake,^{ [6] } Cantor set,^{ [7] } Sierpinski carpet and Menger sponge, in the number of elements in the construction steps for a Sierpinski triangle, and in many formulas related to these sets. There are 3^{n} possible states in an n-disk Tower of Hanoi puzzle or vertices in its associated Hanoi graph.^{ [8] } In a balance puzzle with w weighing steps, there are 3^{w} possible outcomes (sequences where the scale tilts left or right or stays balanced); powers of three often arise in the solutions to these puzzles, and it has been suggested that (for similar reasons) the powers of three would make an ideal system of coins.^{ [9] }

In number theory, all powers of three are perfect totient numbers.^{ [10] } The sums of distinct powers of three form a Stanley sequence, the lexicographically smallest sequence that does not contain an arithmetic progression of three elements.^{ [11] } A conjecture of Paul Erdős states that this sequence contains no powers of two other than 1, 4, and 256.^{ [12] }

Graham's number, an enormous number arising from a proof in Ramsey theory, is (in the version popularized by Martin Gardner) a power of three. However, the actual publication of the proof by Ronald Graham used a different number.^{ [13] }

(sequence A000244 in the OEIS )

3^{0} | = | 1 | 3^{16} | = | 43046721 | 3^{32} | = | 1853020188851841 | 3^{48} | = | 79766443076872509863361 | ||||

3^{1} | = | 3 | 3^{17} | = | 129140163 | 3^{33} | = | 5559060566555523 | 3^{49} | = | 239299329230617529590083 | ||||

3^{2} | = | 9 | 3^{18} | = | 387,420,489 | 3^{34} | = | 16677181699666569 | 3^{50} | = | 717897987691852588770249 | ||||

3^{3} | = | 27 | 3^{19} | = | 1162261467 | 3^{35} | = | 50031545098999707 | 3^{51} | = | 2153693963075557766310747 | ||||

3^{4} | = | 81 | 3^{20} | = | 3486784401 | 3^{36} | = | 150094635296999121 | 3^{52} | = | 6461081889226673298932241 | ||||

3^{5} | = | 243 | 3^{21} | = | 10460353203 | 3^{37} | = | 450283905890997363 | 3^{53} | = | 19383245667680019896796723 | ||||

3^{6} | = | 729 | 3^{22} | = | 31381059609 | 3^{38} | = | 1350851717672992089 | 3^{54} | = | 58149737003040059690390169 | ||||

3^{7} | = | 2187 | 3^{23} | = | 94143178827 | 3^{39} | = | 4052555153018976267 | 3^{55} | = | 174449211009120179071170507 | ||||

3^{8} | = | 6561 | 3^{24} | = | 282429536481 | 3^{40} | = | 12157665459056928801 | 3^{56} | = | 523347633027360537213511521 | ||||

3^{9} | = | 19683 | 3^{25} | = | 847288609443 | 3^{41} | = | 36472996377170786403 | 3^{57} | = | 1570042899082081611640534563 | ||||

3^{10} | = | 59049 | 3^{26} | = | 2541865828329 | 3^{42} | = | 109418989131512359209 | 3^{58} | = | 4710128697246244834921603689 | ||||

3^{11} | = | 177147 | 3^{27} | = | 7625597484987 | 3^{43} | = | 328256967394537077627 | 3^{59} | = | 14130386091738734504764811067 | ||||

3^{12} | = | 531441 | 3^{28} | = | 22876792454961 | 3^{44} | = | 984770902183611232881 | 3^{60} | = | 42391158275216203514294433201 | ||||

3^{13} | = | 1594323 | 3^{29} | = | 68630377364883 | 3^{45} | = | 2954312706550833698643 | 3^{61} | = | 127173474825648610542883299603 | ||||

3^{14} | = | 4782969 | 3^{30} | = | 205891132094649 | 3^{46} | = | 8862938119652501095929 | 3^{62} | = | 381520424476945831628649898809 | ||||

3^{15} | = | 14348907 | 3^{31} | = | 617673396283947 | 3^{47} | = | 26588814358957503287787 | 3^{63} | = | 1144561273430837494885949696427 |

In graph theory, a **strongly regular graph** is defined as follows. Let *G* = be a regular graph with *v* vertices and degree *k*. *G* is said to be **strongly regular** if there are also integers λ and μ such that:

A **convex polytope** is a special case of a polytope, having the additional property that it is also a convex set contained in the -dimensional Euclidean space . Most texts use the term "polytope" for a bounded convex polytope, and the word "polyhedron" for the more general, possibly unbounded object. Others allow polytopes to be unbounded. The terms "bounded/unbounded convex polytope" will be used below whenever the boundedness is critical to the discussed issue. Yet other texts identify a convex polytope with its boundary.

In geometry, a set of lines is called **equiangular** if all the lines intersect at a single point, and every pair of lines makes the same angle.

In graph theory, the **Möbius ladder***M*_{n}, for even numbers n, is formed from an n-cycle by adding edges connecting opposite pairs of vertices in the cycle. It is a cubic circulant graph, so-named because (with the exception of *M*_{6}, *M*_{n} has exactly *n*/2 four-cycles which link together by their shared edges to form a topological Möbius strip. Möbius ladders were named and first studied by Guy and Harary .

**Hamming graphs** are a special class of graphs named after Richard Hamming and used in several branches of mathematics and computer science. Let *S* be a set of *q* elements and *d* a positive integer. The Hamming graph *H*(*d*,*q*) has vertex set *S ^{d}*, the set of ordered

In mathematics, the **permutohedron** of order *n* is an (*n* − 1)-dimensional polytope embedded in an *n*-dimensional space. Its vertex coordinates (labels) are the permutations of the first *n* natural numbers. The edges identify the shortest possible paths that connect two vertices (permutations). Two permutations connected by an edge differ in only two places, and the numbers on these places are neighbors.

**Algebraic combinatorics** is an area of mathematics that employs methods of abstract algebra, notably group theory and representation theory, in various combinatorial contexts and, conversely, applies combinatorial techniques to problems in algebra.

**Polyhedral combinatorics** is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher-dimensional convex polytopes.

In mathematics, an **associahedron***K*_{n} is an (*n* − 2)-dimensional convex polytope in which each vertex corresponds to a way of correctly inserting opening and closing parentheses in a word of *n* letters and the edges correspond to single application of the associativity rule. Equivalently, the vertices of an associahedron correspond to the triangulations of a regular polygon with *n* + 1 sides and the edges correspond to edge flips in which a single diagonal is removed from a triangulation and replaced by a different diagonal. Associahedra are also called **Stasheff polytopes** after the work of Jim Stasheff, who rediscovered them in the early 1960s after earlier work on them by Dov Tamari.

In polyhedral combinatorics, a branch of mathematics, **Steinitz's theorem** is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs. That is, every convex polyhedron forms a 3-connected planar graph, and every 3-connected planar graph can be represented as the graph of a convex polyhedron. For this reason, the 3-connected planar graphs are also known as polyhedral graphs.

The **Gosset graph**, named after Thorold Gosset, is a specific regular graph (1-skeleton of the 7-dimensional 3_{21} polytope) with 56 vertices and valency 27.

In the mathematical field of graph theory, the **Brouwer–Haemers graph** is a 20-regular undirected graph with 81 vertices and 810 edges. It is a strongly regular graph, a distance-transitive graph, and a Ramanujan graph. Although its construction is folklore, it was named after Andries Brouwer and Willem H. Haemers, who proved its uniqueness as a strongly regular graph.

In geometry, the **moment curve** is an algebraic curve in *d*-dimensional Euclidean space given by the set of points with Cartesian coordinates of the form

In combinatorial mathematics, an **Apollonian network** is an undirected graph formed by a process of recursively subdividing a triangle into three smaller triangles. Apollonian networks may equivalently be defined as the planar 3-trees, the maximal planar chordal graphs, the uniquely 4-colorable planar graphs, and the graphs of stacked polytopes. They are named after Apollonius of Perga, who studied a related circle-packing construction.

In graph theory, the **halved cube graph** or **half cube graph** of dimension *n* is the graph of the demihypercube, formed by connecting pairs of vertices at distance exactly two from each other in the hypercube graph. That is, it is the half-square of the hypercube. This connectivity pattern produces two isomorphic graphs, disconnected from each other, each of which is the halved cube graph.

In geometry, a **Hanner polytope** is a convex polytope constructed recursively by Cartesian product and polar dual operations. Hanner polytopes are named after Olof Hanner, who introduced them in 1956.

In graph theory, a **locally linear graph** is an undirected graph in which every edge belongs to exactly one triangle. Equivalently, for each vertex of the graph, its neighbors are each adjacent to exactly one other neighbor, so the neighbors can be paired up into an induced matching. Locally linear graphs have also been called locally matched graphs.

In graph theory, **Conway's 99-graph problem** is an unsolved problem asking whether there exists an undirected graph with 99 vertices, in which each two adjacent vertices have exactly one common neighbor, and in which each two non-adjacent vertices have exactly two common neighbors. Equivalently, every edge should be part of a unique triangle and every non-adjacent pair should be one of the two diagonals of a unique 4-cycle. John Horton Conway offered a $1000 prize for its solution.

In graph theory, the **Berlekamp–Van Lint–Seidel graph** is a locally linear strongly regular graph with parameters . This means that it has 243 vertices, 22 edges per vertex, exactly one shared neighbor per pair of adjacent vertices, and exactly two shared neighbors per pair of non-adjacent vertices. It was constructed by Elwyn Berlekamp, J. H. van Lint, and Johan Jacob Seidel as the coset graph of the ternary Golay code.

In graph theory, the **Games graph** is the largest known locally linear strongly regular graph. Its parameters as a strongly regular graph are (729,112,1,20). This means that it has 729 vertices, and 40824 edges. Each edge is in a unique triangle and each non-adjacent pair of vertices have exactly 20 shared neighbors. It is named after Richard A. Games, who suggested its construction in an unpublished communication and wrote about related constructions.

- ↑ Ranucci, Ernest R. (December 1968), "Tantalizing ternary",
*The Arithmetic Teacher*,**15**(8): 718–722, doi:10.5951/AT.15.8.0718, JSTOR 41185884 - ↑ Moon, J. W.; Moser, L. (1965), "On cliques in graphs",
*Israel Journal of Mathematics*,**3**: 23–28, doi: 10.1007/BF02760024 , MR 0182577, S2CID 9855414 - ↑ Tomita, Etsuji; Tanaka, Akira; Takahashi, Haruhisa (2006), "The worst-case time complexity for generating all maximal cliques and computational experiments",
*Theoretical Computer Science*,**363**(1): 28–42, doi: 10.1016/j.tcs.2006.06.015 - ↑ For the Brouwer–Haemers and Games graphs, see Bondarenko, Andriy V.; Radchenko, Danylo V. (2013), "On a family of strongly regular graphs with ",
*Journal of Combinatorial Theory*, Series B,**103**(4): 521–531, arXiv: 1201.0383 , doi: 10.1016/j.jctb.2013.05.005 , MR 3071380 . For the Berlekamp–van Lint–Seidel and Games graphs, see van Lint, J. H.; Brouwer, A. E. (1984), "Strongly regular graphs and partial geometries" (PDF), in Jackson, David M.; Vanstone, Scott A. (eds.),*Enumeration and Design: Papers from the conference on combinatorics held at the University of Waterloo, Waterloo, Ont., June 14–July 2, 1982*, London: Academic Press, pp. 85–122, MR 0782310 - ↑ Kalai, Gil (1989), "The number of faces of centrally-symmetric polytopes",
*Graphs and Combinatorics*,**5**(1): 389–391, doi:10.1007/BF01788696, MR 1554357, S2CID 8917264 - ↑ von Koch, Helge (1904), "Sur une courbe continue sans tangente, obtenue par une construction géométrique élémentaire",
*Arkiv för Matematik*(in French),**1**: 681–704, JFM 35.0387.02 - ↑ See, e.g., Mihăilă, Ioana (2004), "The rationals of the Cantor set",
*The College Mathematics Journal*,**35**(4): 251–255, doi:10.2307/4146907, JSTOR 4146907, MR 2076132 - ↑ Hinz, Andreas M.; Klavžar, Sandi; Milutinović, Uroš; Petr, Ciril (2013), "2.3 Hanoi graphs",
*The tower of Hanoi—myths and maths*, Basel: Birkhäuser, pp. 120–134, doi:10.1007/978-3-0348-0237-6, ISBN 978-3-0348-0236-9, MR 3026271 - ↑ Telser, L. G. (October 1995), "Optimal denominations for coins and currency",
*Economics Letters*,**49**(4): 425–427, doi:10.1016/0165-1765(95)00691-8 - ↑ Iannucci, Douglas E.; Deng, Moujie; Cohen, Graeme L. (2003), "On perfect totient numbers",
*Journal of Integer Sequences*,**6**(4), Article 03.4.5, Bibcode:2003JIntS...6...45I, MR 2051959 - ↑ Sloane, N. J. A. (ed.), "SequenceA005836",
*The On-Line Encyclopedia of Integer Sequences*, OEIS Foundation - ↑ Gupta, Hansraj (1978), "Powers of 2 and sums of distinct powers of 3",
*Univerzitet u Beogradu Publikacije Elektrotehničkog Fakulteta, Serija Matematika i Fizika*(602–633): 151–158 (1979), MR 0580438 - ↑ Gardner, Martin (November 1977), "In which joining sets of points leads into diverse (and diverting) paths",
*Scientific American*,**237**(5): 18–28, doi:10.1038/scientificamerican1177-18

This page is based on this Wikipedia article

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.