YIHENG SU

What is the maximum number of edges u(n) that a unit distance graph (UDG) of n vertices can have, as asked by an unsolved problem of Paul Erdős? We address the problem of determining the maximum number of edges in a UDG of n vertices using computer search. We seek to demonstrate a computer algorithm to generate dense UDGs for vertex counts up to at least 100. Via beam search with an added visitation metric, our algorithm finds all known maximally dense UDGs up to isomorphism at the push of a button. In addition, for 15 < n, where u(n) is unknown, i) the algorithm finds all previously published densest UDGs up to isomorphism for 15 < n ≤ 30, ii) the rate of growth of u(n)/n remains similar for 30 < n. iii) we build a database of over 60 million UDGs found by our algorithm. The preprint of the paper is available on arXiv.

★Features:

• Designed a novel heuristic beam search algorithm to improved the maximum number of edges in unit distance graphs.
• Explored graph constructions from the Moser Lattice with heuristic generating rules like rotation, translation, and reflection.
• Used multiprocessor and GPU implementations to optimize the efficiency of the search algorithms.

★Skills: Python; Numpy, Matplotlib, Pandas, Scikit-learn, Multiprocessing.

Eigenmaps are important in analysis, geometry, and machine learning, particularly in nonlinear dimension reduction. This project investigates the relationship between eigen-coordinates of graph Laplacians and Chebyshev polynomials. We will consider constructing graph Laplacian operators on $[-1,1]$, $[-1,1]^2$, the sphere $S^2$, and the Sierpinski gasket. We also have explored these operators when the points are selected randomly with various distributions, such as uniform and Gaussian. We have developed algorithms capable of generating eigenmap plots for the aforementioned sample spaces. In our next step, we would also like to compare the eigen-coordinates of graph Laplacian operators constructed from those intervals with families of orthogonal polynomials, such as the Hermite polynomials and possibly exceptional orthogonal polynomials. The paper is available on the UConn REU website.

★Features:

• Studied eigenmaps of Laplacian matrices transforming high-dimensional data into graph representations.
• Use NumPy and Matplotlib to visualize the eigenmaps.
• Explored the properties of eigenmaps, including data distribution, manifold smoothness, and boundary conditions.
• Analyzed eigenmaps on structures including intervals, squares, torus, and the Sierpinski triangle, emphasizing their connections to orthogonal polynomials and optimal parameter choices.

★Skills: Python, MATLAB; NumPy.