Un hypercube (n-dimensional cube) graph este un graf care are un nod pentru fiecare string binar de lungime n. Doua varfuri sunt adiacente daca cele doua numere difera printr-un singur bit. (2^n varfuri, n * 2^(n-1) muchii)
Doua muchii sunt independente daca nu au nici un varf in comun si nu exista nici un patrat (ciclu de lungime 4) care le contine pe ambele.
Care este numarul maxim de muchii independente doua cate doua (un upper/lower bound maybe)? (adica, cat de mare poate fi un set S de muchii astfel incat oricare doua muchii din S sunt independente).
Any thoughts?
Numarul maxim de muchii independente doua cate doua e mult mai mare decat credeam
.
Un lower bound de O(2^(n-1)) e aproape evident (construiesti un graf G care are un varf pentru fiecare muchie; doua varfuri sunt adiacente in G daca cele doua muchii nu sunt independente; G are n*2^(n-1) varfuri si fiecare varf are 3(n-1) vecini, deci are un independent set >= n*2^(n-1)/(3*(n-1))).
Initial am crezut ca numarul maxim de muchii independente doua cate doua e polinomial in n (problema nu e foarte interesanta daca numarul de muchii e exponential).
Anyway.. nevermind.
Cu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena