A Young Korean Mathematician Solves a 50-Year-Old Conundrum

In 1972, during a casual gathering, mathematician ERDŐS Pal brought up a mathematical problem to his colleagues Laszlo LOVASZ and Vance FABER. It was a simple proposition related to graph theory, which the three mathematicians thought could be easily proven. However, contrary to their expectations, the problem remained unsolved for decades and became an enduring mystery in the world of mathematics.

Fast forward to 2021, the problem was finally solved after over 50 years. Despite numerous mathematicians grappling with the problem, the longstanding conundrum in the mathematical world found its resolution in the hands of a young Korean mathematician, who achieved this remarkable feat less than a year after receiving his doctoral degree. Laszlo LOVASZ himself expressed his joy through the mathematics journal 'Quanta,' stating that it's "like a beautiful piece of work" and that he is pleased to witness such progress.

The protagonist who solved the problem is KANG Dong Yup, the Young Scientist Fellow (YSF) and the next-generation research leader in the Extreme Combinatorics and Probability Group within the Institute for Basic Science (IBS). The Young Scientist Fellowship is an IBS program aimed at junior researchers to foster outstanding research achievements. Kang joined the IBS as a YSF in June of this year.

In October, Kang was recognized for his research accomplishments and received the prestigious 2023 Korean Mathematical Society Award for Young Mathematicians. This award is given to individuals who received their Ph.D. less than 5 years ago and have made significant contributions to the field of mathematics. Three recipients are selected each year.

We had the opportunity to speak with Research Leader KANG Dong Yup to delve into the background of his research that led to the resolution of this 50-year-old problem.

Q: Could you introduce yourself?

A: I am KANG Dong Yup, a research leader at the IBS Extreme Combinatorics and Probability Group. I majored in computer science and mathematics at KAIST and earned my Ph.D. in Mathematical Sciences from KAIST in 2020. My advisor, Professor EOM Sang-il, leads the IBS Discrete Mathematics Group as a Chief Investigator. After completing my Ph.D., I spent three years as a postdoctoral researcher at the University of Birmingham in the UK and am currently conducting research in the IBS Extreme Combinatorics and Probability Group.

Q: What is the Extreme Combinatorics and Probability Group?

A: The IBS Extreme and Probability Combination Group CI, led by Professor Hong LIU, was launched in March 2022 as the fourth research group established in the Center for Mathematical and Computational Sciences. The Extreme Combinatorics and Probability Group focuses on research areas such as extreme combinatorics, probabilistic combinatorics, and discrete geometry.

Q: Could you tell us about your research?

A: I am researching extreme combinatorics and probabilistic combinatorics. Extreme combinatorics deals with finding optimal values of combinatorial parameters in situations with constraints. In probabilistic combinatorics, I study probability spaces related to specific combinatorial structures. Although they may seem unrelated at first, these two fields complement each other. For example, methodologies used in extreme combinatorics can be applied to probabilistic combinatorics.

These fields have been seriously studied for about 100 years, and they are more recent compared to classical mathematical fields like algebra and number theory. With the advancement of computers, research in these areas has become more active, especially because solving real-life problems using computers often requires mathematical methods.

Q: How is your research relevant to real-life applications?

A: A typical example is using navigation systems to find optimal routes. One of the main objects we deal with in our research is graphs, which are structures composed of 'nodes' and connecting 'edges.' This is something people generally refer to as a network. In the case of navigation, points are represented as nodes, and roads are represented as edges, which transform the task into an algorithmic problem.

Structural graph theory is related to algorithmic problems of graphs with specific properties. Probabilistic combinatorics is deeply connected to the design of random algorithms. Therefore, when designing algorithms for applications like social network friend recommendations or search algorithms for search engines, mathematical theories from these areas come into play.

Q: Your research was featured in the 2021 Quanta Magazine.

A: I successfully proved the Erdős–Faber–Lovász conjecture for all but finitely many cases. The conjecture states that "if a linear hypergraph has N vertices, then the number of colors needed to color the overlapping edges of the hypergraph in such a way that adjacent edges have different colors is at most N."

Here, a hypergraph is a mathematical structure that allows each edge to contain more than two vertices. Although this proposition seems relatively simple in mathematics, it turned out to be a puzzle that remained unsolved for over 50 years.

Q: How do you usually choose your research topics?

A: I tend to choose research topics spontaneously, and it often works well for me. When selecting a research topic, it's essential to feel a strong attraction and interest since research typically involves a prolonged commitment to the chosen subject. Sometimes, I develop an interest in problems introduced at workshops, or I might receive proposals from collaborators. I also initiate proposals myself at times.

Q: Could you tell us about the motivation behind starting the research on the Erdős–Faber–Lovász conjecture?

A: It happened when I was a postdoctoral researcher at the University of Birmingham. Professors Daniela KÜHN and Deryk OSTHUS, who were my mentors, suggested trying to solve this problem one day. In fact, it seemed out of the blue. I thought they were joking because it was a long-standing problem that hadn't been solved for a long time. But they were serious.

Q: Was it challenging?

A: To put it bluntly, it was not as difficult as we thought. Initially, the professors thought that using the results of this one paper would be sufficient. However, when we attempted to solve the problem, it turned out that it was a misconception on their part. Such things are common among mathematicians.

Serendipity played a role. At that time, I was working on a problem with colleagues that, ironically, ended up providing the key idea for solving the Erdős–Faber–Lovász conjecture. We also had a researcher in our team who was working on graph theory and coloring problems. The fortunate sequence of events allowed us to solve the conjecture in about six months.

Q: You solved a puzzle that had remained unsolved for over 50 years in just six months?

