Hajnal Péter: Ponthalmazok felezõegyeneseinek számáról

Legyen S egy ponthalmaz a síkon. Az egyszerûség kedvéért tegyük fel, hogy általános helyzetûek és S elemszáma páros. Egy egyenes felezõegyenes, ha nem halad át pontjaink egyikén sem és mindkét oldalára ugyanannyi pont kerül. Két felezõ egyenest nem különböztetünk meg, ha a két ``fél-fél ponthalmaz'' halmazpárként nem különbözik. Hány felezõegyenes van? Az értelmes kérdés, maximum hány felezõ egyenes van. A kérdés távolról sincs megoldva, de nem olyan rég lényeges elõrelépések születtek. A mostani legjobb becslés O(n^{4/3}), de konstrukció csak közel lineáris létezik.

Minden erdeklõdõt szeretettel várunk,

Péter