ISEF reflection + advice
by shiningsunnyday, May 21, 2017, 11:53 AM
This post is a brief reflection on my ISEF experience - including the project itself and how everything worked out. Since the Chengdu fair, I’ve gotten many PM’s from users to describe my experience, so I hope this post answers some of those questions and inspires AoPSers to join next year.
First, I’ll give a brief summary of our project. Since we’ve had to deliver summaries/pitches at all levels from a target audience ranging from an elementary schooler to a PHD in our field, it wouldn’t harm to do it again in this post.
On earth, we’re all familiar with the GPS satellite system which pinpoints the precise location of an object by knowing the object’s distance to three different satellites. Our project is an analogous concept, but for graphs, where “distance” between two vertices is defined as the minimum number of edges needed to get from one to the other. Essentially, say an object is lost on a certain vertex of the graph. By pre-selecting a well chosen set of vertices to be “landmarks,” the object may deduce which vertex it’s on by knowing the distance to each of these landmarks. The metric dimension of a graph is the minimal number of landmarks to set up this navigational system on the graph - that is, an object can always find itself no matter where it is.
For example, the metric dimension of a path is one - pick the first vertex as landmark and every vertex will have different distances to it. The metric dimension of a cycle with
vertices is two - pick two consecutive vertices and the distances to the two landmarks will be 
which are all distinct. The metric dimension is typically evaluated in gruesomely-slow manner for one specific graph at a time (the current algorithm is to try every set of landmarks), which makes our project the first attempt to prove bounds on the metric dimension for general families of graphs. Three bounds, the results of great efforts experimenting with small graphs and finding heuristics, are proven. We prove that the optimal upper bounds on the metric dimension for the Hamiltonian & outer planar and outer planar families are half and two-thirds of the number of vertices respectively. We also prove for maximal planar graphs a bound of three-fourths the number of vertices, while we conjecture the family’s actual metric dimension to be two-fifths the number of vertices (
a constant).
The first result is straightforward - go around the Hamiltonian cycle and select every alternating vertex to be a landmark and prove by contradiction that there exists two vertices with the same set of distances to all landmarks (the reader is encouraged to do so; hint: outer planar condition will be used). After I proved this, I tried to apply a similar landmark-selection for our two-fifths graph (I was also inspired after reading a paper that proved all 4-connected maximal planar graphs were Hamiltonian, which may or may not extend to all maximal planar graphs as
becomes large), but the proof by contradiction almost worked but failed for one case.
The second result came about as a result of our https://arxiv.org/pdf/1704.04066 (which puts a bound on the metric dimension in terms of the chromatic number of the graph, which, as far as we know, is the first time coloring has been tied to metric dimension). Roughly-speaking, we proved that the set of all vertices besides that of the most common color in a
coloring of the graph is a sufficient set of landmarks (this is where 
comes in. The itchy part is to deal with sets of vertices among those of the remaining color (we don’t want the case where two unselected vertices have the same set of neighbors, all of which must be landmarks by definition of a graph coloring) , so while our bound is straight-forward it’s not immediately applicable. Fortunately, it’s known that the chromatic number of outer planar graphs is 
and CJ was able to tie up some loose ends by dispelling the remaining few cases in which there existed alike sets of vertices. Plugging in 
into our coloring lemma finishes the proof.
The third result came about as a result of our coloring lemma, into which we can plug in
the result of the First, however, we had to prove our “onion-peeling” lemma, which stated that the only maximal planar graph with alike vertices is the bipyramids via an extremal graph theory argument (this was the highlight of our project mathematically - approx. a C3-level argument). Funnily, CJ and I first articulated the proof of this in the coffee shop on the first day we met in the Philippines, scratch work and ugly graphs all over the place and a couple of suspicious stares in our direction.
For the conjecture, I nevertheless typed up my progress with the Hamiltonian cycles but also emphasized the motivation behind it during each of our interviews - the fact that by Kuratowski’s Theorem a planar graph can’t have
but interestingly 
has metric dimension of 
which may motivate our 
conjecture and possible decomposition/reduction/breaking down into subgraphs approaches (which we tried but failed due to the inflexibility of the metric dimension).
We also discussed applications in chemistry, urban planning, and Mars colonization.
Now, I have to admit, coming to ISEF, CJ and I definitely didn’t expect us to win second place (in fact, I would be glorious if we even won an honorable mention, around top 25% for each category). Mathematical rigor wise, we were probably above-average at best (esp. in the face of the topology, abstract algebra and number theory projects). The thing is, at first glance, our project seemed almost ant-sized when compared to Karthik’s (best of category, the only first place winner) whose background knowledge alone required understanding of category theory and topology as well as co-products and co-limits and their operations (I got lost just sentences into his pitch to CJ and I).
Ultimately, what clicked for me was what the head of judging said two days prior in a symposium, that the judges are really looking for 1) originality and 2) overcoming challenges. So during the interviews, CJ and I focused on the originality side of our results (emphasizing this will open a new pathway to the study of metric dimension and that our work is the first of its kind) and how we had to overcome the challenges of having all our initial (based off existing literature) approaches all fail. What ended up working was the two approaches at the bottom of our possible-approaches-list, Hamiltonian cycles and coloring, the only two original approaches.
In addition, a couple of judges took great interest in the fact we’re from separate (and possible war-tension-biding) countries and still managed to work together, so I guess it might’ve helped us.
So in deciding whether to do ISEF, I think the first thing to note is that mathematical projects aren’t mathematical research in the traditional sense (emphasizing rigor and strong background knowledge). ISEF is all about innovation and it’s hard to persuade the judging committee that if your project simply adds a twist on existing results, no matter how high-level your topic is. A lot of math projects there proved some generalization of an existing result at a high level background - while impressive and probably stronger work, the fact it’s been done before probably takes away from the score (and the math professors there will certainly not cut you any slack for that).
I would suggest MIT Primes as a better alternative for presenting hard-sound proofs and delving into appropriate theory/problems under excellent mentorship (you can ask my brother-in-arms flyingpurplepeopleeater about that). In fact, the hardest part about ISEF is probably in finding the right topic, since there’s really no one to ask when choosing topic. In fact, I spent about a month making calls with math professors in the Connecticut area via a counselor at the Yale’s Young Scholars Program. Most of them gave less-than-satisfactory topic recommendations, so I ended up grabbing a graduate level combinatorics book (this was around October) and went to work reading papers by myself. At that point, CJ and I werespamming talking almost 24/7 on Skype. Eventually, CJ came across the words metric dimension for the first time at a local university, and I happened to be reading a lot on planar graphs at the time, so we thought, “Why not explore the metric dimensions of planar graphs, since it’s been never been done before?” And that’s really how our project started.
As to how to get the right topic, I don’t really have any answers. I would personally suggest combinatorics since it’s a newer field than say prime numbers and is relatively easy to be innovative, but of course other fields are just as fruitful for research. Perhaps, it may be easier to do something with an applied flavor (for example, our project could be applied for object navigation). While mathematical rigor is still a must, doing something applied (perhaps to solve a real life problem) not only may speed up the process of generating a topic but may also be easier for you to explain to judges, esp. at the local fair (I can definitely imagine what the other math projects had to go through at their local/regional fairs). Our results and proofs, while entirely combinatorial, may have gotten a compelling bonus point for the fact we were able to explain it in a way people can sympathize and appreciate the significance of (that is, the GPS analogy).
To sum it up, I definitely encourage more AoPSers to do ISEF (I only met a handful, even in our category). It’s hard to put my experience in words since really, anything is possible - and just going to ISEF will make you a more optimistic person. From attending symposiums by distinguished lecturers, to listening in on the panels of entrepreneurs and Nobel Prize winners and MacArthur fellows, to just walking around the exhibit and being in the same room as the future leaders of STEM, to presenting your ideas to both professors and the public was a special experience that made me wake up every morning feeling excited to learn something new.
Of course, you also get to go to a-completely-reserved-for-ISEF Universal Studios and go on the Mummy ride with no waiting time and go into any restaurant and order all you can eat for free.
I became slightly more daring and open myself the past week. The first day, CJ and I made a great effort to go around to random delegations and striking up conversations (I let CJ handle all the ones with girls), but by the end of the week talking to anyone was really natural.
The ultimate takeaway is that anything you can dream of can become a reality; the only thing stopping you is your own doubts. Quite literally, I had practiced my celebration poses alone in my room so many times when it actually happened I was barely surprised. ISEF is all about developing a mindset that every one of us can make a change in the world - in the words of one of the alumni, if not us, then who? Critics' beliefs are based only off the status quo, and the status quo must've been formed at some point by someone no smarter than you and it's meant to be changed.
Of course, I also think it's very important to reach out - all the brightest minds in the world today are just a few mouse clicks away, so all you need is the courage. While people may not respond (like the professors CJ and I emailed), you should keep asking. I owe great gratitude for CJ - the 2nd place would've never taken place without him.
If there's any more questions you can comment here or send CJ or I a PM and we'll respond. Otherwise, I encourage you all to try and maybe I can meet some of you next year?
First, I’ll give a brief summary of our project. Since we’ve had to deliver summaries/pitches at all levels from a target audience ranging from an elementary schooler to a PHD in our field, it wouldn’t harm to do it again in this post.
On earth, we’re all familiar with the GPS satellite system which pinpoints the precise location of an object by knowing the object’s distance to three different satellites. Our project is an analogous concept, but for graphs, where “distance” between two vertices is defined as the minimum number of edges needed to get from one to the other. Essentially, say an object is lost on a certain vertex of the graph. By pre-selecting a well chosen set of vertices to be “landmarks,” the object may deduce which vertex it’s on by knowing the distance to each of these landmarks. The metric dimension of a graph is the minimal number of landmarks to set up this navigational system on the graph - that is, an object can always find itself no matter where it is.
For example, the metric dimension of a path is one - pick the first vertex as landmark and every vertex will have different distances to it. The metric dimension of a cycle with
vertices is two - pick two consecutive vertices and the distances to the two landmarks will be 
which are all distinct. The metric dimension is typically evaluated in gruesomely-slow manner for one specific graph at a time (the current algorithm is to try every set of landmarks), which makes our project the first attempt to prove bounds on the metric dimension for general families of graphs. Three bounds, the results of great efforts experimenting with small graphs and finding heuristics, are proven. We prove that the optimal upper bounds on the metric dimension for the Hamiltonian & outer planar and outer planar families are half and two-thirds of the number of vertices respectively. We also prove for maximal planar graphs a bound of three-fourths the number of vertices, while we conjecture the family’s actual metric dimension to be two-fifths the number of vertices (
a constant).The first result is straightforward - go around the Hamiltonian cycle and select every alternating vertex to be a landmark and prove by contradiction that there exists two vertices with the same set of distances to all landmarks (the reader is encouraged to do so; hint: outer planar condition will be used). After I proved this, I tried to apply a similar landmark-selection for our two-fifths graph (I was also inspired after reading a paper that proved all 4-connected maximal planar graphs were Hamiltonian, which may or may not extend to all maximal planar graphs as
becomes large), but the proof by contradiction almost worked but failed for one case.The second result came about as a result of our https://arxiv.org/pdf/1704.04066 (which puts a bound on the metric dimension in terms of the chromatic number of the graph, which, as far as we know, is the first time coloring has been tied to metric dimension). Roughly-speaking, we proved that the set of all vertices besides that of the most common color in a
coloring of the graph is a sufficient set of landmarks (this is where 
comes in. The itchy part is to deal with sets of vertices among those of the remaining color (we don’t want the case where two unselected vertices have the same set of neighbors, all of which must be landmarks by definition of a graph coloring) , so while our bound is straight-forward it’s not immediately applicable. Fortunately, it’s known that the chromatic number of outer planar graphs is 
and CJ was able to tie up some loose ends by dispelling the remaining few cases in which there existed alike sets of vertices. Plugging in 
into our coloring lemma finishes the proof.The third result came about as a result of our coloring lemma, into which we can plug in
the result of the First, however, we had to prove our “onion-peeling” lemma, which stated that the only maximal planar graph with alike vertices is the bipyramids via an extremal graph theory argument (this was the highlight of our project mathematically - approx. a C3-level argument). Funnily, CJ and I first articulated the proof of this in the coffee shop on the first day we met in the Philippines, scratch work and ugly graphs all over the place and a couple of suspicious stares in our direction.For the conjecture, I nevertheless typed up my progress with the Hamiltonian cycles but also emphasized the motivation behind it during each of our interviews - the fact that by Kuratowski’s Theorem a planar graph can’t have
but interestingly 
has metric dimension of 
which may motivate our 
conjecture and possible decomposition/reduction/breaking down into subgraphs approaches (which we tried but failed due to the inflexibility of the metric dimension).We also discussed applications in chemistry, urban planning, and Mars colonization.
Now, I have to admit, coming to ISEF, CJ and I definitely didn’t expect us to win second place (in fact, I would be glorious if we even won an honorable mention, around top 25% for each category). Mathematical rigor wise, we were probably above-average at best (esp. in the face of the topology, abstract algebra and number theory projects). The thing is, at first glance, our project seemed almost ant-sized when compared to Karthik’s (best of category, the only first place winner) whose background knowledge alone required understanding of category theory and topology as well as co-products and co-limits and their operations (I got lost just sentences into his pitch to CJ and I).
Ultimately, what clicked for me was what the head of judging said two days prior in a symposium, that the judges are really looking for 1) originality and 2) overcoming challenges. So during the interviews, CJ and I focused on the originality side of our results (emphasizing this will open a new pathway to the study of metric dimension and that our work is the first of its kind) and how we had to overcome the challenges of having all our initial (based off existing literature) approaches all fail. What ended up working was the two approaches at the bottom of our possible-approaches-list, Hamiltonian cycles and coloring, the only two original approaches.
In addition, a couple of judges took great interest in the fact we’re from separate (and possible war-tension-biding) countries and still managed to work together, so I guess it might’ve helped us.
So in deciding whether to do ISEF, I think the first thing to note is that mathematical projects aren’t mathematical research in the traditional sense (emphasizing rigor and strong background knowledge). ISEF is all about innovation and it’s hard to persuade the judging committee that if your project simply adds a twist on existing results, no matter how high-level your topic is. A lot of math projects there proved some generalization of an existing result at a high level background - while impressive and probably stronger work, the fact it’s been done before probably takes away from the score (and the math professors there will certainly not cut you any slack for that).
I would suggest MIT Primes as a better alternative for presenting hard-sound proofs and delving into appropriate theory/problems under excellent mentorship (you can ask my brother-in-arms flyingpurplepeopleeater about that). In fact, the hardest part about ISEF is probably in finding the right topic, since there’s really no one to ask when choosing topic. In fact, I spent about a month making calls with math professors in the Connecticut area via a counselor at the Yale’s Young Scholars Program. Most of them gave less-than-satisfactory topic recommendations, so I ended up grabbing a graduate level combinatorics book (this was around October) and went to work reading papers by myself. At that point, CJ and I were
As to how to get the right topic, I don’t really have any answers. I would personally suggest combinatorics since it’s a newer field than say prime numbers and is relatively easy to be innovative, but of course other fields are just as fruitful for research. Perhaps, it may be easier to do something with an applied flavor (for example, our project could be applied for object navigation). While mathematical rigor is still a must, doing something applied (perhaps to solve a real life problem) not only may speed up the process of generating a topic but may also be easier for you to explain to judges, esp. at the local fair (I can definitely imagine what the other math projects had to go through at their local/regional fairs). Our results and proofs, while entirely combinatorial, may have gotten a compelling bonus point for the fact we were able to explain it in a way people can sympathize and appreciate the significance of (that is, the GPS analogy).
To sum it up, I definitely encourage more AoPSers to do ISEF (I only met a handful, even in our category). It’s hard to put my experience in words since really, anything is possible - and just going to ISEF will make you a more optimistic person. From attending symposiums by distinguished lecturers, to listening in on the panels of entrepreneurs and Nobel Prize winners and MacArthur fellows, to just walking around the exhibit and being in the same room as the future leaders of STEM, to presenting your ideas to both professors and the public was a special experience that made me wake up every morning feeling excited to learn something new.
Of course, you also get to go to a-completely-reserved-for-ISEF Universal Studios and go on the Mummy ride with no waiting time and go into any restaurant and order all you can eat for free.
I became slightly more daring and open myself the past week. The first day, CJ and I made a great effort to go around to random delegations and striking up conversations (I let CJ handle all the ones with girls), but by the end of the week talking to anyone was really natural.
The ultimate takeaway is that anything you can dream of can become a reality; the only thing stopping you is your own doubts. Quite literally, I had practiced my celebration poses alone in my room so many times when it actually happened I was barely surprised. ISEF is all about developing a mindset that every one of us can make a change in the world - in the words of one of the alumni, if not us, then who? Critics' beliefs are based only off the status quo, and the status quo must've been formed at some point by someone no smarter than you and it's meant to be changed.
Of course, I also think it's very important to reach out - all the brightest minds in the world today are just a few mouse clicks away, so all you need is the courage. While people may not respond (like the professors CJ and I emailed), you should keep asking. I owe great gratitude for CJ - the 2nd place would've never taken place without him.
If there's any more questions you can comment here or send CJ or I a PM and we'll respond. Otherwise, I encourage you all to try and maybe I can meet some of you next year?
tho it'll probably begin with: "assume that all michael said is false..."
May 2018
April 2018