Potencia de tres

En teoría de grafos , las potencias de tres aparecen en la cota de Moon-Moser 3 ^{n /3} sobre el número de conjuntos independientes máximos de un grafo de n vértices ^{[ 2 ]} y en el análisis temporal del algoritmo de Bron-Kerbosch para encontrar estos conjuntos ^{[ 3 ]} . Varios grafos importantes fuertemente regulares también tienen un número de vértices que es una potencia de tres, incluyendo el grafo de Brouwer-Haemers (81 vértices), el grafo de Berlekamp-van Lint-Seidel (243 vértices) y el grafo de Games (729 vértices) ^{[ 4 ] .}

En combinatoria enumerativa , hay 3 ⁿ subconjuntos con signo de un conjunto de n elementos. En combinatoria poliédrica , el hipercubo y todos los demás politopos de Hanner tienen un número de caras (sin contar el conjunto vacío como cara) que es una potencia de tres. Por ejemplo, un 2-cubo , o cuadrado , tiene 4 vértices, 4 aristas y 1 cara, y 4 + 4 + 1 = 3 ² . La conjetura de Kalai ^sobre 3d afirma que este es el número mínimo posible de caras para un politopo con simetría central . ^{[ 5 ]}

En matemáticas recreativas y geometría fractal , las longitudes inversas a potencias de tres aparecen en las construcciones que conducen al copo de nieve de Koch , ^{[ 6 ]} el conjunto de Cantor , ^{[ 7 ]} la alfombra de Sierpinski y la esponja de Menger , en el número de elementos en los pasos de construcción para un triángulo de Sierpinski , y en muchas fórmulas relacionadas con estos conjuntos. Hay 3 ⁿ estados posibles en un rompecabezas de la Torre de Hanoi de n discos o vértices en su grafo de Hanoi asociado . ^{[ 8 ]} En un rompecabezas de balanza con w pasos de pesaje, hay 3 ^w resultados posibles (secuencias donde la balanza se inclina hacia la izquierda o hacia la derecha o permanece equilibrada); las potencias de tres a menudo aparecen en las soluciones de estos rompecabezas, y se ha sugerido que (por razones similares) las potencias de tres harían un sistema ideal de monedas . ^{[ 9 ]}

En teoría de números , todas las potencias de tres son números totientes perfectos . ^{[ 10 ]} Las sumas de distintas potencias de tres forman una secuencia de Stanley , la secuencia lexicográficamente más pequeña que no contiene una progresión aritmética de tres elementos. ^{[ 11 ]} Una conjetura de Paul Erdős afirma que esta secuencia no contiene ninguna potencia de dos aparte de 1, 4 y 256. ^{[ 12 ]}

El número de Graham , un número enorme que surge de una demostración en la teoría de Ramsey , es (en la versión popularizada por Martin Gardner ) una potencia de tres. Sin embargo, la publicación real de la demostración por Ronald Graham utilizó un número diferente que es una potencia de dos y mucho menor. ^{[ 13 ]}