An alternating walk in a digraph is a walk so that the vertex is either the head of both and or the tail of both and for every . A digraph is universal if for every pair of edges , there is an alternating walk containing both and
Question Does there exist a locally finite highly arc transitive digraph which is universal?
Conjecture For every fixed graph , there exists a constant , so that every graph without an induced subgraph isomorphic to contains either a clique or an independent set of size .
Conjecture Every complete geometric graph with an even number of vertices has a partition of its edge set into plane (i.e. non-crossing) spanning trees.
Throughout this post, by projective plane we mean the set of all lines through the origin in .
Definition Say that a subset of the projective plane is octahedral if all lines in pass through the closure of two opposite faces of a regular octahedron centered at the origin.
Definition Say that a subset of the projective plane is weakly octahedral if every set such that is octahedral.
Conjecture Suppose that the projective plane can be partitioned into four sets, say and such that each set is weakly octahedral. Then each is octahedral.
Problem Is there a minimum integer such that the vertices of any digraph with minimum outdegree can be partitioned into two classes so that the minimum outdegree of the subgraph induced by each class is at least ?
Question Is the binary affine cube the only 3-connected matroid for which equality holds in the bound where is the circumference (i.e. largest circuit size) of ?
The crossing number of is the minimum number of crossings in all drawings of in the plane.
The -dimensional (hyper)cube is the graph whose vertices are all binary sequences of length , and two of the sequences are adjacent in if they differ in precisely one coordinate.
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.
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 Let be a sequence of points in with the property that for every , the points are distinct, lie on a unique sphere, and further, is the center of this sphere. If this sequence is periodic, must its period be ?
Problem Is there an algorithm which takes as input a triangulated 4-manifold, and determines whether or not this manifold is combinatorially equivalent to the 4-sphere?
Conjecture Let if is odd and if is even. Let . Assume we start with some number and repeatedly take the of the current number. Prove that no matter what the initial number is we eventually reach .
Question What is the least integer such that every set of at least points in the plane contains collinear points or a subset of points in general position (no three collinear)?