A: It was indeed a significant event in my research career. It's common to face roadblocks when solving mathematical problems. Resolving those roadblocks can take anywhere from a week to several months. However, this research progressed unusually smoothly. Even when we faced challenges, ideas came to us within a few days. Interestingly, even the professors, who were my mentors, said it was like magic.

Q: What does this research result mean for this field?

A: The problem we solved is one of the simplest examples among the unresolved problems related to linear hypergraph coloring. Unlike Brooks' theorem or Vizing's theorem about graph coloring, which have precise results, problems related to linear hypergraph coloring have rarely produced exact results. Typically, researchers obtain approximate results. The significance lies in providing an exact result rather than an approximate one. I believe that this result can serve as a bridgehead for the journey of solving important problems in my research area.

Q: Did this achievement contribute to being recognized, like being selected as a Rising Young Mathematician in 2021?

A: I was genuinely happy when I heard the news. I didn't expect it at all. However, I also had mixed feelings. Looking at the list of previous awardees, there were many outstanding mathematicians. I wondered if I truly deserved such a high honor. It was a bit burdensome, but I accepted it as an encouragement for further success in my research career, so I plan to dedicate myself even more to my work.

Q: Your original dream was to become a programmer rather than a mathematician?

A: I dreamed of becoming a programmer since I was young. I loved computer programming to the extent that I participated in the International Olympiad in Informatics (IOI) as a high school student. Naturally, I planned to major in computer science when entering university. When I joined KAIST's computer science department, I was already taking sophomore year courses during my freshman year. Ironically, during my sophomore year courses, there were no courses available for me to take.

I ended up taking math courses because a friend recommended it. It was a course on real analysis, a rigorous form of mathematics. I was also interested in algorithm design within programming, and I believed that studying rigorous mathematics would help me in designing algorithms.

Q: You later shifted your career path to become a full-fledged mathematician

A: Computer science is broadly divided into computer science and computer engineering. I was more interested in computer science with a focus on theory. I wanted to delve deep into the study of algorithms and to achieve that, I realized I needed to study more mathematics. In computer algorithms, graph algorithms are often dealt with, which are also studied in mathematics, so the connection was clear.

Q: After receiving your Ph.D. from KAIST, you went to the University of Birmingham in the UK.

A: Professor KIM Jae-hoon, a professor in the Department of Mathematical Sciences at KAIST, had a significant influence. I first met Professor Kim at a workshop organized by postdoctoral researchers during my master's course at KAIST. Professor Kim was planning to move to the University of Birmingham as a postdoctoral researcher. The University of Birmingham is a large institution with many researchers well-versed in my research area, and it seemed like a good place for research.

Later, I attended a workshop at the University of Oxford in 2018. There, I met Professors Hong LIU and KIM Jae-hoon again, and they were the mentors who later played a crucial role in my career. The University of Birmingham had a postdoctoral position opening around that time. Although I still had one more year until completing my Ph.D., the professors proposed that I wait for a year at the University of Birmingham. I ended up choosing the University of Birmingham due to the excellent mentors and the conducive research environment.

Q: After that, you joined IBS as YSF. Could you tell us about the joining process.

A: My contract period as a postdoctoral researcher at the University of Birmingham was coming to an end. Professor Hong LIU suggested that I apply for the IBS YSF. I had a bit of nostalgia for Korea because I couldn't enter the country due to COVID-19 during my three years in the UK.

Q: Similar programs exist abroad. Why did you choose to be an IBS YSF.

A: First and foremost, research funding is abundant. Pure mathematics doesn't require advanced experimental equipment, but attending international workshops and conferences requires funds for travel and stays. Also, hosting workshops in Korea and inviting foreign scholars or speakers is a good way to use the funds actively. The support allows researchers to proactively organize workshops.

The environment that enables researchers to focus solely on research is another advantage. Researchers often find administrative tasks challenging, but IBS has staff who provide support for administrative tasks and assist researchers. This creates the best conditions for researchers to work independently on their research.

Lastly, the duration of the research is relatively long. Typically, the contract period for postdoctoral researchers is about 2 to 3 years, but in the case of IBS YSF, there is a 3-year contract with the possibility of an additional 2-year extension. You can conduct research for up to 5 years. Ample time allows for a stable environment where researchers can focus on their work.

Q: Are there significant advantages of IBS YSF compared to similar programs abroad?

A: Even compared to institutions worldwide, I believe the conditions offered by IBS YSF are exceptional. However, there are some obstacles for foreign researchers to choose to work in Korea. For example, most mathematical workshops and conferences are held in the United States or Europe, which can be difficult to attend. Language is another barrier. Nevertheless, IBS provides excellent support and infrastructure, attracting foreign researchers. In fact, many outstanding foreign researchers are working at IBS.

Personally, I think there needs to be more programs like these to enhance the development of mathematics in Korea. Although IBS has many graduate student researchers, if talented researchers from around the world gather in Korea, it can provide Korean student researchers with more opportunities for joint research and further develop their skills.

Q: What are your research plans for the future?

A: If you are a mathematician in my field, there are problems that everyone admires. Unresolved problems related to "Ramsey numbers" are among them. There are also many unsolved conjectures left by mathematicians Erdős, and his co-researchers, such as "Erdős–Hajnal Conjecture." Someday, I want to solve problems like these. My team and I already solved Erdős–Faber–Lovász conjecture, but I want to go much further than that. By solving problems in my field, I believe it would be possible to create more efficient random algorithms. There are many areas where such algorithms are being used currently, and I believe it would be possible to greatly lower the time and complexity to perform calculations.