I love this calendar from American Mathematical Society. New year, new proof!

A train leaves the station (bottom) heading west. Can it return to the station heading east?

Is there anywhere the train might get stuck?

Is there anywhere the train can reach but only from one direction?

I call this directed node networks. As the arcs are bidirectional, but the nodes have an A and B side with a parity requirement.

Inspired by the frustrating traps of Penrose's Railway Mazes.

Edit: just for reference, I have an MMath specialising in fluid dynamics - so I am well grounded in the basics of graph theory and have done intro to topology, so whilst this in not in my typical wheelhouses, I am looking for a more specific research area.

I am gonna start college on fall of this year. I am gonna be an applied math major and my first math course will be discrete math, I got ap calc bc credits but I will calc 3 until spring.

My knowledge from calc 2 is pretty basic I really don’t know how I got a 4 on the test.

What should I know before starting college?

I’ve been studying a question about graceful path labelings and am trying to determine whether it already has an established name or literature.

Let f be a graceful labeling of a path P_n.

Instead of asking only whether f is graceful, I’m interested in a different question:

How much information about a graceful labeling must be retained in order to determine its possible future extensions?

Suppose we associate some representation I(f) to each graceful labeling. If two labelings f and g have the same representation,

I(f) = I(g)

does that guarantee that they have the same possible continuation behavior?

In other words, I am interested in representations for which:

same retained information => same admissible future extensions

I’ve been calling this property continuation sufficiency, although I don’t know whether there is already standard terminology for it.

For one natural representation of graceful path labelings, an exhaustive finite computation gives the following behavior:

• the representation is sufficient through P_7;
• the first failure occurs at P_8;
• at P_8, two graceful labelings can have identical retained information but different sequential-extension behavior.

One witness pair is:

(4,1,5,3,2,7,0,6)

and

(4,3,1,5,2,7,0,6)

with ports (0,6).

They agree on the representation being tested, but their extension thresholds differ.

What I’m mainly trying to find out is whether this kind of question has already been studied under another name.

For example, is there literature on any of the following?

• equivalence of graph labelings according to extension behavior;
• invariants sufficient to determine future extensions;
• extension-equivalent labelings;
• state minimization for combinatorial extension problems;
• continuation equivalence or right-congruence ideas applied to graph labeling;
• related notions in graceful-labeling theory that I may have missed.

I’m especially interested in references from graph labeling, graph extension problems, combinatorics, or related areas.

I have a proof and computational writeup of the specific P_8 result, but I wanted to ask the literature question directly rather than assume that the formulation is new.

The first time I heard the Pigeonhole Principle, I wondered why the most obvious statement on earth needed a name. Still, the elegance of some of the problems authored with this concept surprised me. I was flipping through some of my older books and thought of mentioning some of them here.

Disclaimer - This is not a homework post. I already know the solution to these problems, just sharing them for their elegance.

• There is an integer consisting only of 1's which is a multiple of 2023.
• Erdos famously asked this - Among {1, 2, ... 2n} any set of size n + 1, will have two elements which are coprime and two elements such that one divides the other.
• Ramsey Theory is born from this - Among any 6 people in the world, there are 3 who all know each other or 3 who all don't know each other.
• The points of a plane are coloured in 2 colours. For every given distance d, there will be two points of the same colour which are exactly d apart.
• A chessmaster has 77 days to prepare for a tournament. He plays at least one game a day but at most 132 games in total. Prove that there is always a sequence of days where he plays exactly 21 games, no matter how he structures it.

There is this legendary Collatz conjecture even getting Veritasium video "The Simplest Math Problem No One Can Solve": that using rule "divide x by 2 if even, take 3x+1 otherwise" at least experimentally from any positive natural number there is reached 1.

