If everyone in a city has exactly one friend in common with every other resident, must there be someone who is friends with all residents? — In order to answer this question, let’s first convert it into the language of graph theory. We represent the people in the city with vertices, and connect any two of these vertices with an edge if they are friends. The degree of a vertex is the number of edges which…

How a mathematician’s time in a forced labor camp during WW2 led to the discovery of a graph theory problem that still remains unsolved — In 1944, at the height of World War Two, the Hungarian Jewish mathematician Pál Turán was forced to labor in a brick factory near Budapest. His job consisted of pushing brick-filled carts from kilns to the yards where the bricks were stored. The carts traveled on crisscrossing rails connecting the…

We discuss a range of classical integer factorization algorithms and explore their future in the face of Shor’s algorithm. — Public-key cryptosystems like RSA have become indispensable in the digital age. From helping to secure e-commerce, to ensuring private communication on messaging apps, they constitute critical internet infrastructure. RSA’s power relies on the difficulty of factoring large integers. Other public-key cryptosystems depend on related challenges, like the discrete logarithm problem…

Delving into a deceptively simple-sounding problem that has gone unsolved for decades. — Introduction Like many great questions in math, the Cycle Double Cover Conjecture (C.D.C.C.) has the distinction of being relatively easy to state, but quite difficult to prove. It was proposed independently by two mathematicians, George Szekeres [7] and Paul Seymour [6], in the 1970s. …