The time is now - Spring classes are filling up!

MIT PRIMES/Art of Problem Solving

CROWDMATH 2017: Graph Algorithms & Applications

G
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.
0 replies
CrowdMath
Dec 19, 2016
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
rauss
Jan 16, 2018
rauss
Mar 9, 2018
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.
13 replies
JGeneson
Dec 25, 2016
JGeneson
Dec 27, 2017
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
goodbear
Nov 24, 2017
JGeneson
Dec 26, 2017
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 $n>3$ 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 $n>3$ are pilferer win graphs so for the cop to win the graph must be a cyclic graph with $n\leq{3}$ 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 $n>{3}$ vertices, now adding a branch of length $p\leq{k/2}$ at point $L$ 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 $k/2$ 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 $k/2$ turns the distance that the pilferer is allowed to travel must be $\leq{k/2}$ 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 ..
9 replies
iammosespaulr
Nov 14, 2017
JGeneson
Dec 2, 2017
cop vs robber in a maze
JGeneson   16
N Nov 21, 2017 by JGeneson
Let $R$ be a connected region in the plane. Suppose that the cop is a segment of length $x$ and the robber is a segment of length $y$.

The cop starts inside $R$ (so we assume that a segment of length $x$ fits somewhere inside $R$), as does the robber. Based on $R$, $x$, $y$, and the initial positions, does the cop catch the robber if both use optimal play?

A good place to start might be regions $R$ 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
JGeneson
Aug 22, 2017
JGeneson
Nov 21, 2017
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 $n$ vertices have a dominating set of size $O(\log{n})$?

OPEN PROBLEM 2: What is the computational complexity of the problems Dominating Set and Max Cut for point visibility graphs?
2 replies
JGeneson
Nov 13, 2017
JGeneson
Nov 13, 2017
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.
0 replies
JGeneson
Nov 1, 2017
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.)
96 replies
cjquines0
Apr 23, 2017
JGeneson
Oct 16, 2017
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 $k$-visibility graph with $n$ vertices at most twice the maximum possible number of edges in a bar $k$-visibility graph with $n$ vertices?

Why or why not?
90 replies
JGeneson
Dec 28, 2016
goodbear
Oct 6, 2017
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
cop vs robber in a maze
JGeneson   16
N Nov 21, 2017 by JGeneson
Let $R$ be a connected region in the plane. Suppose that the cop is a segment of length $x$ and the robber is a segment of length $y$.

The cop starts inside $R$ (so we assume that a segment of length $x$ fits somewhere inside $R$), as does the robber. Based on $R$, $x$, $y$, and the initial positions, does the cop catch the robber if both use optimal play?

A good place to start might be regions $R$ 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
JGeneson
Aug 22, 2017
JGeneson
Nov 21, 2017
cop vs robber in a maze
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.
JGeneson
1096 posts
#1 • 3 Y
Y by goodbear, Adventure10, Mango247
Let $R$ be a connected region in the plane. Suppose that the cop is a segment of length $x$ and the robber is a segment of length $y$.

The cop starts inside $R$ (so we assume that a segment of length $x$ fits somewhere inside $R$), as does the robber. Based on $R$, $x$, $y$, and the initial positions, does the cop catch the robber if both use optimal play?

A good place to start might be regions $R$ 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?
Z K Y
G
H
=
a