r/mathematics • u/Homaderuvas • 14h ago

Drop some interesting problems in combinatorics

Hi guys kindly share some challenging and interesting combinatorics problems you have encountered with in the past.

8 Upvotes
  • permalink
  • reddit

90% Upvoted

12 comments sorted by

5

u/gexaha 14h ago

This one is very interesting - https://en.wikipedia.org/wiki/Union-closed_sets_conjecture

2

u/Homaderuvas 14h ago

I worked on this problem for about 3-4 months for absolutely no reason.

1

u/HasFiveVowels 11h ago

Same here! It seems so reasonable but then you get into it and you go "ahhh… there’s the rub"

5

u/NotaValgrinder 14h ago

Open problems or problems that have already been solved?

2

u/Homaderuvas 14h ago

Problems that have already been solved .

1

u/NotaValgrinder 14h ago

What level? Research level problems or just like fun combinatorics problems you could give one line solutions to?

3

u/Homaderuvas 14h ago

Research level problems that have been solved already.

4

u/NotaValgrinder 14h ago

Here's one - the algorithmic form of the LLL, solved by Moser: Given a k-SAT expression where each variable appears in at most 2^k/4k clauses, there exists a randomized algorithm that finds a satisfying assignment which averages polynomial time.

2

u/SnooCookies590 10h ago

Hindman’s theorem is super cool, more for the topological proof technique used. This writeup gives a nice introductory account:

https://math.uchicago.edu/\~may/REU2017/REUPapers/ZhouGuanyu.pdf

2

u/Claquet 14h ago

Found the subword complexity of the thue morse sequence

2

u/According_Switch_143 48m ago

Does every 2n-1+1 vertex induced subgraph of an n-dimensional hypercube (on 2n vertices) contain a vertex of degree at least root(n)? Note that there is a 2n-1 vertex induced subgraph of a hypercube consisting of only isolated vertices.

2

u/Traveling-Techie 46m ago

I chewed on this one for a while: what’s the number of times you have to flip a coin to get N in a row with P per cent certainty? Eg, if you want to film a video of you getting heads 20 times in a row with no cuts between, how many times do you need to flip for a 50% chance of success? It’s harder than it sounds.