General Information

---

Project Description

Steiner Tree Problem is a well-known planar problem, posed first in the 19th century. It states: given n points in a plane, what is the shortest tree connecting these points, when we can add new points, called Steiner points. Very little about this problem is known in higher dimensions, though. The simplest object to study in n-dimensional space is the regular simplex. The best results known come from [2]. We hope to improve on them.

Research Log

Week 0 (1/6-2/6)

We met our supervisor via Zoom and met his co-worker Henry Fleischmann in person. We were given a first push for what we should think about, so we started to go through the papers.

Week 1 (5/6-9/6)

We introduced our project to the whole REU23 group, see presentation. We went through some useful properties of the Steiner trees in a plane (see [1]) and tried to generalize them in higher dimensions.

Week 2 (12/6-15/6)

For the first time, we met our supervisor in person. The meeting was wonderful and the conclusion was:

Good news: We managed to generalize a property that seems useful for upper or lower bounds on the length of the Steiner tree! And it holds in every dimension greater than or equal to 3!
Bad news: There already is an article (see [3]) providing a numerical algorithm for how to find Steiner points... we should have realized (or found it) sooner.
Good news: There is a lot of new information that we can go through.

In our team, we agreed that we did quite a lot during these two weeks (considering the fact that we also went to the Graph Algorithm Workshop this week, which was very inspiring - thanks DIMACS for organizing!). That made me feel a bit more relaxed and now I'm looking forward to the new obstacles in front of us. The Steiner Tree Problem is pretty difficult, but we've gained a lot of understanding.

Our next plan is to understand the algorithm given in [3]. We were also given a problem that we could tackle that is related but not the same. We'll see how things go.

Week 3 (19/6-24/6)

This week, we visited our mentor in New York and were discussing the problem all day long until not even coffee was able to wake us up. We didn't made that much of a progress; however, we discovered various new directions that we can explore.

For the most of the week, all three in our group focused on the Graph Theory direction - we wanted to find some nice characterization of the topology. We came up with a lot of conjectures, but the globality of the problem makes it hard to prove anything.
The problem is very fun since we seem to never run out of ideas about what we can try.

For next week, I think I will focus more on some other direction.

On Friday, I gave a presentation about the Czech language on the Culture Day.

Week 4 (26/6-30/6)

This week, a lot of interesting observations were made about the points in certain n-simplexes. We began trying to understand these patterns and we came up with an interesting inductive construction that may be useful for Steiner Trees in some high dimensions.
It may not necessarily give an optimal Steiner Tree, but it certainly gives a very good approximation.

The other branch of our research continued to try to prove that our conjectured topology has the minimal APTC among all possible "full" topologies for Steiner Trees. That is a very ambitious goal, but it doesn't seem out of reach. We have yet to find the correct approach.

Week 5 (3/7-7/7)

We discovered how the optimal Steiner Tree for n=5 explicitly looks (in the sense that the coordinates fit the numerical value in [3] very nicely) - the question remains "Why is it exactly this?". After more effort and implementing the approach in [2], we were able to compute the case n=7 as well.
This seems like a lot of progress, but at the same time it feels like we've just now caught up to [2]. However, we made a lot of interesting observations along the way that can hopefully be useful for the rest of our research.
The next obstacle is n=9 - do the Steiner points of the optimal Steiner Tree have an explicit closed formula? They cannot be computed using the tools in [2] and it may be possible that there is not a closed formula, according to [3].

We made quite a lot of progress in the graph theory approach. We (probably, it still needs a bit of polishing) found a way how to decrease the APTC. We hope that we can find a sequence of transformations of a given topology that will always lead us to the optimal topology - i.e. the conjectured topology.

Week 6 (10/7-14/7)

It's the penultimate week of my stay here - next Friday, we're flying to Prague. So we started putting everything together so that we can wrap things up nicely next week.
There has been small mistakes in our proofs all over the place, so this week we mainly tried to fill these gaps. We found a nicer way to prove that we can do switches to decrease the APTC to a lof of different topologies. Our conjectured one is (hopefully the only) one such that there exists no switch!
We began discussing possible ways to prove that the conjectured topology is APTC optimal. It looks like we found a nice proof for number of terminals that is a power of 2. For other n, we have interesting ideas, but none looks clean enough to call it a proof.

The Geometric branch of research was focused mainly on filling a small hole in one construction - we needed to say that the lines incident to terminals have lengths always at least 1/√3. That's a very bad approximation (the empirical data shows that the lengths are closer to √(2/3)), but it didn't seem obvious how to prove that.
Luckily, we found a way. It is probably much more difficult than it needs to be, but I personally felt very happy about this - we proved something non-trivial! It needs to be polished since there are a lot of steps along the way and every one of these needs to be formally written down - but that should not be much more work.

On Thursday, we visited IBM in the state of New York. It was interesting to see the quantum computers they have there. Unfortunately, we did not have too much time to look around, but I'm very glad I could visit such a unique place!

Week 7 (17/7-21/7)

In this week, we were able to complete our proof for the fact that our conjectured topology is the only optimal one in the notion of APTC. That was the last main topic we started this summer and so it is nice that we can wrap things up nicely!
However, we find only on Wednesday that this topic has already been studied in [4]. Good news is that our result agrees with theirs.

The main part was writing in LaTeX - we would like to send our research to a conference and, therefore, we would like to explain our results in a way that is understandable. It is very helpful for me to see how it is done, but it takes a lot of time.
On Thursday, we presented our results to the whole REU DIMACS 2023 group. On Friday, we flew back to Prague, where we will stay for another two weeks.

There is still a lot of writing in front of us, so that is what we should focus on during the two weeks to come. But since we're departing from DIMACS, I would like to thank Lazaros, Caleb and everyone at DIMACS and REU for a wonderful research experience. I hope there is a lot of similarily wonderful experience in our lives to come (either in research or not).

Week 8 (24/7-28/7)

Attending a series of lectures on Charles University lead by Jan Kynčl, Martin Balko, Jan Volec and David Sychrovský. Also finishing our writeup.

Week 9 (31/7-3/8)

Attending Midsummer Combinatorial Workshop.

Presentations

•   Introductory Presentation
•   Presentation about Czech Language
•   Final Presentation

References

• [1]  Gilbert, E. N., and H. O. Pollak. “Steiner Minimal Trees.” SIAM Journal on Applied Mathematics 16, no. 1 (1968): 1–29. JSTOR.
• [2]  Chung, F. R. K., and E. N. Gilbert. "Steiner Trees for the Regular Simplex." Bulletin of the Institute of Mathematics Academia Sinice, vol. 4, no. 2 (1976): 313-325. USCD Math Department
• [3]  Smith, W.D. "How to find Steiner minimal trees in euclideand-space." Algorithmica 7 (1992): 137–177. DOI
• [4]  L.A. Székely, Hua Wang, Taoyang Wu. "The sum of the distances between the leaves of a tree and the ‘semi-regular’ property." Discrete Mathematics, vol. 311, no. 13 (2011): 1197-1203. DOI

Acknowledgements

This work was carried out while the author Jakub Petr 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.