MIT PRIMES/Art of Problem Solving
CROWDMATH 2016: Pattern Avoidance
Pattern Avoidance
CrowdMath project forum
CrowdMath project forum
3
M
G
BBookmark
VNew Topic
kLocked
Pattern Avoidance
CrowdMath project forum
CrowdMath project forum
3
M
G
BBookmark
VNew Topic
kLocked
No tags match your search
Mmatrix
linear algebra
Problem 3
Marcus - Excluded Permutation Matrices
Fulek: Forbidden Patterns in 0-1 Matrices
Problem 1
extremal functions
function
Keszegh - Forbidden Submatrices
Guth - Joints Problem
Problem 2
crowdmath
H. Cohn et al. - D_4 Not Optimal
H. Cohn et al. - D_4 Not Optimal - null
Problem 7
Klazar, Marcus - Füredi-Hajnal conjecture
Klazar, Marcus - Füredi-Hajnal conjecture - null
Problem 8
Problem 9
Fox - Typically Exponential Limits
geometry
inequalities
mitprimes
pattern avoidance
Sequences
Weidert - Extremal Problems
algorithms
Fulek: Forbidden Patterns in 0-1 Matrices - Exercise A
Marcus - Excluded Permutation Matrices - Exercise B
pattern
pigeonhole principle
polymath
polynomial
Problem 4
0-1 swap
algebra
algorithm
AM-GM
avoidance
Binary
calculus
combinatorics
crowdmath 2017
data points
Dimensions
Foundation mathematics
Fox - Typically Exponential Limits - Exercise A
Fulek Forbidden Patterns in 0-1 Matrices
Fulek: Forbidden Patterns in 0-1 Matrices - Exercise B
Fulek: Forbidden Patterns in 0-1 Matrices - Exercise C
No tags match your search
MG
Topic
First Poster
Last Poster
i CrowdMath paper: pattern containment algorithms
JGeneson 1
N
Apr 19, 2017
by JGeneson
Hi everyone,
Here is a draft of the third CrowdMath paper about algorithms for detecting pattern containment in 0-1 matrices. This paper was written by CrowdMath mentor Peter Tian.
If you see any typos, errors, improvements, or places where you can add a figure or more explanation, then please edit the tex file and post it in this thread. This paper will be open to edit until the end of March.
Anyone is welcome to edit this paper. If you edit it, then please edit the version attached to the most recent post in this thread.
Thank you very much for your help.
Here is a draft of the third CrowdMath paper about algorithms for detecting pattern containment in 0-1 matrices. This paper was written by CrowdMath mentor Peter Tian.
If you see any typos, errors, improvements, or places where you can add a figure or more explanation, then please edit the tex file and post it in this thread. This paper will be open to edit until the end of March.
Anyone is welcome to edit this paper. If you edit it, then please edit the version attached to the most recent post in this thread.
Thank you very much for your help.
1 reply
i CrowdMath paper: pattern avoidance game
JGeneson 2
N
Apr 19, 2017
by JGeneson
Hi everyone,
Here is a draft of the second CrowdMath paper about the pattern avoidance game in 0-1 matrices. This paper was written by CrowdMath mentor Ben Yang.
If you see any typos, errors, improvements, or places where you can add a figure or more explanation, then please edit the tex file and post it in this thread. This paper will be open to edit until the end of March.
Anyone is welcome to edit this paper. If you edit it, then please edit the version attached to the most recent post in this thread.
Thank you very much for your help.
Here is a draft of the second CrowdMath paper about the pattern avoidance game in 0-1 matrices. This paper was written by CrowdMath mentor Ben Yang.
If you see any typos, errors, improvements, or places where you can add a figure or more explanation, then please edit the tex file and post it in this thread. This paper will be open to edit until the end of March.
Anyone is welcome to edit this paper. If you edit it, then please edit the version attached to the most recent post in this thread.
Thank you very much for your help.
2 replies
i CrowdMath paper: minimally non-linear patterns
JGeneson 4
N
Jan 4, 2017
by JGeneson
Hi everyone,
Here is a draft of the first CrowdMath paper about minimally non-linear patterns in 0-1 matrices, sequences, and ordered graphs.
If you see any typos, errors, improvements, or places where you can add a figure or more explanation, then please edit the tex file and post it in this thread. This paper will be open to edit for the rest of the year.
Anyone is welcome to edit this paper. If you edit it, then please edit the version attached to the most recent post in this thread.
Thank you very much for your help.
Here is a draft of the first CrowdMath paper about minimally non-linear patterns in 0-1 matrices, sequences, and ordered graphs.
If you see any typos, errors, improvements, or places where you can add a figure or more explanation, then please edit the tex file and post it in this thread. This paper will be open to edit for the rest of the year.
Anyone is welcome to edit this paper. If you edit it, then please edit the version attached to the most recent post in this thread.
Thank you very much for your help.
4 replies
k i Welcome to CrowdMath
CrowdMath 1
N
Mar 14, 2016
by copeland
CrowdMath is an open project that gives all high school students the opportunity to collaborate on a large research project with top-tier research mentors and an exceptional peer group. MIT PRIMES and Art of Problem Solving are working together to create a place for students to experience research mathematics and discover ideas that did not exist before.
Below we've tried to unpack and explain the things you will find on the CrowdMath page:
Resources and Problems
The problems in the CrowdMath project are open, unsolved problems in mathematics. We will be discovering new truths that were unknown before. The problems will become available on March 1, 2016. Until then, we expect participants to be studying the readings in our Resources section of the CrowdMath page.
The Resources for this project are background ideas that you will need to understand and make progress on the CrowdMath problems. We've chosen resources that are directly relevant to the project: the problems are defined explicitly in terms of ideas that you will find in our resources. All of the problems we will pose are thematically linked and all of the resources we post will be as well. We will be releasing the resources roughly in the order that you should be reading them.
Each resource also has exercises to help clarify the key ideas and give practice with them. You can discuss the exercises by clicking either the "View Discussions" or "Start New Topic" button.
Eligibility
CrowdMath is designed to give very well-prepared high school students (as of 1/1/16) experience with math research. Very advanced middle school students are also welcome to participate. We know that the problems will be interesting to a broader range of people, but we want to create a specific opportunity for the upcoming generation of math and science researchers.
Be polite and constructive
This rule is simple, but important. The goal here is to learn to collaborate. Be nice!
Make your comments as easy to understand as possible
Polymath is a conversation. Assume that many people will be reading anything you write. Take a little time to make sure you write as clearly as possible and all of your collaborators will appreciate it.
Mentors
We have plenty of people watching and ready to help out when needed. However, we also know that there are many mathematicians out there who will find the CrowdMath project interesting and will want to help out. If you'd like to take part, send us a note at crowdmath@aops.com.
Dissemination of results and intellectual property
Polymath projects are inherently massively collaborative. Done correctly, it should be impossible to determine the lines between one person's work and the rest of the group. As such, we agree that the results created must be attributed to all CrowdMath contributors.
Below we've tried to unpack and explain the things you will find on the CrowdMath page:
Resources and Problems
The problems in the CrowdMath project are open, unsolved problems in mathematics. We will be discovering new truths that were unknown before. The problems will become available on March 1, 2016. Until then, we expect participants to be studying the readings in our Resources section of the CrowdMath page.
The Resources for this project are background ideas that you will need to understand and make progress on the CrowdMath problems. We've chosen resources that are directly relevant to the project: the problems are defined explicitly in terms of ideas that you will find in our resources. All of the problems we will pose are thematically linked and all of the resources we post will be as well. We will be releasing the resources roughly in the order that you should be reading them.
Each resource also has exercises to help clarify the key ideas and give practice with them. You can discuss the exercises by clicking either the "View Discussions" or "Start New Topic" button.
Eligibility
CrowdMath is designed to give very well-prepared high school students (as of 1/1/16) experience with math research. Very advanced middle school students are also welcome to participate. We know that the problems will be interesting to a broader range of people, but we want to create a specific opportunity for the upcoming generation of math and science researchers.
Be polite and constructive
This rule is simple, but important. The goal here is to learn to collaborate. Be nice!
Make your comments as easy to understand as possible
Polymath is a conversation. Assume that many people will be reading anything you write. Take a little time to make sure you write as clearly as possible and all of your collaborators will appreciate it.
Mentors
We have plenty of people watching and ready to help out when needed. However, we also know that there are many mathematicians out there who will find the CrowdMath project interesting and will want to help out. If you'd like to take part, send us a note at crowdmath@aops.com.
Dissemination of results and intellectual property
Polymath projects are inherently massively collaborative. Done correctly, it should be impossible to determine the lines between one person's work and the rest of the group. As such, we agree that the results created must be attributed to all CrowdMath contributors.
1 reply
Step 3 : Characterization
TropicalBlast 0
Aug 14, 2024
Step 3 : Characterization of P
Consider what kinds of patterns P would force the number of ones to be sparse.
Single ones: If P is a single 1 x 1 matrix with a single "1", ex(n, P) can be as large as n^2, since any placement of ones would avoid P trivially.
Row or column patterns: If P consists of a single row or a single column of ones then any n x n matrix with more than kn ones would necessarily contain a submatrix that matches P.
I am not sure whether this is method is correct? Can someone clarify?
Consider what kinds of patterns P would force the number of ones to be sparse.
Single ones: If P is a single 1 x 1 matrix with a single "1", ex(n, P) can be as large as n^2, since any placement of ones would avoid P trivially.
Row or column patterns: If P consists of a single row or a single column of ones then any n x n matrix with more than kn ones would necessarily contain a submatrix that matches P.
I am not sure whether this is method is correct? Can someone clarify?
0 replies
Problem 9 Important Results
iamgauss 4
N
Jan 11, 2019
by vkmathwhiz
As you may know, there is a thread for Problem 7 that lists all the important results discovered by CrowdMath for that problem. I thought it might be helpful to have a similar thread for the rest of the problems. Please add all important discoveries that have been made that are topical to Problem 9 here. Make sure to say where the theorems were proved and by whom. There are also threads for Problems 1-8. Thanks!
4 replies
Functional Reciprocal Theory
adityaguharoy 18
N
Aug 16, 2018
by alexanderoldspartan
Hello,
Here I am going to discuss a new theory and a quite useful way of solving inequality problems in which we use the Rearrangement inequality as a tool to develop a new type of inequality the Functional Reciprocal Sum inequality which is described as follows :
This work is authored by Aditya Guha Roy
If for a function over some subset we have
the pairs and are similarly sorted then we say that
is p-monotone over .
And if ,
the pairs and are oppositely sorted then we say that
is i-monotone over .
With this we have some lemmas :
Lemma 1 : (First Functional Reciprocal Sum Inequality (FRS 1)
If is p-monotone over and is i-monotone over then, we have the following inequality :
Sketch of Proof
Can we extend this to variables ?
If yes, how ?
Please help !!
Here I am going to discuss a new theory and a quite useful way of solving inequality problems in which we use the Rearrangement inequality as a tool to develop a new type of inequality the Functional Reciprocal Sum inequality which is described as follows :
This work is authored by Aditya Guha Roy
If for a function over some subset we have
the pairs and are similarly sorted then we say that
is p-monotone over .
And if ,
the pairs and are oppositely sorted then we say that
is i-monotone over .
With this we have some lemmas :
Lemma 1 : (First Functional Reciprocal Sum Inequality (FRS 1)
If is p-monotone over and is i-monotone over then, we have the following inequality :
Sketch of Proof
Use Rearrangement inequality over to establish the inequality and
use Rearrangement inequality over
to establish the inequality
and can be established using Rearrangement inequality or AM-GM inequality.
Problems
use Rearrangement inequality over
to establish the inequality
and can be established using Rearrangement inequality or AM-GM inequality.
Problems
We can solve many problems using this Lemma:
Problem 1
For all positive reals and all non-negative real numbers we have the following :
Problem 2
For all positive and all nonnegative we have
Problem 3 (CeuAzul)
For all acute angles
Problem 4
For all we have
Problem 1
For all positive reals and all non-negative real numbers we have the following :
Problem 2
For all positive and all nonnegative we have
Problem 3 (CeuAzul)
For all acute angles
Problem 4
For all we have
Can we extend this to variables ?
If yes, how ?
Please help !!
18 replies
Crowdmath 2018
Kayak 2
N
Jan 6, 2018
by devenware
When will it start ? Also, what are the topics for high schoolers ? How can they participate ?
2 replies
crowdmath survey
JGeneson 2
N
Sep 30, 2017
by JGeneson
Help improve CrowdMath for future generations of students! You are invited to take part in the first ever survey of CrowdMath participants, conducted by MIT PRIMES. All participants from 2016 and 2017 – from an active contributor to a casual visitor – are welcome. It’s a brief (10-15 min), fully anonymous, and fun survey about your experience on CrowdMath. The survey will close at the end of September, so please act fast. We look forward to hearing from you!
https://goo.gl/forms/zponMrhClu57tX8o1
https://goo.gl/forms/zponMrhClu57tX8o1
2 replies
Proposing problems
Kayak 0
Aug 15, 2017
Can I propose research problems - i.e problems which I find interesting and may have some good research value, to be researched collaboratively here ?
0 replies
alternative method for proving the Stanley-Wilf conjecture
JGeneson 3
N
Jul 20, 2017
by yugrey
The Stanley-Wilf conjecture states that for any fixed permutation of , there exists a constant such that the number of permutations of that avoid is at most .
Furedi and Hajnal made another conjecture that implies the Stanley-Wilf conjecture: for every permutation matrix . CrowdMath problem 2 is to improve the bounds on for every permutation matrix .
Klazar made another conjecture about partition avoidance that implies the Stanley-Wilf conjecture. We say that a partition of contains a partition of if there exists a subpartition of that has the same relative order as . Klazar conjectured that if avoids and , where denotes a separation between parts, then there exists a constant such that the number of partitions of avoiding is at most .
http://kam.mff.cuni.cz/~klazar/cpfsp1.pdf page 4
Marcus and Tardos proved the Stanley-Wilf conjecture by proving the Furedi-Hajnal conjecture. Klazar's conjecture remains open, and was recently listed with several other conjectures in the paper below:
https://arxiv.org/pdf/1608.02279v1.pdf
If you have ideas or questions about these papers or the conjectures, please post them here. A solution to Klazar's conjecture could imply improved bounds on the constants in the Stanley-Wilf conjecture.
Furedi and Hajnal made another conjecture that implies the Stanley-Wilf conjecture: for every permutation matrix . CrowdMath problem 2 is to improve the bounds on for every permutation matrix .
Klazar made another conjecture about partition avoidance that implies the Stanley-Wilf conjecture. We say that a partition of contains a partition of if there exists a subpartition of that has the same relative order as . Klazar conjectured that if avoids and , where denotes a separation between parts, then there exists a constant such that the number of partitions of avoiding is at most .
http://kam.mff.cuni.cz/~klazar/cpfsp1.pdf page 4
Marcus and Tardos proved the Stanley-Wilf conjecture by proving the Furedi-Hajnal conjecture. Klazar's conjecture remains open, and was recently listed with several other conjectures in the paper below:
https://arxiv.org/pdf/1608.02279v1.pdf
If you have ideas or questions about these papers or the conjectures, please post them here. A solution to Klazar's conjecture could imply improved bounds on the constants in the Stanley-Wilf conjecture.
3 replies
Fulek: Forbidden Patterns in 0-1 Matrices - Exercise B
Plasma_Vortex 72
N
Feb 12, 2017
by Thothdragonfly2
What is the maximum number of ones in an matrix avoiding ?
72 replies
Question
Thothdragonfly2 5
N
Feb 11, 2017
by Thothdragonfly2
For a matrix A to contain a pattern B, could we both find a submatrix of A and change 1 entries to 0 entries, or just one of the two?
I am new to this, so thanks!
I am new to this, so thanks!
5 replies
Problem 8 Important Results
iamgauss 3
N
Dec 31, 2016
by JGeneson
As you may know, there is a thread for Problem 7 that lists all the important results discovered by CrowdMath for that problem. I thought it might be helpful to have a similar thread for the rest of the problems. Please add all important discoveries that have been made that are topical to Problem 8 here. Make sure to say where the theorems were proved and by whom. There are also threads for Problems 1-7 and 9. Thanks!
3 replies
alternative method for proving the Stanley-Wilf conjecture
JGeneson 3
N
Jul 20, 2017
by yugrey
The Stanley-Wilf conjecture states that for any fixed permutation of , there exists a constant such that the number of permutations of that avoid is at most .
Furedi and Hajnal made another conjecture that implies the Stanley-Wilf conjecture: for every permutation matrix . CrowdMath problem 2 is to improve the bounds on for every permutation matrix .
Klazar made another conjecture about partition avoidance that implies the Stanley-Wilf conjecture. We say that a partition of contains a partition of if there exists a subpartition of that has the same relative order as . Klazar conjectured that if avoids and , where denotes a separation between parts, then there exists a constant such that the number of partitions of avoiding is at most .
http://kam.mff.cuni.cz/~klazar/cpfsp1.pdf page 4
Marcus and Tardos proved the Stanley-Wilf conjecture by proving the Furedi-Hajnal conjecture. Klazar's conjecture remains open, and was recently listed with several other conjectures in the paper below:
https://arxiv.org/pdf/1608.02279v1.pdf
If you have ideas or questions about these papers or the conjectures, please post them here. A solution to Klazar's conjecture could imply improved bounds on the constants in the Stanley-Wilf conjecture.
Furedi and Hajnal made another conjecture that implies the Stanley-Wilf conjecture: for every permutation matrix . CrowdMath problem 2 is to improve the bounds on for every permutation matrix .
Klazar made another conjecture about partition avoidance that implies the Stanley-Wilf conjecture. We say that a partition of contains a partition of if there exists a subpartition of that has the same relative order as . Klazar conjectured that if avoids and , where denotes a separation between parts, then there exists a constant such that the number of partitions of avoiding is at most .
http://kam.mff.cuni.cz/~klazar/cpfsp1.pdf page 4
Marcus and Tardos proved the Stanley-Wilf conjecture by proving the Furedi-Hajnal conjecture. Klazar's conjecture remains open, and was recently listed with several other conjectures in the paper below:
https://arxiv.org/pdf/1608.02279v1.pdf
If you have ideas or questions about these papers or the conjectures, please post them here. A solution to Klazar's conjecture could imply improved bounds on the constants in the Stanley-Wilf conjecture.
3 replies