Gráfok maximális matroidjai

Témavezető:	Jordán Tibor
	ELTE TTK, Operációkutatási Tsz.
email:	tibor.jordan@ttk.elte.hu

Projekt leírás

Adottak G és H gráfok, H maximális matroidja G-ben az az M matroid, aminek alaphalmaza G élhalmaza és igaz rá, hogy:

1. G-nek minden H-val izomorf részgráfja kör M-ben és
2. Ha N egy olyan matroid, amire (1) igaz, akkor minden független halmaz N-ben M-ben is független.

Érdekes kérdések:

• Milyen H-kra (és G-kre) létezik ilyen matroid?
• Adott M esetén meg tudjuk-e határozni H-t?
• Mit tudunk mondani, ha H és G hipergráfok?

Célom a már meglévő eredmények megismerése a témában, illetve a nyitott kérdések vizsgálata.

Korábbi hallgatók

• Biskopics Boglárka: Gráfok maximális matroidjai (2020/21 II. félév Egyéni Kutatómunka 1)