Description
Két, azonos csúcshalmazon definiált, $G_1$ és $G_2$ gráf szimmetrikus differenciája az a gráf, melynek csúcshalmaza megegyezik a $G_1$ és $G_2$ gráfok csúcshalmazával, és amelynek éleit azok a csúcspárok alkotják, melyek a $G_1$ és $G_2$ gráfok pontosan egyikében szomszédosak.
Érdekes megvizsgálni, hogy egy $n$ méretű közös csúcshalmazon legfeljebb mennyi gráf adható úgy, hogy közülük bármely kettő szimmetrikus differenciája kielégítsen valamilyen előírt feltételt.
Ha például azt a feltételt választjuk, hogy ez a differencia legalább $d$ élet tartalmazzon, akkor visszakapjuk a klasszikus kódelméleti kérdést: Legfeljebb mennyi $m$ hosszú bináris kód adható úgy, hogy közülük bármely kettő legalább $d$ helyen különbözzön?
Meggondolható, hogy $m = \binom{n}{2}$ választással ez tényleg ugyanaz a probléma, ha a bináris kódokra úgy tekintünk, mint az $n$ csúcsú gráfok élhalmazait leíró karakterisztikus vektorokra.
Azonban vizsgálhatunk általánosabb tulajdonságokat is, mint például az összefüggőséget vagy azt, hogy an-e Hamilton-út a gráfban vagy akár egy-egy rögzített részgráf tartalmazását is.
Ebben az előadásban néhány eredményt szeretnék ismertetni egy erről a problémakörről szóló cikkünkből, melynek társszerzői Alon, Körner, Milojević és Simonyi.