Temukan tepinya di Hypergraph

Question

Saya memiliki 8 simpul. Saya perlu membentuk hyperedges sedemikian rupa sehingga setiap sisi harus berisi tepat 4 simpul dan setiap sisi harus berpotongan dengan setiap sisi lainnya tepat pada 2 simpul. Berapa banyak tepi yang ada (maksimum)? Saya yakin jawabannya adalah 7, tapi bagaimana caranya ?. Saya mendapat jawabannya dengan mendaftar kemungkinan kombinasi. Apakah ada pendekatan algoritmik? Saya perlu menemukan pendekatan umum untuk ini. Bantuan apa pun akan sangat dihargai. Terima kasih

Jumlah maksimum tepi pada grafik

Answer 1

Maksimal memang $7$.

Batas atas

Dengan setiap sisi $e$ kami berasosiasi $8$ tiga kali lipat ($3$-element set) dari simpul, yaitu, $4$ tiga kali lipat terkandung dalam $e$ dan $4$ tiga kali lipat terputus dari $e$. Tidak ada triple yang diasosiasikan dengan dua sisi yang berbeda; ini mengikuti dari fakta bahwa ujung-ujungnya berpotongan tepat di dua simpul. Jika kita punya$n$ tepi maka kita punya $8n$tiga kali lipat simpul yang berbeda. Karena hanya ada$8$ simpul, itu mengikuti itu $\8n\le\binom83$, yaitu, $n\le\binom83/8=7$.

Batas bawah

Bahkan, di satu set yang adil $7$ poin, kita bisa keluarga keluarga $7$ $4$-set sehingga salah satu dari keduanya berpotongan tepat di dua titik. Perhatikan bahwa pelengkap dari$4$-set adalah $3$-set, dan dua $4$-set berpotongan tepat di dua titik jika dan hanya jika komplemennya berpotongan tepat di satu titik. Jadi, masalah yang setara adalah menemukan sistem$7$ tiga kali lipat $7$titik sedemikian rupa sehingga dua tripel berpotongan tepat di satu titik. Ini adalah konstruksi yang terkenal; cari sistem triple Steiner atau pesawat Fano .