The time is now - Spring classes are filling up!

MIT PRIMES/Art of Problem Solving

CROWDMATH 2019: Graph Coloring

G
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.
3 replies
CrowdMath
Dec 28, 2018
TheMath_boy
Nov 29, 2019
Maths trigonometry
AlbatrossX   4
N Sep 30, 2023 by Serengeti22
Find no of solutions of since=X/10
4 replies
AlbatrossX
Feb 10, 2019
Serengeti22
Sep 30, 2023
Question
Jwenslawski   7
N Nov 1, 2022 by charlivenum
What is Graph Coloring?
7 replies
Jwenslawski
Nov 26, 2021
charlivenum
Nov 1, 2022
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.
0 replies
GlanePito
May 18, 2021
0 replies
Problem 4: outline
notethanol   1
N Dec 16, 2019 by JGeneson
EFL segment conjecture: Let $M$ be a set of $m$ segments such that every pair has at most one point in common. Then, $M$ has an EFL coloring with $m$ 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 $M$ colored.
1 reply
notethanol
Dec 14, 2019
JGeneson
Dec 16, 2019
Equivalence of EFL Conjecture and curve EFL conjecture
notethanol   1
N Dec 9, 2019 by JGeneson
EFL conjecture: Let $G$ be a graph consisting of $m$ copies of $K_m$, every pair of which has at most one vertex in common. Then, $\chi(G) = m$.

Curve EFL conjecture: Let $M$ be a set of $m$ curves such that every pair has at most one point in common. Then, $M$ has an EFL coloring with $m$ colors.

EFL conjecture $\implies$ Curve EFL conjecture

Within any given set of curves, imaginary points can be added to each curve so that Graph $G$ is composed of $m$
$K_m$'s while also ensuring that each $K_m$ has a maximum of one intersection. Thus, the EFL conjecture implies the Curve EFL conjecture.

Curve EFL conjecture $\implies$ EFL conjecture

Within any graph $G$, m curves (1, . . . , m) can be added so that each $K_i$'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
notethanol
Dec 1, 2019
JGeneson
Dec 9, 2019
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.
3 replies
notethanol
Oct 19, 2019
JGeneson
Dec 9, 2019
formation width algorithm
JGeneson   2
N Dec 9, 2019 by JGeneson
Definitions
An $(r,s)$-formation is a concatenation of $s$ permutations of $r$ letters, e.g. $a b c c b a a b c a c b$ is a $(3, 4)$-formation.

For every sequence $u$ define $fw(u)$, the formation width of $u$, to be the minimum $s$ for which there exists $r$ such that there is a subsequence isomorphic to $u$ in every $(r,s)$-formation.

Problem:
In the first $2$ papers on $fw$ (https://arxiv.org/abs/1308.3810 and https://arxiv.org/abs/1502.04095), we found an algorithm to calculate $fw(u)$ for any sequence $u$.

The algorithm in the second paper is faster than the first, but both algorithms are very slow. Find a faster algorithm to compute $fw(u)$.

Notes
Both papers have Python formation width algorithms at the end.

Suppose that $I_{c} = 1 2 \dots c$ and $D_{c} = c (c-1) \dots 1$. A formation with all permutations equal to $I_{c}$ or $D_{c}$ for some $c$ is called a binary formation.

The key fact used for both algorithms is Corollary 12 in the first paper:

If $u$ has $r$ distinct letters, then every binary $(r, s)$-formation contains $u$ if and only if $s \geq fw(u)$.

Algorithm for calculating $fw(u)$:
Let $r$ be the number of distinct letters in $u$. Starting with $s = 1$, check if every binary $(r, s)$-formation contains $u$. If so, output $s$ and halt. Otherwise increment $s$ and repeat.
2 replies
JGeneson
Dec 29, 2018
JGeneson
Dec 9, 2019
formation width algorithm for 3-letter sequences
JGeneson   2
N Dec 9, 2019 by JGeneson
For definition of $fw(u)$, see the Problems page.

One of the problems for $fw(u)$ is to find an algorithm to compute $fw(u)$ that is polynomial-time in the length of $u$. There is already a polynomial-time algorithm for $fw(u)$ when $u$ has two distinct letters. Is there a polynomial-time algorithm for $fw(u)$ for sequences $u$ with three distinct letters?
2 replies
JGeneson
Nov 19, 2019
JGeneson
Dec 9, 2019
probabilistic algorithms for computing formation width
JGeneson   2
N Nov 26, 2019 by solvingking
For definition of $fw(u)$, see the Problems page.

Any ideas for probabilistic algorithms for computing $fw(u)$?

For example, how accurate a value can we get for $fw(u)$ by checking only a random subset of the binary formations with $s$ permutations instead of the full set of binary formations with $s$ permutations in order to to compute $fw(u)$?
2 replies
JGeneson
Nov 19, 2019
solvingking
Nov 26, 2019
complexity of formation width decision problem
JGeneson   1
N Nov 25, 2019 by JGeneson
Is it possible to prove complexity results about formation width?

For example, what can we say about the complexity of the formation width decision problem:

Given a sequence $u$ and an integer $k$, is $fw(u)  \leq k$?
1 reply
JGeneson
Nov 19, 2019
JGeneson
Nov 25, 2019
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.
3 replies
notethanol
Oct 19, 2019
JGeneson
Dec 9, 2019
a