MIT PRIMES/Art of Problem Solving
CROWDMATH 2017: Graph Algorithms & Applications
No tags match your search
Mgraph theory
Nowakowski
algorithm
Komarov
Dean
probability
cop-and-robber
cop-and-killer
Felsner
function
geometry
Blinovsky
Hartke
Nowakowski - Exercise A
calculus
geometric transformation
Komarov - Exercise C
Nowakowski - Exercise B
Problem 8
rectangle
rotation
3D geometry
analytic geometry
Blinovsky - Exercise A
Blinovsky - Exercise B
cop-and-pilferer
cop-vs-hypnostist
cop-vs-illusionist
Dean - Exercise A
derivative
Felsner - Exercise A
Hartke - Exercise A
integration
Komarov - Exercise B
magical opponents
parameterization
Problem 1
Problem 11
Problem 7
retract
Sawhney
Sawhney - Exercise A
set theory
tetrahedron
Thickness
No tags match your search
MG
Topic
First Poster
Last Poster
k i Welcome to Crowdmath
CrowdMath 0
Dec 19, 2016
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 2017. 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/17) 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 in early 2017. 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/17) 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.
0 replies
A procedure for finding winning strategies in cop-v-killer
rauss 1
N
Mar 9, 2018
by rauss
I've altered the procedure from Vertex-to-Vertex Pursuit in a Graph to model the cop-vs-killer game. I've attached a sketch of the definition and a python file modelling it for graphs represented as adjacency lists.
1 reply
The 2017 CrowdMath PRIMES prizes
JGeneson 13
N
Dec 27, 2017
by JGeneson
The MIT Program for Research in Math, Engineering, and Science (PRIMES) will award PRIMES internships to the two highest ranked participants in CrowdMath 2017 who are still in high school in Spring 2018. These students will have the opportunity to work on a research project on Skype with a mentor at MIT through PRIMES in 2018. One student will be chosen from each of the Graph Algorithms and Applications and Broken Stick projects.
CrowdMath is an online research program open to high school and college students all over the world. High school students can improve their CrowdMath rankings by posting questions, answers, ideas, or proofs on the CrowdMath message board. The rankings for the 2017 CrowdMath PRIMES prizes will be based on CrowdMath posts during the year 2017 and will be finalized on December 31, 2017. Rankings will be posted below and updated monthly.
CrowdMath is an online research program open to high school and college students all over the world. High school students can improve their CrowdMath rankings by posting questions, answers, ideas, or proofs on the CrowdMath message board. The rankings for the 2017 CrowdMath PRIMES prizes will be based on CrowdMath posts during the year 2017 and will be finalized on December 31, 2017. Rankings will be posted below and updated monthly.
13 replies
Retracts and the Cop and Killer game
goodbear 7
N
Dec 26, 2017
by JGeneson
I have some additional results on the cop and killer game, with the intent of being able to characterize outcomes using retracts of the original graphs. Because I used some features of LaTeX not available on AoPS (such as defining some of the symbols I use), I'm just attaching the PDF here for now; if I have time later I'll convert to inline BBCode and update this post.
7 replies
Cop-Win Graph Properties
iammosespaulr 9
N
Dec 2, 2017
by JGeneson
For the cop to force a win situation the cop must be able to get the thief irrespective of the thief's choice to surrender.For cyclic graphs where there are no dominated vertices (one whose closed neighborhood is a subset of another vertex's neighborhood) i.e cyclic graphs which have the number of vertices and have their vertices connected only by the boundary of the cyclic structure , we find that the pilferer has a chance of completely evading the cop by just staying ahead of the cop this happens irrespective of the no of turns that he is given so the pilferer must win.We have already concluded that cyclic graphs which have vertex are pilferer win graphs so for the cop to win the graph must be a cyclic graph with or dismantle-able graph i.e it should be able to have a dominated vertex which can then be added or removed from the graph without affecting the end result to prove this let us assume the pilferer and the cop use their most effective strategies and they start in a cyclic graph with vertices, now adding a branch of length at point point such that there is an opportunity for the pilferer to get caught by entering the branch given that the branch terminates before he reaches turns, but since both the cop and the pilferer are using their effective strategies the pilferer will continue to evade the police by not entering the branch thereby producing the same result we had earlier i.e resulting in the pilferer evading the cop ,from this we could conclude that adding a branch which is essentially a chain of dominated vertices to a point on the graph does not change the outcome hence it must also be true for the converse leading the outcome to be unaffected even if you remove dominated vertices .Since we are allowed only turns the distance that the pilferer is allowed to travel must be for a non-cyclic graph i.e terminating branched graphs.
I had written a simulation that would give the shortest route by mapping the various paths between the pilferer and the cop ,i may post it soon ..
I had written a simulation that would give the shortest route by mapping the various paths between the pilferer and the cop ,i may post it soon ..
9 replies
cop vs robber in a maze
JGeneson 16
N
Nov 21, 2017
by JGeneson
Let be a connected region in the plane. Suppose that the cop is a segment of length and the robber is a segment of length .
The cop starts inside (so we assume that a segment of length fits somewhere inside ), as does the robber. Based on , , , and the initial positions, does the cop catch the robber if both use optimal play?
A good place to start might be regions where all sides are parallel to the coordinate axes.
How does the result change if the cop and robber are circles or squares instead of segments?
What if the game is played inside connected regions in space?
The cop starts inside (so we assume that a segment of length fits somewhere inside ), as does the robber. Based on , , , and the initial positions, does the cop catch the robber if both use optimal play?
A good place to start might be regions where all sides are parallel to the coordinate axes.
How does the result change if the cop and robber are circles or squares instead of segments?
What if the game is played inside connected regions in space?
16 replies
problems about point visibility graphs
JGeneson 2
N
Nov 13, 2017
by JGeneson
https://arxiv.org/pdf/1711.01811.pdf
This recent arxiv paper shows NP-hardness for the following problems on point visibility graphs:
Feedback Vertex Set
Longest Induced Path
Bisection
F-free Vertex Deletion (for certain sets F)
(Point visibility graphs are graphs induced by a set of points in the plane where the graph's vertices represent the points in the plane and two vertices are adjacent if and only if no other point lies on the line segment between the points.)
The paper mentions some cool open problems about point visibility graphs:
A dominating set is a set of vertices in a graph such that every vertex in the graph is in the set or has a neighbor in the set.
OPEN PROBLEM 1: Does every point visibility graph with vertices have a dominating set of size ?
OPEN PROBLEM 2: What is the computational complexity of the problems Dominating Set and Max Cut for point visibility graphs?
This recent arxiv paper shows NP-hardness for the following problems on point visibility graphs:
Feedback Vertex Set
Longest Induced Path
Bisection
F-free Vertex Deletion (for certain sets F)
(Point visibility graphs are graphs induced by a set of points in the plane where the graph's vertices represent the points in the plane and two vertices are adjacent if and only if no other point lies on the line segment between the points.)
The paper mentions some cool open problems about point visibility graphs:
A dominating set is a set of vertices in a graph such that every vertex in the graph is in the set or has a neighbor in the set.
OPEN PROBLEM 1: Does every point visibility graph with vertices have a dominating set of size ?
OPEN PROBLEM 2: What is the computational complexity of the problems Dominating Set and Max Cut for point visibility graphs?
2 replies
graph pursuit paper
JGeneson 0
Nov 1, 2017
The first paper from this CrowdMath project is now on arxiv: https://arxiv.org/abs/1710.11352
There are many more unsolved problems about graph pursuit algorithms and visibility graphs that you can still work on. See this page for a partial list of open problems.
There are many more unsolved problems about graph pursuit algorithms and visibility graphs that you can still work on. See this page for a partial list of open problems.
0 replies
Cop-and-killer game
cjquines0 96
N
Oct 16, 2017
by JGeneson
Consider the following generalization of the cop-and-robber game which is more symmetric. Our two players are now a cop and a killer, also a perfect information game. The cop picks a vertex and the killer also picks a vertex. Then the game begins, with the cop going first. He moves to an adjacent vertex, followed by the killer moving to an adjacent vertex. If after the cop moves he occupies the vertex the killer is located, he wins. Similarly, if after the killer moves, she occupies the vertex the cop is located, she wins. If neither happens after a finite amount of turns, it is a stalemate.
Some initial results.
Clearly all graphs with a universal vertex are cop-win.
All trees which are not stars are killer-win.
Sketch
(A cop-win graph in the dismantlable sense is not always a cop-win graph in the cop-killer sense.)
Clearly the triangle is cop-win. Also, the four-cycle is killer-win. Cycles with more than five vertices are stalemate graphs.
Sketch
(This is clearly different from the cop-robber game, in that the killer wins in the four-cycle.)
Grid graphs are killer-win, but king's graphs (with dimension at least two) are stalemate graphs.
Sketch
(Direct products don’t seem to have any connection, unlike cop-robber graphs.)
Some initial results.
Clearly all graphs with a universal vertex are cop-win.
All trees which are not stars are killer-win.
Sketch
Suppose the cop has picked a vertex, which we will root the tree at. The killer picks a vertex with distance two to the vertex the cop picked, which is possible as the tree is not a star. When the game begins, after each cop move, the killer moves toward the cop (there is only one possible move); thus the distance between them after this is still two, assuming the cop does not move backwards. The cop can only move forward for a finite number of moves as the graph does not contain a cycle, so eventually he will reach a leaf node. The cop then moves away from the leaf node, and is adjacent to the killer, after which the killer moves to the cop’s vertex and wins.
(A cop-win graph in the dismantlable sense is not always a cop-win graph in the cop-killer sense.)
Clearly the triangle is cop-win. Also, the four-cycle is killer-win. Cycles with more than five vertices are stalemate graphs.
Sketch
For the former, the killer picks the opposite corner of the four-cycle and wins next turn. For the latter, killer picks vertex of distance two from cop, and moves so that they are never adjacent, neither player can win.
(This is clearly different from the cop-robber game, in that the killer wins in the four-cycle.)
Grid graphs are killer-win, but king's graphs (with dimension at least two) are stalemate graphs.
Sketch
For the former, killer chooses opposite corner of a four-cycle the cop is currently in. Killer mirrors cop's moves, maintaining distance two until cop is forced into corner, in which case killer wins next turn. For the latter, each player just maintains distance two from the other.
(Direct products don’t seem to have any connection, unlike cop-robber graphs.)
96 replies
Maximum number of edges in a rectangle k-visibility graph
JGeneson 90
N
Oct 6, 2017
by goodbear
Is the maximum possible number of edges in a rectangle -visibility graph with vertices at most twice the maximum possible number of edges in a bar -visibility graph with vertices?
Why or why not?
Why or why not?
90 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
Cop-Win Graph Properties
iammosespaulr 9
N
Dec 2, 2017
by JGeneson
For the cop to force a win situation the cop must be able to get the thief irrespective of the thief's choice to surrender.For cyclic graphs where there are no dominated vertices (one whose closed neighborhood is a subset of another vertex's neighborhood) i.e cyclic graphs which have the number of vertices and have their vertices connected only by the boundary of the cyclic structure , we find that the pilferer has a chance of completely evading the cop by just staying ahead of the cop this happens irrespective of the no of turns that he is given so the pilferer must win.We have already concluded that cyclic graphs which have vertex are pilferer win graphs so for the cop to win the graph must be a cyclic graph with or dismantle-able graph i.e it should be able to have a dominated vertex which can then be added or removed from the graph without affecting the end result to prove this let us assume the pilferer and the cop use their most effective strategies and they start in a cyclic graph with vertices, now adding a branch of length at point point such that there is an opportunity for the pilferer to get caught by entering the branch given that the branch terminates before he reaches turns, but since both the cop and the pilferer are using their effective strategies the pilferer will continue to evade the police by not entering the branch thereby producing the same result we had earlier i.e resulting in the pilferer evading the cop ,from this we could conclude that adding a branch which is essentially a chain of dominated vertices to a point on the graph does not change the outcome hence it must also be true for the converse leading the outcome to be unaffected even if you remove dominated vertices .Since we are allowed only turns the distance that the pilferer is allowed to travel must be for a non-cyclic graph i.e terminating branched graphs.
I had written a simulation that would give the shortest route by mapping the various paths between the pilferer and the cop ,i may post it soon ..
I had written a simulation that would give the shortest route by mapping the various paths between the pilferer and the cop ,i may post it soon ..
9 replies