The time is now - Spring classes are filling up!

MIT PRIMES/Art of Problem Solving

CROWDMATH 2016: Pattern Avoidance

G
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.
1 reply
JGeneson
Jan 22, 2017
JGeneson
Apr 19, 2017
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.
2 replies
JGeneson
Jan 22, 2017
JGeneson
Apr 19, 2017
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.
4 replies
JGeneson
Nov 26, 2016
JGeneson
Jan 4, 2017
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.
1 reply
CrowdMath
Dec 22, 2015
copeland
Mar 14, 2016
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?
0 replies
TropicalBlast
Aug 14, 2024
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
iamgauss
Apr 29, 2016
vkmathwhiz
Jan 11, 2019
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 $f: \mathbb{R^+} \to \mathbb{R^+}$ over some subset $S \subseteq \mathbb{R^+}$ we have
$\bullet$ $\forall x \in S , \forall y \in S$ the pairs $(f(x) \cdot x , f(y) \cdot y)$ and $(\frac{f(x)}{x} , \frac{f(y)}{y})$ are similarly sorted then we say that
$f:$ is p-monotone over $S$.
And if ,
$\bullet$ $\forall x \in S , \forall y \in S$ the pairs $(f(x) \cdot x , f(y) \cdot y)$ and $(\frac{f(x)}{x} , \frac{f(y)}{y})$ are oppositely sorted then we say that
$f:$ is i-monotone over $S$.

With this we have some lemmas :

Lemma 1 : (First Functional Reciprocal Sum Inequality (FRS 1)
If $f: \mathbb{R^+} \to \mathbb{R^+}$ is p-monotone over $S \subseteq \mathbb{R^+}$ and $g:\mathbb{R^+}\to \mathbb{R^+}$ is i-monotone over $S$ then, we have the following inequality :
$2 \le \frac{g(x)}{g(y)}+\frac{g(y)}{g(x)} \le \frac{x}{y}+\frac{y}{x} \le \frac{f(x)}{f(y)}+\frac{f(y)}{f(x)}$
Sketch of Proof


Can we extend this to $3$ variables ?
If yes, how ?
Please help !!
18 replies
adityaguharoy
Nov 21, 2016
alexanderoldspartan
Aug 16, 2018
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
Kayak
Dec 10, 2017
devenware
Jan 6, 2018
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
2 replies
JGeneson
Sep 22, 2017
JGeneson
Sep 30, 2017
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
Kayak
Aug 15, 2017
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 $\pi$ of $1, \ldots, k$, there exists a constant $c$ such that the number of permutations of $1, \ldots, n$ that avoid $\pi$ is at most $c^{n}$.

Furedi and Hajnal made another conjecture that implies the Stanley-Wilf conjecture: $ex(n, P) = O(n)$ for every permutation matrix $P$. CrowdMath problem 2 is to improve the bounds on $ex(n, P)$ for every permutation matrix $P$.

Klazar made another conjecture about partition avoidance that implies the Stanley-Wilf conjecture. We say that a partition $\sigma$ of $[n]$ contains a partition $\tau$ of $[k]$ if there exists a subpartition $\sigma'$ of $\sigma$ that has the same relative order as $\tau$. Klazar conjectured that if $\tau$ avoids $123$ and $12 / 34$, where $/$ denotes a separation between parts, then there exists a constant $c$ such that the number of partitions of $[n]$ avoiding $\tau$ is at most $c^{n}$.

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
JGeneson
Sep 8, 2016
yugrey
Jul 20, 2017
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 $n\times n$ matrix avoiding $L1$?
\[
L1=\begin{pmatrix}
&\bullet&\bullet&\\
\bullet&&&\bullet\\
&\bullet&&
\end{pmatrix}
\]
72 replies
Plasma_Vortex
Dec 23, 2015
Thothdragonfly2
Feb 12, 2017
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!
5 replies
Thothdragonfly2
Feb 10, 2017
Thothdragonfly2
Feb 11, 2017
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
iamgauss
Apr 29, 2016
JGeneson
Dec 31, 2016
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?
0 replies
TropicalBlast
Aug 14, 2024
0 replies
Step 3 : Characterization
j G H J
G H BBookmark kLocked kLocked NReply
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
TropicalBlast
1 post
#1
This topic is linked to Problem 1.
Y by
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?
This post has been edited 1 time. Last edited by TropicalBlast, Aug 14, 2024, 6:11 PM
Reason: not sure whether the method used is correct.
Z K Y
N Quick Reply
G
H
=
a