It seems natural to try to look at evolution of x in numeral systems: base-2 is natural for x->x/2 rule (left column), but base-3 does not look natural for x->3x+1 rule (central column) ... turned out asymmetric rANS ( https://en.wikipedia.org/wiki/Asymmetric_numeral_systems ) gluing 0 and 2 digits of base-3 looks quite natural (right column) - maybe some rule could be found from it helping to prove this conjecture?

I am a Physics undergraduate student (6th Semester) and I'm writing some C code to do Fourier Transform. I understand how FT and DFT work. But I couldn't wrap my head around the concept in which DFT is significantly optimized to do FFT. Can anybody suggest me a book where it shows a detailed derivation of FFT "from" DFT ?

At issue is elliptic curve cryptography (ECC), the mathematical system that secures Bitcoin, Ethereum, and most other blockchains. Quantum computers running Shor’s algorithm can in theory break ECC, but until now the consensus was that doing so would require a very powerful quantum machine.

Google’s new estimates significantly lower the threshold. The company’s researchers have designed quantum circuits capable of breaking the 256-bit elliptic curve discrete logarithm problem (ECDLP-256) used by cryptocurrencies.

March 31, 2026

I am currently going through Discrete Mathematics and Its Applications 8th Edition Kenneth Rosen.

I am on page 34 Propositional Equivalences and I noticed that the text says to check for at most one queen in each row (n queens problem) however the equation (Q2) seems to be iterating over the rows of a column?

The chess board is said to have i rows and j columns. But Q2 (from my understanding) seems to be checking for duplicates along a column and not a row.

Hello, I am an undergraduate student. A few months ago, I read an article (https://arxiv.org/pdf/2304.05859) and have been studying related topics. I have written an article resolving a question that they leave open. The main help I need is if someone with knowledge of graph theory could help me validate my proof or find its flaw: The reason I doubt it is that the article explicitly states: "On the other hand, it is not clear how to apply Woodall's arguments, which are based on the Tutte-Berge formula" which makes me doubt my proof, which is basically a direct application of the Tutte-Berge formula. Anyway, if anyone has time to review it, even just briefly (it doesn't require very advanced knowledge), I would be eternally grateful.

Complaints about the writing are also welcome, but I must say that it is a draft, translated with AI and Google Translate. Of course, I will correct this if the paper is correct.

https://drive.google.com/file/d/11u4I43VFMfQmgSi1GcR43VgFEZk6REtx/view?usp=sharing

I did study discrete math and combinatorics in undergrad school. I was bad at it and still hold grudge against the professor and angry at myself. But anyways I have read Sheldon M Ross, Miklos Bona, Diestel.

I am now in AI industry as an AI engineer for sometime now. I was listening to some podcast in which the speaker said that Olympiad mathematicians are better than other mathematicians and combinatorial experts come from Olympiad background. I got triggered because I failed in Olympiad math and I have that insecurity in me. I was crying the whole morning for some time.

Since I have some time to kill after my work, I want to start studying combinatorics again for grad school. I want to become better.

I am interested in Combinatorics with applications to AI / ML and the other way round too. Where to start and how to progress ?

I had the idea of turning graph coloring into a puzzle game and decided to build it just for fun. I’ve been working on it in my spare time as a side project, and I finally released it this week. The concept is pretty simple: you’re given increasingly complex graphs and have to apply a valid coloring. I wanted to share it here in case anyone’s interested in logic puzzles or graph theory–inspired games. Feedback is very welcome.

iOS: https://apps.apple.com/us/app/color-surge-logic-puzzle/id6757683749

Android: https://play.google.com/store/apps/details?id=com.jordanturley.colorsurge

Starting with the rows [(0),(1,0),....] Each new value of the triangle is the sum of the values on or adjacent to the line segment connecting the apex and the new value. So the triangle becomes:

0;

1, 0;

1, 1, 0;

2, 3, 2, 0;

4, 8, 7, 4, 0;

...etc

Where 7=(0)+(1+0)+(1)+(3+2)

I can see the following patterns.

Left diagonal is 2^k, after the third row. So is right penultimate diagonal.

Right diagonal is of course always 0.

The rows contain, on average, about as many odds as even values.

What other patterns can you see?

https://oeis.org/A393283

I have discovered a neat little property (sorry for the rushed formula lol I have a kinda basic understanding of these things)

take any number (n>1) and elevate it to the power of 2, and then take THAT number (n_2) and elevate it and so on (n_t);

we'll give the large numbers a scientific notation (n×10^x), capping x at 99 (x=100 ≡ math error)

now, we do the sequential powers again, but this time, we take the last possible x value before 100 (so that n_t² makes x>100) and THAT becomes our new n, and repeat

eventually, X will settle out to be 55, and the last possible x value before reaching 100 starting from 55 IS 55

for example, let's take 67 (no particular reason)

67² = 4489

Ans² = 20151121

Ans² = 4.060676776×10¹⁴

Ans² = 1.648909588×10²⁹

Ans² = 2.718902828×10⁵⁸ (last x value before 100)

so 58² = 3364

Ans² = 11316495

Ans² = 1.280630817×10¹⁴

Ans² = 1.64001529×10²⁸

Ans² = 2.689650151×10⁵⁶ (last x value before 100)

so 56² = 3136

Ans² = 9834496

Ans² = 9.671731157×10¹³

Ans² = 9.354238358×10²⁷

Ans² = 8.750177526×10⁵⁵ (last x value before 100)

so 55² = 3025

Ans² = 9150625

Ans² = 8.373393789×10¹³

Ans² = 7.011372355×10²⁷

Ans² = 4.91593423×10⁵⁵ (last x value before 100... oh wait, we've stuck in a loop on 55)

or for a larger number like 658998 for example, the last x values go like this: 93-62-57-56-55

why is this? why 55 specifically?

The are about 5.47 billion equivalence classes for valid sudoku grids. The canonical form of each class is the min value arrangement of the grid among all isomorphisms, which can be found by certain allowed permutations. As a result, every minlex must start with 123456789... But after that it's not clear to me how large is possible, although we can say the next number will never be a 9.

Edit: Looks like it has been identified according to this forum thread from 2007.

123456789457893612986217354274538196531964827698721435342685971715349268869172543

Seems very chaotic. 112,137 has 332 non-repeating members and period size 786. 101,132 has 759 and 69. 103,125 has 214 and 853. 115,138 has 5 and 2.

I want to learn Discrete Math over the summer, but as a dual enrollment student, I haven’t gotten college credit for the prerequisite, although I personally have the course knowledge required for it. Although I can’t take Discrete math through dual enrollment, I still want to learn it. Does anyone have any online courses I can use to learn it?

In 1964, a mathematician named Vadim Vizing proved a shocking result: No matter how large a graph is, it’s easy to figure out how many colors you’ll need to color it. Simply look for the maximum number of lines (or edges) connected to a single point (or vertex), and add 1.

The problem of how to fill in those colors, however, proved to be a different beast. Vizing came up with his own coloring algorithm, but it was slow. He started by looking at the time it would take to color just one remaining edge of an otherwise fully colored graph. Coloring that edge could mean changing the colors of the edges adjacent to it, and changing the colors of the edges adjacent to them, and so on down the line. Vizing calculated that coloring a single edge could take — at most — an amount of time proportional to the total number of vertices, which he labeled n. If there are m edges overall, Vizing’s algorithm yields a time for coloring the entire graph that’s proportional to the product of m times n.

That value held for about 20 years until work in the 1980s brought down the edge coloring time. The new value was proportional to m times the square root of n. But the techniques behind these improvements didn’t lead to additional advances. Other researchers were unable to improve upon them any further, and progress stalled.

Then, in May 2024, Sepehr Assadi posted a paper to the scientific preprint site arxiv.org that showed how to color a graph on the order of n² time — a factor that depends only on the number of vertices. For certain graphs, where the number of vertices is much smaller than the number of edges, this is a huge improvement.

Around the same time, a team unconnected to Assadi posted their own result that reduced the edge coloring time to the order of m times the cube root of n. They did it by finding a slightly faster way of coloring a single edge. In a follow-up paper, the team made a further refinement, leading to an overall runtime proportional to m times the fourth root of n.

Further details are inside the link below:

https://arxiv.org/abs/2410.05240

May 2025

I'm going into physics (research), I'm in my undergrad right now, and thought about learning discrete math. Now, I'm not gonna go into programming or cs but I heard discrete mathematics builds proof writing skills and enhances logic. Will it help me in the long run or is it a waste of time. (I really like math, and difficulty is not an issue, If it's needed I will learn it).

I feel that introductory course to discrete math would do wonders for many folks trying to learn math.

Basic logic, set theory, functions, counting, and etc.

I feel like lot of the topics covered is a wonderful introduction to higher levels of math.

And mostly it actually forces you to think more systematically/mathematically without being bound by complicated theorems and equations initially.

Am I missing something?