Limites para o número de Carathéodory em Grafos de Hamming

Do teorema de Carathéodory surge a definição do número de Carathéodory para grafos. Determinar se um grafo G admite um conjunto de Carathéodory de cardinalidade k na convexidade P3 é um problema NP-completo. No entanto, para determinadas classes de grafos, é possível obter algoritmos polinomiais e estabelecer limites justos. Motivados por esses avanços, neste trabalho estabelecemos um limite inferior para o número de Carathéodory na classe dos grafos de Hamming de dimensão n, provando que esse valor é no mínimo n.