MIT PRIMES/Art of Problem Solving
CROWDMATH 2021: Extremal combinatorics
Extremal Combinatorics
Polymath project forum
Polymath project forum
3
M
G
BBookmark
VNew Topic
kLocked
Extremal Combinatorics
Polymath project forum
Polymath project forum
3
M
G
BBookmark
VNew Topic
kLocked
No tags match your search
Mwellman
Sequence
combinatorics
expectation
matrix
pattern avoidance
Saturation
Sequences
stochastic process
floor function
geometry
graph theory
keszegh
linear algebra
wellman - rs
algorithm
alternation
Competitions
contests
Discrete Math
equalsn
induction
inequalities
keszegh - addedcol
keszegh - diagonal
linops
Matrices
permutations
pigeonhole principle
question
robots
ufree
videos
wellman - fixedn
wellman - fixeds
wellman - upperbound
No tags match your search
MG
Topic
First Poster
Last Poster
Asymptotically Optimal Construction for General C
EdwinNational 5
N
Jul 13, 2022
by LoneShadow379
We give an explicit construction with letters , and show that it has leading constant :
Note: is a sequence repeated times. We call each in the construction a .
Construction
Proof that the construction works
Note: is a sequence repeated times. We call each in the construction a .
Construction
Our construction is
, and for general , .
, and for general , .
Proof that the construction works
Consider two letters . We show that the alternating subsequence containing and has length less than .
The snippits containing and , in order, are
contributes 1 .
contributes 1 .
contributes terms to the sequence, as it starts with a .
contributes 1 .
contributes 1 .
Thus the length of the subsequence with and is . Setting gives a subsequence of length at most . This applies to all and , so the sequence has order at most .
The sequence itself has length , which is with leading coefficient .
More generally, setting gives a subsequence of length at most , creating a sequence of order , which have length asymptotic to , the upper bound.
The snippits containing and , in order, are
contributes 1 .
contributes 1 .
contributes terms to the sequence, as it starts with a .
contributes 1 .
contributes 1 .
Thus the length of the subsequence with and is . Setting gives a subsequence of length at most . This applies to all and , so the sequence has order at most .
The sequence itself has length , which is with leading coefficient .
More generally, setting gives a subsequence of length at most , creating a sequence of order , which have length asymptotic to , the upper bound.
5 replies
New Participant
doomslayer2945 1
N
Jan 14, 2022
by PiGuy3141592
Hey there! I just joined Crowd Math. How do I get started? Can someone catch me up to speed?
1 reply
welcome to crowdmath 2021
JGeneson 4
N
Jan 6, 2022
by PiGuy3141592
This year, our main topic is extremal combinatorics, with a focus on problems about sequences and 0-1 matrices. These problems have applications to many areas including:
-robot navigation (e.g. an algorithm for finding a shortest path between two given points in a grid with obstacles)
-discrete geometry (e.g. an upper bound on the maximum number of unit distances in a convex n-gon), and
-permutation pattern avoidance (the solution to the Stanley-Wilf conjecture).
Researchers have been investigating these kinds of problems for over fifty years. The topic requires no background knowledge besides basic combinatorics. You can learn more about relevant definitions and background reading on the Resources page. That page has a list of papers and exercises with each paper. All of the exercises are solved problems, they are there to help understand the topic.
The Problems page has a list of open problems. These problems are unsolved, most are from publications, and I made some of them. I’ll post some more open problems later in the year, and typically crowdmath participants also suggest open problems. Here are some examples of Crowdmath research papers from past years:
https://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i1p5
https://arxiv.org/search/math?searchtype=author&query=CrowdMath%2C+P+A
https://arxiv.org/abs/2008.13302
https://arxiv.org/abs/1710.11352
-robot navigation (e.g. an algorithm for finding a shortest path between two given points in a grid with obstacles)
-discrete geometry (e.g. an upper bound on the maximum number of unit distances in a convex n-gon), and
-permutation pattern avoidance (the solution to the Stanley-Wilf conjecture).
Researchers have been investigating these kinds of problems for over fifty years. The topic requires no background knowledge besides basic combinatorics. You can learn more about relevant definitions and background reading on the Resources page. That page has a list of papers and exercises with each paper. All of the exercises are solved problems, they are there to help understand the topic.
The Problems page has a list of open problems. These problems are unsolved, most are from publications, and I made some of them. I’ll post some more open problems later in the year, and typically crowdmath participants also suggest open problems. Here are some examples of Crowdmath research papers from past years:
https://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i1p5
https://arxiv.org/search/math?searchtype=author&query=CrowdMath%2C+P+A
https://arxiv.org/abs/2008.13302
https://arxiv.org/abs/1710.11352
4 replies
How do I join CrowdMath/get started?
aarpo 4
N
Dec 25, 2021
by Naman_Chibber
I am very interested in External Combinatorics and wondered how I can get started with CrowdMath 2021 (how can I contribute, etc.). I also wanted to ask, if research is published, would our names be on the paper (regarding what we contributed)?
4 replies
The $u$-free process on sequences
JGeneson 27
N
Dec 20, 2021
by PiGuy3141592
Consider the following process:
Fix a sequence with distinct letters. Let (the empty sequence).
1. For , we uniformly at random select a letter from (each with probability ).
2. Let be the sequence obtained from by addending the letter .
3. If does not contain and the last letters of are all distinct, let and increment and go back to 1. Otherwise, let and increment and go back to 1. (Note: the definition of containment here is the same as on the problem/resource pages.)
Eventually, this process produces a sequence for which it is impossible to add any more letters to the end without forcing containment of or a repeated letter among the last , so is constant after a certain point.
Define to be the expected length of the sequence that we obtain using the above process.
The problem is to find for all sequences .
Some (possibly?) easier to start with:
, , ,
, , ,
, , ,
and any other nice sequences that you can think of.
Is there an algorithm to calculate in general?
This problem is an analogue of the -free process on graphs: see e.g. https://arxiv.org/abs/0908.0429
Fix a sequence with distinct letters. Let (the empty sequence).
1. For , we uniformly at random select a letter from (each with probability ).
2. Let be the sequence obtained from by addending the letter .
3. If does not contain and the last letters of are all distinct, let and increment and go back to 1. Otherwise, let and increment and go back to 1. (Note: the definition of containment here is the same as on the problem/resource pages.)
Eventually, this process produces a sequence for which it is impossible to add any more letters to the end without forcing containment of or a repeated letter among the last , so is constant after a certain point.
Define to be the expected length of the sequence that we obtain using the above process.
The problem is to find for all sequences .
Some (possibly?) easier to start with:
, , ,
, , ,
, , ,
and any other nice sequences that you can think of.
Is there an algorithm to calculate in general?
This problem is an analogue of the -free process on graphs: see e.g. https://arxiv.org/abs/0908.0429
27 replies
CrowdMath meeting area (discord)
Babu10 0
Dec 13, 2021
Hello everyone I think we should all meet in discord to discuss ideas what do you think. Here is the invite link f you want to drop by https://discord.gg/KrGtAR7XaV
0 replies
New to Research
TheMath_boy 3
N
Oct 28, 2021
by walliboi0912
Hello, I'm new to research and I want to contribute to this project. I have read the papers from the resources but still, I didn't understand most of the parts of the research paper. I didn't catch many terminologies from the research paper.
Can someone please suggest to me how to get started with this project? What are the prerequisite topics that I need to know? Do I need college-level math knowledge?
Can someone please suggest to me how to get started with this project? What are the prerequisite topics that I need to know? Do I need college-level math knowledge?
3 replies
Where can I find the papers that are mentioned in Exercise A?
rusticglass 2
N
Aug 17, 2021
by rusticglass
Where can I find the papers that are mentioned in Exercise A? I can only find a Cornell webpage.
2 replies
Is CrowdMath 2021 still active?
lfc2004 1
N
Jul 15, 2021
by parityhome
Apologies for the intrusion, but I've just found out about CrowdMath and I'm interested in participating, but given the long time that appears to have elapsed since the most recent posts on the message board I wanted to check in and see if people are still actively working on the problems.
1 reply
Symmetric versions of $u$-free process on sequence
parityhome 0
Jun 8, 2021
I don't mean to add more versions of just for fun. The motivation is to make more symmetric. For example, we know that and are quite different.
One version is , where b stands for Bidirectional, and in the process we are allowed to insert a symbol to the beginning of the sequence as long as is avoided and the required sparsity is still preserved.
Another version is , where i stands for Insertion: we can insert any symbol anywhere with the same constraints.
Both these versions can have variant that only respects sparsity, and the process terminates whenever is present.
One version is , where b stands for Bidirectional, and in the process we are allowed to insert a symbol to the beginning of the sequence as long as is avoided and the required sparsity is still preserved.
Another version is , where i stands for Insertion: we can insert any symbol anywhere with the same constraints.
Both these versions can have variant that only respects sparsity, and the process terminates whenever is present.
0 replies
Asymptotically Optimal Construction for General C
EdwinNational 5
N
Jul 13, 2022
by LoneShadow379
We give an explicit construction with letters , and show that it has leading constant :
Note: is a sequence repeated times. We call each in the construction a .
Construction
Proof that the construction works
Note: is a sequence repeated times. We call each in the construction a .
Construction
Our construction is
, and for general , .
, and for general , .
Proof that the construction works
Consider two letters . We show that the alternating subsequence containing and has length less than .
The snippits containing and , in order, are
contributes 1 .
contributes 1 .
contributes terms to the sequence, as it starts with a .
contributes 1 .
contributes 1 .
Thus the length of the subsequence with and is . Setting gives a subsequence of length at most . This applies to all and , so the sequence has order at most .
The sequence itself has length , which is with leading coefficient .
More generally, setting gives a subsequence of length at most , creating a sequence of order , which have length asymptotic to , the upper bound.
The snippits containing and , in order, are
contributes 1 .
contributes 1 .
contributes terms to the sequence, as it starts with a .
contributes 1 .
contributes 1 .
Thus the length of the subsequence with and is . Setting gives a subsequence of length at most . This applies to all and , so the sequence has order at most .
The sequence itself has length , which is with leading coefficient .
More generally, setting gives a subsequence of length at most , creating a sequence of order , which have length asymptotic to , the upper bound.
5 replies