Ha hat embert elhívunk egy buliba, akkor a matematika szabályai szerint lesz közöttük legalább három olyan, akik már ismerik egymást, vagy legalább három ember, akik még soha nem találkoztak egymással. A matematikusokat azonban régóta foglalkoztatja egy kérdés: hány embert kell meghívni ahhoz, hogy egy adott számú ember mind ismeri egymást, vagy mind ismeretlenek egymás számára?

A kérdés egy régóta fennálló probléma a kombinatorikában, vagyis a matematikának azon ágában, amely számba veszi, hogy egy objektumhalmaz milyen módon rendezhető el. Az optimális válasz megadása meglepően nehéz, és néhány egyszerű megoldást leszámítva nem is ismert. Ám egy négy matematikusból álló csapat most megtalálta az eddigi legjobb megoldást, ami az eddigi legjobb a korábbi, 1935-ben kitalált megoldásnál – írta meg a Nature.

A problémát először Frank Ramsey brit matematikus írta le 1930-ban. Elképzelni az alábbi módon lehet: adott R számú ember, akik összegyűlnek egy szobában. Mindegyikük ismerős vagy ismeretlen a többiek számára. Tegyük fel, hogy meg akarjuk találni azt a k méretű részhalmazt, amelynek tagjai vagy mind ismerősök, vagy mind idegenek egymásnak.

A kérdés, hogy adott k esetén mekkora a legkisebb R(k), ami garantálja ezen feltétel teljesülését?

Az régóta ismert, hogy egy 6 fős csoport legalább 3-3 barátot vagy idegent tartalmaz, és minden 18 fős csoportban legalább 4 barát vagy 4 idegen van. Az 5-ös szám esetében azonban már ismeretlen az R, illetve csak annyit tudni róla, hogy 43 és 48 között kell lennie.

Két magyar matematikus, Erdős Pál és Szekeres György 1935-ben bizonyították be, hogy az R(k) legfeljebb 4^k kell, hogy legyen. Ez a felső korlát viszont messze nem optimális, ugyanis 44 már 256, holott ha legalább 4 barátot vagy 4 idegent szeretnénk találni, akkor ahhoz a fentebb írtak szerint egy 18 fős csoport is elegendő.

100 éves matematikai hibára bukkantak a kutatók, jobb tévék és festékek készülhetnek

Az amerikai kutatók eredetileg a tudományos adatok jobb megjelenítésén dolgoztak, amikor váratlanül kiderült: Schrödinger és társai tévedtek.

A kutatókat azóta foglalkoztatja a kérdés, hogy a felső korlát lehet-e kisebb, mint az az Erdős–Szekeres-féle bizonyításból adódik. A matematika nyelvén: van-e olyan C^k, ahol a C kisebb, mint négy.

A szakemberek szerint már egy egészen apró csökkenés is javulást hozhat a képletbe, és a jelek szerint sikerült most rábukkanniuk egy ilyen számra. Ezek szerint a felső korlát a 3,9995^k számítással is megadható. Az eredmény nemcsak azért izgalmas, mert a matematikusok örülnek neki: változást hozhat a hálózatok tanulmányozásába is, amivel például a fertőző betegségek terjedését vizsgálják. Az erről szóló tanulmány az arXiv preprint szerveren olvasható el.

Ha máskor is tudni szeretne hasonló dolgokról, lájkolja a HVG Tech rovatának Facebook-oldalát.