Ilona Palásti

Ilona Palásti (1924–1991) was a Hungarian mathematician who worked at the Alfréd Rényi Institute of Mathematics. She is known for her research in discrete geometry, geometric probability, and the theory of random graphs.^[1] With Alfréd Rényi and others, she was considered to be one of the members of the Hungarian School of Probability.^[2]

In connection to the Erdős distinct distances problem, Palásti studied the existence of point sets for which the ${\displaystyle i}$th least frequent distance occurs ${\displaystyle i}$ times. That is, in such points there is one distance that occurs only once, another distance that occurs exactly two times, a third distance that occurs exactly three times, etc. For instance, three points with this structure must form an isosceles triangle. Any ${\displaystyle n}$ evenly-spaced points on a line or circular arc also have the same property, but Paul Erdős asked whether this is possible for points in general position (no three on a line, and no four on a circle). Palásti found an eight-point set with this property, and showed that for any number of points between three and eight (inclusive) there is a subset of the hexagonal lattice with this property. Palásti's eight-point example remains the largest known.^[3][4][E]

Another of Palásti's results in discrete geometry concerns the number of triangular faces in an arrangement of lines. When no three lines may cross at a single point, she and Zoltán Füredi found sets of ${\displaystyle n}$ lines, subsets of the diagonals of a regular ${\displaystyle 2n}$-gon, having ${\displaystyle n(n-3)/3}$ triangles. This remains the best lower bound known for this problem, and differs from the upper bound by only ${\displaystyle O(n)}$ triangles.^[3][D]

In geometric probability, Palásti is known for her conjecture on random sequential adsorption, also known in the one-dimensional case as "the parking problem". In this problem, one places non-overlapping balls within a given region, one at a time with random locations, until no more can be placed. Palásti conjectured that the average packing density in ${\displaystyle d}$-dimensional space could be computed as the ${\displaystyle d}$th power of the one-dimensional density.^[5] Although her conjecture led to subsequent research in the same area, it has been shown to be inconsistent with the actual average packing density in dimensions two through four.^[6][A]

Palásti's results in the theory of random graphs include bounds on the probability that a random graph has a Hamiltonian circuit, and on the probability that a random directed graph is strongly connected.^[7][B][C]