Problem Find a constant such that for any there is a sequence of tautologies of depth that have polynomial (or quasi-polynomial) size proofs in depth Frege system but requires exponential size proofs.
Problem What is the largest connected planar graph of minimum degree 3 which has everywhere positive combinatorial curvature, but is not a prism or antiprism?
A -page book embedding of consists of a linear order of and a (non-proper) -colouring of such that edges with the same colour do not cross with respect to . That is, if for some edges , then and receive distinct colours.
One can think that the vertices are placed along the spine of a book, and the edges are drawn without crossings on the pages of the book.
The book thickness of , denoted by bt is the minimum integer for which there is a -page book embedding of .
Let be the graph obtained by subdividing each edge of exactly once.
Conjecture There is a function such that for every graph ,
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 .
Problem Two players start at a distance of 2 on an (undirected) line (so, neither player knows the direction of the other) and both move at a maximum speed of 1. What is the infimum expected meeting time (first time when the players occupy the same point) which can be achieved assuming the two players must adopt the same strategy?
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?
Question Is the MSO-alternation hierarchy strict for pictures that are balanced, in the sense that the width and the length are polynomially (or linearly) related.
Conjecture Let be a -connected cubic graph and let be a -regular subgraph such that is connected. Then has a cycle double cover which contains (i.e all cycles of ).
Conjecture For every graph without a bridge, there is a flow .
Conjecture There exists a map so that antipodal points of receive opposite values, and so that any three points which are equidistant on a great circle have values which sum to zero.
Problem Is it true for all , that every sufficiently large -connected graph without a minor has a set of vertices whose deletion results in a planar graph?
Question I've been working on this for a long time and I'm getting nowhere. Could you help me or at least tell me where to look for help. Suppose D is an m-by-m diagonal matrix with integer elements all . Suppose X is an m-by-n integer matrix . Consider the partitioned matrix M = [D X]. Obviously M has full row rank so it has a right inverse of rational numbers. The question is, under what conditions does it have an integer right inverse? My guess, which I can't prove, is that the integers in each row need to be relatively prime.
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.
The problem concerns the extension of Monadic Second Order Logic (over a binary relation representing the edge relation) with the following atomic formulas:
\item \item
where is a fixed recursive set of integers.
Let us fix and a closed formula in this language.
Conjecture Is it true that the validity of for a graph of tree-width at most can be tested in polynomial time in the size of ?
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 It has been shown that a -outerplanar embedding for which is minimal can be found in polynomial time. Does a similar result hold for -edge-outerplanar graphs?