De Erdös-Sós Conjecture

Erdös-Sós Conjecture:

Zij G = (V,E) een graaf. Als #E > (k-2)#V/2 dan geldt dat G iedere boom van orde k bevat.

Dit betekent dat als je een graaf G hebt die aan de eis voldoet dan bestaat er voor iedere boom van orde k een inbedding in G. We gaan er vanuit dat G een simpele graaf is.

Dit probleem kan vanuit twee kanten bekeken worden. In het begin is het namelijk handig om naar speciale gevallen te kijken. Er kan gekeken worden naar situaties waar beperkingen gelden voor de graaf G of gevallen waar beperkingen gelden voor de boom.

Een vergelijkbaar probleem is de Sumner's Universal Tournament Conjecture. Dit probleem gaat over volledige grafen waarin iedere kant een richting heeft meegekregen. De conjecture zegt het volgende:

Zij G volledige gerichte graaf van orde 2k-2, dan bevat G iedere gerichte boom van orde k.

In eerste instantie is er naar dit probleem gekeken, maar hier zijn minder resultaten over te vinden. Daarom is er voor gekozen om deze site alleen te wijden aan de Erdös-Sós Conjecture. Er is een poging gedaan om een overzicht te krijgen van de resultaten die tot nu toe geboekt zijn.

Om de artikelen over dit probleem beter te begrijpen is het aan te raden om eerst de definities te bekijken.

Dit probleem, de Erdös-Sós Conjecture, is gevonden op: AllTreesSubgraphs .