Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add Ramsey Numbers #5

Open
derrickstolee opened this issue Jul 24, 2018 · 0 comments
Open

Add Ramsey Numbers #5

derrickstolee opened this issue Jul 24, 2018 · 0 comments

Comments

@derrickstolee
Copy link
Member

Ramsey Numbers involve coloring the edges of a (hyper) graph while avoiding monochromatic subgraphs. These numbers grow very quickly, especially when considering the symmetries involved in the problem statement.

It would be interesting to see how Z3 can handle these symmetries, and how simply we can reproduce well-known Ramsey bounds. Possibly, we could extend known knowledge by hitting small cases of strange graphs.

One enormous challenge will be how we can organize the results. There are so many ways to discuss Ramsey numbers and the input space is so huge (once you generalize to arbitrary graphs) and there are many variations (size Ramsey, ordered Ramsey, etc.).

One approach would be to start replicating results from the Small Ramsey Numbers Dynamic Survey in small pieces. We will likely want to break the problem down into smaller pieces.

Proposal

Create a folder named r containing a README.md that describes Ramey numbers in general. That README.md describes the different variations and how they relate, and where they are located in subdirectories of r.

Examples: classical for standard Ramsey numbers, size for size Ramsey numbers, ordered for ordered Ramsey numbers, hyper for hypergraph Ramsey numbers, etc.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant