General Information
| Student: | Seth Bartynski |
|---|---|
| Office: | CoRE 450 |
| School: | University of Pennsylvania |
| E-mail: |  |
| Project: | [NAME OF YOUR PROJECT] |
Project Description
To fill in.
Weekly Log
- Week 1:
- This week I read through some of the papers that Dr. Abello had given to me relating to the project. I also began preparing this website to record my progress. Finally, I created a presentation to outline and describe my project (see Presentations below for a PDF copy of the finished version of the presentation).
- Week 2:
This week I finished my presentation with some helpful comments from my advisor. I then gave my presentation on Monday morning, along with the other REU students. I also attended a pre-defense of one the Ph.D. students at Rutgers, whose talk relates to my project. After reading some more background papers, I met with Dr. Abello on Tuesday and discussed the direction for my project, as well as how research operates as a whole.
After the meeting, I researched the computation of "Venn diagrams" for a collection, or family, of sets. In other words, given a family of sets $ \mathcal{F} = \{ S_1, \dots, S_m \} $, for each non-empty $ \mathcal{J} \subseteq [1..m] $, find $$ \bigcap_{i \in \mathcal{J}} S_i $$ I found connections between this problem and concepts such as the intersection graph, the nerve of an open cover in a topological space, and the Principle of Inclusion-Exclusion, of course. However, I was unable to find any work related to the computation of all such intersections.
On Wednesday, in addition to continuing my search above, I attended a talk by Dr. Neil Sloane on the Online Encyclopedia of Integer Sequences, which I found to be very interesting. On Thursday, I met with Dr. Abello again and presented my results. We discussed the calculation of all intersections of a family of sets as described above, with my task for the next week to implement this process and begin experimenting with interesting families of sets. I met with one of the other students working with Dr. Abello, who introduced me to the code that they had written thus far. After the meeting, Dr. Abello gave me a list of claims relating to fixed points and the iterative edge decomposition of [1] to test out. I began exploring these claims to determine their validity.
I also finished this website!
- Week 3:
This week I finished investigating four of the claims that Dr. Abello had sent to me, after discussing them briefly over e-mail. I successfully found proofs for three of the claims, and provided a counterexample for the fourth claim. In particular, the fourth claim dealt with whether performing the iterative edge decomposition on the local neighborhood of a given vertex results in a layout resembling that of the iterative edge decomposition, when performed on the graph as a whole. Unfortunately, this claim is false, as I provided a counterexample, using one of the examples from [1].
I typed up all of these results and presented them to Dr. Abello at our meeting on Tuesday. He then tasked me with determining if there is a local property of the vertices of a network that would either allow the fourth claim to be true, or prevent it from being so. Per Dr. Abello's suggestion, I also began reading through a related paper [2] on computing $ k $-connected components in a graph, which Dr. Abello believes will tie in closely with the iterative edge decomposition in helping understand complex networks.
Also on Tuesday, I attended a talk by Dr. Sorelle Friedler on auditing black-box models, such as those output by complex machine learning algorithms. I found Dr. Friedler very engaging, as I agree that we should be employing machine learning algorithms whose outputs are easily interpreted by the designers. I continued working on the problems that Dr. Abello suggested in our previous meetings, and determind that the local property to determine the truthfulness of the fourth claim from above would be very hard to find, as the conditions for success and failure vary widely. Additionally, I found a counterexample for a claim that Dr. Abello had given me regarding the effect of contracting similar vertices in a regular graph on the peeling value.
On Thursday, I attended a talk on scientific writing given by Dr. Gallos. I found this talk to be very helpful, especially in the descriptions of the review process for academic writing. I also met with Dr. Abello again, and discussed the results for this week. He then gave me a few more claims to explore. Later that day and Friday, I managed to completely answer two of the claims, which dealt with combining fixed points by connecting a single vertex in one with a subset of the vertices in the other. I determined a set of necessary and sufficient conditions for when the resulting graph is indeed a fixed point, and typed up my findings to send to Dr. Abello.
- Week 4:
This week I continued working on the claims from the previous meeting, as well as the other, more general questions from earlier. On Tuesday, I attended a talk by Dr. David Pennock on Kelly betting (see, for example, this article on Wikipedia). I was really shocked by the stories that Dr. Pennock told us of Dr. Edward O. Thorp, who took Kelly's idea and used it to make money, both via gambling in Los Vegas and investing in the stock market as a hedge fund (Dr. Pennock recommends the book Fortune's Formula for more information on this topic, which I plan on reading).
As I continued to work on the claims from our meeting last Thursday, I realized that I had missed a special case for the claims I thought I had finished, thus meaning that one of the statements in those results is now false. Namely, the case that I had missed was when one of the fixed points is a single vertex. After realizing this, I provided a proof of the amended statement for all fixed points that are not isolated vertices, and began trying to determine what happens in this special case. I easily determined a sufficient condition, but was unable to determine a necessary condition.
On Wednesday, I met with Dr. Abello and discussed the results that I had found the previous week, as well as the issue in the proof that I discovered. We began trying to determine a necessary condition by making various claims about when the resulting graph is not a fixed point. However, in each case, I managed to constuct a counterexample that was a fixed point. Despite our many attempts, we were unable to find a true claim. Thus, we decided for the time being to leave the necessary condition for our claim as an open problem.
We also discussed some of the progress I had made on the other claims from last week. Specifically, I had found a counterexample for a claim involving the way in which vertices appear in different layers of the iterative edge decomposition. In addition, I had found a potential connection between this appearance pattern and the original peel value of the vertex in the graph, but believe that this is simply an artifact of the particular graph I was examining, and conjectured some possible counterexamples to show this connection does not hold in all cases. Finally, we clarified some issues I had with one of the over-arching problems, which I began to explore by looking at small examples.
- Week 5:
This week, I continued looking at the small examples from the previous week, as well as the paper on finding $ k $-vertex connected components in graphs. I began considering how this algorithm could be used on the fixed points found in each layer of the iterative edge decomposition. On Tuesday, I met with Dr. Abello and discussed my progress on these issues, as well as some of the results on the claims that I had found last week. During this meeting, Dr. Abello introduced an important problem to study for the remainder of the program, which involved relating the $ k $-connectivity of a fixed point with the $ k $-connectivity of a related structure that he defined during our meeting.
During this meeting, Dr. Abello also introduced an interesting problem that occupied me for most of the rest of the week. Specifically, it dealt with how to deal with vertices of degree two, which impact the peeling value of a graph without adding much topological significance. For example, consider the complete graph on five vertices, $ K_5 $. Next, consider the graph formed from $ K_5 $ by "inserting" a new vertex in the middle of each edge. This process is known as subdivison and results in a graph that is homeomorphic to $ K_5 $. Although the two graphs are homeomorphic, they have vastly different peeling values. The peeling value of $ K_5 $ is five, whereas the peeling value of this new graph is two. For this reason, we seek to be able to remove these vertices, so that we can study the underlying structure instead. Dr. Abello suggested a process for removing these vertices, which I then investigated throughout the week.
After playing around with this process, I determined that it did work as intended, and that all biconnected, fixed points of degree peeling two to which this process cannot be applied must be cycles, which are homeomorphic to triangles. Additionally, I considered efficient algorithms for implementing this process in graphs. On Thursday, I met with Dr. Abello and explained my results and algorithms to him. During the meeting, we discussed potential methods for generalizing this process to deal with fixed points of degree peeling three or more.
On Friday, we took a trip to the IBM Thomas J. Watson Research Center, where we got a tour of the IBM ThinkLab, learned about Watson playing Jeopardy, and learned about quantum computing at IBM. I found the quantum computing research to be especially engaging, especially since IBM now has a cloud-based platform where users can "compose" quantum programs, and have them run on one of IBM's actual quantum computers! We also had the opportunity to hear some of the researchers at IBM discuss their projects and life at IBM.
- Week 6:
Over the weekend, Dr. Abello e-mailed me, suggesting a new process for dealing with the vertices of degree identified previously. However, I was concerned that this new process was not the same as the previous process, and that this new process can result in modifying graphs in undesirable manners. I managed to come up with an example of these concerns by showing that a graph homeomorphic to $ K_4 $ is tranformed into a triangle under this new process, while the old process transforms this graph into $ K_4 $, as desired. During our meeting on Monday, we discussed my example and why the new process fails where the old process succeeded.
We managed to come up with a slight modification to the new process that we believed behaved similarly to the old process. Dr. Abello then asked me to explore this new process, in order to determine its similarity to the previous process. Over the next two days, I managed to come up with a proof, similar to the one for the old process, wherein I showed that any biconnected, fixed point of degree peeling two to which this new process cannot be applied must be a triangle. I also figured out that one can add specific subgraph structures to an existing graph, without affecting the graph output by this process.
On Wednesday, I attended a talk by current Ph.D. student Caroline Trippel on memory consistency models. I was intrigued by the amount to which compilers can reorganize the execution order of commands, as well as the bugs that result from this reordering process when multiple processors are present. Later on Wednesday, I met with Dr. Abello again, where we discussed my results on the new process. Dr. Abello asked me to formalize some of my results, as well as to see if I could generalize this process to vertices of higher degree.
On Thursday, we had our group photo (link to be added later). I continued working on generalizing the new process, and determined that this proess has some undesirable results when looking at vertices with degree higher than three, as it has the potential to lower the peeling value. I also typed up a few of the results about the new process. On Friday, I attended a graduate student panel, which I found to be very helpful and informative, especially the discussions on choosing reference writers, finding a mentor, and determining funding. Later on Friday, I met with Dr. Abello for the last time, as he is going to be traveling for the remainder of the program. We discussed my results on the failure of the new process. Based on this, we determined a plan for the rest of the summer, with two main points of inquiry: namely, looking at the $ k $-connectivity of fixed points and looking at the intersection graph mentioned above. Finally, I began creating an outline for my presentation and final report.
- Week 7:
(So far) this week I continued to work on preparing my presentation and final report. I have found that having many of my previous results typed up, as well as having chronicled my work on this website, have been very helpful in choosing which topics I wish to present, and in what order. On Tuesday, I attended a talk by Dr. Simon Levin on mathematical ecology. Dr. Levin's talk really resonated with me, as he discussed the history of mathematical ecology over the last century, covering many areas that I really enjoy and have researched independently, including dynamical systems, topological data analysis, complex systems and complexity, game theory, and the history of mathematics.
References
- Abello, James, and François Queyroi. "Fixed points of graph peeling." Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. ACM, 2013.
- Wen, Dong, et al. "Enumerating k-Vertex Connected Components in Large Graphs." arXiv preprint arXiv:1703.08668 (2017).
Presentations
Additional Information
- My Mentor