Znajdź krawędzie w Hypergraph

Question

Mam 8 wierzchołków. Muszę tworzyć hyperedges taki sposób, że każda krawędź powinna zawierać dokładnie 4 wierzchołki i każda krawędź powinna przecinają się z każdym innym krawędzi na dokładnie 2 wierzchołki. Ile jest krawędzi (maksymalnie)? Wierzę, że odpowiedź brzmi 7, ale jak? Otrzymałem odpowiedź, wypisując możliwe kombinacje. Czy istnieje podejście algorytmiczne? Muszę znaleźć uogólnione podejście do tego. Każda pomoc byłaby bardzo mile widziana. Dziękuję Ci

Maksymalna liczba krawędzi na wykresie

Answer 1

Rzeczywiście maksimum $7$.

Górna granica

Z każdą krawędzią $e$ kojarzymy $8$ triples ($3$-zestawy elementów) wierzchołków, a mianowicie $4$ trójki zawarte w $e$ i $4$ trójki rozłączone z $e$. Żadna trójka nie jest skojarzona z dwoma różnymi krawędziami; wynika to z faktu, że krawędzie przecinają się dokładnie w dwóch wierzchołkach. Jeśli mamy$n$ krawędzie to mamy $8n$wyraźne trójki wierzchołków. Ponieważ są tylko$8$ wierzchołki, wynika z tego $\8n\le\binom83$tj. $n\le\binom83/8=7$.

Dolna granica

W rzeczywistości na zestawie tylko $7$ punktów, możemy rodzina $7$ $4$-ustawia tak, że dowolne dwa z nich przecinają się dokładnie w dwóch punktach. Zwróć uwagę, że uzupełnienia$4$-zestawy są $3$-zestawy i dwa $4$-sets przecinają się w dokładnie dwóch punktach wtedy i tylko wtedy, gdy ich dopełnienia przecinają się dokładnie w jednym punkcie. Zatem równoważnym problemem jest znalezienie systemu$7$ trzykrotnie $7$punkty takie, że dowolne dwie trójki przecinają się dokładnie w jednym punkcie. To jest dobrze znana konstrukcja; spójrz w górę System potrójny Steiner lub samolot Fano .