Conjecture There exists a fixed constant so that every abelian group has a subset with so that the Cayley graph has no clique or independent set of size .
Conjecture If is a non-empty graph containing no induced odd cycle of length at least , then there is a -vertex colouring of in which no maximum clique is monochromatic.
Problem Let be a graph, a countable end of , and an infinite set of pairwise disjoint -rays in . Prove that there is a set of pairwise disjoint -rays that devours such that the set of starting vertices of rays in equals the set of starting vertices of rays in .
Given integers , the 2-stage Shuffle-Exchange graph/network, denoted , is the simple -regular bipartite graph with the ordered pair of linearly labeled parts and , where , such that vertices and are adjacent if and only if (see Fig.1).
Given integers , the -stage Shuffle-Exchange graph/network, denoted , is the proper (i.e., respecting all the orders) concatenation of identical copies of (see Fig.1).
Let be the smallest integer such that the graph is rearrangeable.
Conjecture Suppose runners having distinct constant speeds start at a common point and run laps on a circular track with circumference 1. Then for any given runner, there is a time at which that runner is distance at least (along the track) away from every other runner.
Problem What is the maximum number of colours needed to colour countries such that no two countries sharing a common border have the same colour in the case where each country consists of one region on earth and one region on the moon ?
Problem Let be a -dimensional smooth submanifold of , diffeomorphic to . By the Jordan-Brouwer separation theorem, separates into the union of two compact connected -manifolds which share as a common boundary. The Schoenflies problem asks, are these -manifolds diffeomorphic to ? ie: is unknotted?
Conjecture For which values of and are there bi-colored graphs on vertices and different colors with the property that all the monochromatic colorings have unit weight, and every other coloring cancels out?
Conjecture For every rational and every rational , there is no polynomial-time algorithm for the following problem.
Given is a 3SAT (3CNF) formula on variables, for some , and clauses drawn uniformly at random from the set of formulas on variables. Return with probability at least 0.5 (over the instances) that is typical without returning typical for any instance with at least simultaneously satisfiable clauses.
Conjecture Denote by the number of non-Hamiltonian 3-regular graphs of size , and similarly denote by the number of non-Hamiltonian 3-regular 1-connected graphs of size .
Note that the above is a generalization of monotone Galois connections (with and replaced with suprema and infima).
Then we have the following diagram:
What is at the node "other" in the diagram is unknown.
Conjecture "Other" is .
Question What repeated applying of and to "other" leads to? Particularly, does repeated applying and/or to the node "other" lead to finite or infinite sets?