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. With Alfréd Rényi and others, she was considered to be one of the members of the Hungarian School of Probability.

Contributions

In connection to the Erdős distinct distances problem, Palásti studied the existence of point sets for which the $i$th least frequent distance occurs $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 $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.^[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 $n$ lines, subsets of the diagonals of a regular $2n$-gon, having $n(n-3)/3$ triangles. This remains the best lower bound known for this problem, and differs from the upper bound by only $O(n)$ triangles.^[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 $d$-dimensional space could be computed as the $d$th power of the one-dimensional density. 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.^[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.^[B][C]

Selected publications

A.

Palásti, Ilona (1960), "On some random space filling problems", Magyar Tud. Akad. Mat. Kutató Int. Közl., 5: 353–360, MR 0146947

B.

Palásti, I. (1966), "On the strong connectedness of directed random graphs", Studia Scientiarum Mathematicarum Hungarica, 1: 205–214, MR 0207588

C.

Palásti, I. (1971), "On Hamilton-cycles of random graphs", Period. Math. Hungar., 1 (2): 107–112, doi:10.1007/BF02029168, MR 0285437, S2CID 122925690

D.

Füredi, Z.; Palásti, I. (1984), "Arrangements of lines with a large number of triangles", Proceedings of the American Mathematical Society, 92 (4): 561–566, doi:10.2307/2045427, JSTOR 2045427, MR 0760946

E.

Palásti, I. (1989), "Lattice-point examples for a question of Erdős", Period. Math. Hungar., 20 (3): 231–235, doi:10.1007/BF01848126, MR 1028960, S2CID 123415960