Conjecture Can the approximation ratio be improved for the Maximum Edge Disjoint Paths problem (MaxEDP) in planar graphs or can an inapproximability result stronger than -hardness?
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 If is a finite field with at least 4 elements and is an invertible matrix with entries in , then there are column vectors which have no coordinates equal to zero such that .
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.
Conjecture Let be a simple graph with vertices and list chromatic number . Suppose that and each vertex of is assigned a list of colors. Then at least vertices of can be colored from these lists.
Problem Consider the set of all topologically inequivalent polyhedra with edges. Define a form parameter for a polyhedron as where is the number of vertices. What is the distribution of for ?
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 ?
Begin with the generating function for unrestricted partitions:
(1+x+x^2+...)(1+x^2+x^4+...)(1+x^3+x^6+...)...
Now change some of the plus signs to minus signs. The resulting series will have coefficients congruent, mod 2, to the coefficients of the generating series for unrestricted partitions. I conjecture that the signs may be chosen such that all the coefficients of the series are either 1, -1, or zero.