MIT PRIMES/Art of Problem Solving
CROWDMATH 2019: Graph Coloring
No tags match your search
MButler
graph theory
Graph coloring
probability
algorithm
Boris
zero forcing
algorithms
Berliner
algebra
ceiling function
clarification
combinatorics
expected value
polynomial
Problem 1
Problem 2
Problem 3
Berliner - Exercise A
Berliner - Exercise B
Berliner - Exercise B3
Boris - Exercise A
Boris - Exercise B
Boris - Exercise D
Butler - Exercise A1
Butler - Exercise A2
Butler - Exercise A3
Butler - Exercise A4
Butler - Exercise B1
Butler - Exercise B2
Butler - Exercise B3
Butler - Exercise B4
Butler - Exercise C1
Butler - Exercise C2
Butler - Exercise C3
Butler - Exercise C4
calculus
colorability
cycles
Date
function
Fw
geometric transformation
geometry
induction
intersections
Overview
paths
please help me
Problem 4
No tags match your search
MG
Topic
First Poster
Last Poster
i Welcome to CrowdMath
CrowdMath 3
N
Nov 29, 2019
by TheMath_boy
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 in early 2019. 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 and college students (as of 1/1/18) 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.
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 in early 2019. 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 and college students (as of 1/1/18) 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.
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.
3 replies
Maths trigonometry
AlbatrossX 4
N
Sep 30, 2023
by Serengeti22
Find no of solutions of since=X/10
4 replies
Complexity of graph coloring
GlanePito 0
May 18, 2021
Hi,
I can't get my head about complexity of graph coloring and wiki didn't really help me.
Here is what I think I know:
Generally, Coloring graph is NP-hard problem.
Coloring graph with 3 colors is NP-complete problem.
But I don't get how can it be harder to color a graph when you have more colors. Lets go to extreme, if I had a complete graph with 50 vertices and I had 5000 colors, I don't think it would be really hard to color this graph so graph-coloring properties are met (each vertex new color)... So how can the complexity arise when you have more colors.
I expect that problem/hardness of it is actually in coloring with specific K or maybe deciding what is the smallest K that graph can be colored... But I am not sure, and that is why I am asking for help and clarity.
I can't get my head about complexity of graph coloring and wiki didn't really help me.
Here is what I think I know:
Generally, Coloring graph is NP-hard problem.
Coloring graph with 3 colors is NP-complete problem.
But I don't get how can it be harder to color a graph when you have more colors. Lets go to extreme, if I had a complete graph with 50 vertices and I had 5000 colors, I don't think it would be really hard to color this graph so graph-coloring properties are met (each vertex new color)... So how can the complexity arise when you have more colors.
I expect that problem/hardness of it is actually in coloring with specific K or maybe deciding what is the smallest K that graph can be colored... But I am not sure, and that is why I am asking for help and clarity.
0 replies
Problem 4: outline
notethanol 1
N
Dec 16, 2019
by JGeneson
EFL segment conjecture: Let be a set of segments such that every pair has at most one point in common. Then, has an EFL coloring with colors.
The EFL segment conjecture is true in general: it can be applied to segments built on planar graphs.
Through a proof by Induction, the conjecture can be first proved for the base case. Then, by successively picking a segment that intersects a segment whose intersection points are already colored (starting with an arbitrary assignment of colors to intersection points of segments), an EFL coloring can be achieved--with all intersection points of colored.
The EFL segment conjecture is true in general: it can be applied to segments built on planar graphs.
Through a proof by Induction, the conjecture can be first proved for the base case. Then, by successively picking a segment that intersects a segment whose intersection points are already colored (starting with an arbitrary assignment of colors to intersection points of segments), an EFL coloring can be achieved--with all intersection points of colored.
1 reply
Equivalence of EFL Conjecture and curve EFL conjecture
notethanol 1
N
Dec 9, 2019
by JGeneson
EFL conjecture: Let be a graph consisting of copies of , every pair of which has at most one vertex in common. Then, .
Curve EFL conjecture: Let be a set of curves such that every pair has at most one point in common. Then, has an EFL coloring with colors.
EFL conjecture Curve EFL conjecture
Within any given set of curves, imaginary points can be added to each curve so that Graph is composed of
's while also ensuring that each has a maximum of one intersection. Thus, the EFL conjecture implies the Curve EFL conjecture.
Curve EFL conjecture EFL conjecture
Within any graph , m curves (1, . . . , m) can be added so that each 's intersections are intersections of the curves as well. Thus, the Curve EFL conjecture implies the EFL conjecture.
Since the two conjectures imply each other, they are equivalent.
Curve EFL conjecture: Let be a set of curves such that every pair has at most one point in common. Then, has an EFL coloring with colors.
EFL conjecture Curve EFL conjecture
Within any given set of curves, imaginary points can be added to each curve so that Graph is composed of
's while also ensuring that each has a maximum of one intersection. Thus, the EFL conjecture implies the Curve EFL conjecture.
Curve EFL conjecture EFL conjecture
Within any graph , m curves (1, . . . , m) can be added so that each 's intersections are intersections of the curves as well. Thus, the Curve EFL conjecture implies the EFL conjecture.
Since the two conjectures imply each other, they are equivalent.
1 reply
Equivalence of two conjectures
notethanol 3
N
Dec 9, 2019
by JGeneson
In Brimkov proposition 17, we are given that Conjecture 3 is true if and only if Conjecture 4 is true.
(Note that Conjecture 3 is the Line EFL Conjecture (or Conjecture A in the exercise): "Let M be a set of m lines drawn in the plane. Then, M has an EFL coloring with m colors")
(Also note that Conjecture 4 is the Segment EFL Conjecture (or Conjecture B in the exercise): "Let M be a set of m segments drawn in the plane. Then, M has an EFL coloring with m colors")
Thus, if Conjecture 3 is true, then Conjecture 4 is also true; if Conjecture 3 is false, then Conjecture 4 is also false. Since the 2 conjectures have the same truth values, it can be said that Conjectures 3 and 4 are equivalent.
(Note that Conjecture 3 is the Line EFL Conjecture (or Conjecture A in the exercise): "Let M be a set of m lines drawn in the plane. Then, M has an EFL coloring with m colors")
(Also note that Conjecture 4 is the Segment EFL Conjecture (or Conjecture B in the exercise): "Let M be a set of m segments drawn in the plane. Then, M has an EFL coloring with m colors")
Thus, if Conjecture 3 is true, then Conjecture 4 is also true; if Conjecture 3 is false, then Conjecture 4 is also false. Since the 2 conjectures have the same truth values, it can be said that Conjectures 3 and 4 are equivalent.
3 replies
formation width algorithm
JGeneson 2
N
Dec 9, 2019
by JGeneson
Definitions
An -formation is a concatenation of permutations of letters, e.g. is a -formation.
For every sequence define , the formation width of , to be the minimum for which there exists such that there is a subsequence isomorphic to in every -formation.
Problem:
In the first papers on (https://arxiv.org/abs/1308.3810 and https://arxiv.org/abs/1502.04095), we found an algorithm to calculate for any sequence .
The algorithm in the second paper is faster than the first, but both algorithms are very slow. Find a faster algorithm to compute .
Notes
Both papers have Python formation width algorithms at the end.
Suppose that and . A formation with all permutations equal to or for some is called a binary formation.
The key fact used for both algorithms is Corollary 12 in the first paper:
If has distinct letters, then every binary -formation contains if and only if .
Algorithm for calculating :
Let be the number of distinct letters in . Starting with , check if every binary -formation contains . If so, output and halt. Otherwise increment and repeat.
An -formation is a concatenation of permutations of letters, e.g. is a -formation.
For every sequence define , the formation width of , to be the minimum for which there exists such that there is a subsequence isomorphic to in every -formation.
Problem:
In the first papers on (https://arxiv.org/abs/1308.3810 and https://arxiv.org/abs/1502.04095), we found an algorithm to calculate for any sequence .
The algorithm in the second paper is faster than the first, but both algorithms are very slow. Find a faster algorithm to compute .
Notes
Both papers have Python formation width algorithms at the end.
Suppose that and . A formation with all permutations equal to or for some is called a binary formation.
The key fact used for both algorithms is Corollary 12 in the first paper:
If has distinct letters, then every binary -formation contains if and only if .
Algorithm for calculating :
Let be the number of distinct letters in . Starting with , check if every binary -formation contains . If so, output and halt. Otherwise increment and repeat.
2 replies
formation width algorithm for 3-letter sequences
JGeneson 2
N
Dec 9, 2019
by JGeneson
For definition of , see the Problems page.
One of the problems for is to find an algorithm to compute that is polynomial-time in the length of . There is already a polynomial-time algorithm for when has two distinct letters. Is there a polynomial-time algorithm for for sequences with three distinct letters?
One of the problems for is to find an algorithm to compute that is polynomial-time in the length of . There is already a polynomial-time algorithm for when has two distinct letters. Is there a polynomial-time algorithm for for sequences with three distinct letters?
2 replies
probabilistic algorithms for computing formation width
JGeneson 2
N
Nov 26, 2019
by solvingking
For definition of , see the Problems page.
Any ideas for probabilistic algorithms for computing ?
For example, how accurate a value can we get for by checking only a random subset of the binary formations with permutations instead of the full set of binary formations with permutations in order to to compute ?
Any ideas for probabilistic algorithms for computing ?
For example, how accurate a value can we get for by checking only a random subset of the binary formations with permutations instead of the full set of binary formations with permutations in order to to compute ?
2 replies
formation width algorithm for 3-letter sequences
JGeneson 2
N
Dec 9, 2019
by JGeneson
For definition of , see the Problems page.
One of the problems for is to find an algorithm to compute that is polynomial-time in the length of . There is already a polynomial-time algorithm for when has two distinct letters. Is there a polynomial-time algorithm for for sequences with three distinct letters?
One of the problems for is to find an algorithm to compute that is polynomial-time in the length of . There is already a polynomial-time algorithm for when has two distinct letters. Is there a polynomial-time algorithm for for sequences with three distinct letters?
2 replies