General Information
| Student: | Josef Matějka |
|---|---|
| Office: | CoRE 434 |
| School: | Faculty of Mathematics and Physics, Charles University |
| Contact: | josef.matejka@rutgers.edu |
| Project: | Optimal Steiner trees for regular simplices |
| Mentor: | Karthik Srikanta |
| Collaborators: | G.A. Gamboa Quintero and Jakub Petr |
I am part of a group of students from Charles University that includes Ondrej Chwiedziuk, Tomas Cizek, Barbora Dohnalova, Jiri Kalvoda, Kyrylo Karlov, Volodymyr Kuznietsov, Gaurav Kucheriya, G.A. Gamboa Quintero, Jakub Petr and Ondrej Sladky.
Project Description
For a given finite set of points in a metric space find a network which connects all points of the set with minimal length. Such a network must be a tree, which is called a Steiner Tree and it may contain vertices other than the points which are to be connected. Such points are called Steiner points. It is open to find (and prove) the minimum cost Steiner tree even for highly structured point-sets, such as when the input points form a regular simplex. We will try to address this question.
Research Log
Week 1 (05/06-09/06)
I started by getting familiar with the notions, terminology and main results involving our topic of research, as well as preparing a presentation introducing the project to the whole REU2023 group. I also met with my supervisor to establish a work plan and determine which notions are the most important for me to focus on and understand.
- Monday: Presentation and working on alternative proofs to properties 3.x in [1] Gilbert, E.N. and Pollak, H.O., 1968. Steiner minimal trees. SIAM Journal on Applied Mathematics, 16(1), pp.1-29.
- Tuesday: Consultation with my mentor and looking into properties 8.x in [1].
- Wednesday: Reading on properties 8.x in [1].
- Thursday: Meeting with the mentor, we have showed first batch of prooves of properties 8.x in [1], also stated the generalization of property 8.4 to dimension three (possibly more).
- Friday: Working on a generalization of property 8.4 from [1].
Week 2 (12/06-16/06)
This week I decided to attend the Workshop on Modern Techniques in Graph Algorithms, therefore I focus a bit less on the research. The workshop was helpful, I have seen the recent results from the graph algorithm - the paper and techniques were inspiring. We also had two meetings with the mentor, we received recommended reading and some ideas how we can proceed with the project.
- Monday: Meeting with our mentor, we showed our conjecure and tlked about it. Rest of the day was spent on the workshop.
- Tuesday: Spent most of the time on the woorkshop. In the evening I was reading the paper [2] Smith, Warren D. "How to find Steiner minimal trees in Euclidean d-space." Algorithmica 7 (1992): 137-177. recommended by my mentor.
- Wednesday: Workshop attendance.
- Thursday: Meeting with the mentor, going through [2].
- Friday: Public holiday Juneteenth.
Week 3 (19/06-23/06)
After the long weekend we got right back into the research. After we realized how small is the knowledge about Steiner trees in Euclidean d-space we started listing all the way we could improve this knowledge. We had stated few conjectures we wish to prove this (or next week).
- Monday: Thinking about Steiner points that are connected to only one terminal. From our experiments it seems that there can be at most one such Steiner point in an optimal Steiner tree topology.
- Tuesday: Meeting with the mentor in NYC, thinking about the "flow of Steiner points coordinates".
- Wednesday: Working on the flow again, we also found better way to state the conjecture.
- Thursday: Meeting with our mentor, we have talked about APTC (all pairwise terminal cost) as property that could be important for topologies.
- Friday: Working on proving that conjectured topology has the best APTC.
Week 4 (26/06-30/06)
We went over the results for regular simplexes with terminals ranging from 3 to 12, we focused on change in coordinates of existing steiner points after one terminal is added. We have conjectured and later proved how Steiner point behave after doubling the number of terminals. We also had another look at APTC measure.
- Monday: Checking the change in coordinates after doubling the number of terminals. Thinking about ways how can be APTC lowered by moving two terminals.
- Tuesday: Continuing our research and presenting the results to our mentor. We have been given another pointers and things to look at.
- Wednesday: Continuing with APTC.
- Thursday: Discussing proofs for APTC non-generalized version.
- Friday: We had meeting with our mentors. We discussed our progress.
Week 5 (03/07-07/07)
We went over the results for regular simplexes with terminals ranging from 3 to 12, we focused on change in coordinates of existing steiner points after one terminal is added. We have conjectured and later proved how Steiner point behave after doubling the number of terminals. We also had another look at APTC measure.
- Monday: Discussing proofs for APTC with colleagues.
- Tuesday: Celebrating 4th of July. Very nice!
- Wednesday: Continuing with APTC.
- Thursday: Meeting with our mentor, we want over the APTC reduction scheme and hopefully fix all the proofs.
- Friday: Putting all our results from APTC reduction to Latex.
Week 6 (10/07-14/07)
We focused on showing optimality of cnjectured topology in terms of APTC. Also we started to give more attention to our notes in Latex, we started going over them and fixing them.
- Monday: Meeting with our mentor, who suggested to wrap our findings.
- Tuesday: Looking into length of oprhaned interval, lower bound.
- Wednesday: Thinking about the length of binary tree expression in [1], we want to show that our construction is better than theirs.
- Thursday: Field trip to IBM reasearch.
- Friday: We want to find upper bound for either core or for the legth of oprhan terminals.
Acknowledgements
This work was carried out while the author Josef Matějka was a participant in the 2023 DIMACS REU program, supported by CoSP, a project funded by European Union’s Horizon 2020 research and innovation programme, grant agreement No. 823748.