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?
login/create account
such that for any 
there is a sequence of tautologies of depth 
Frege system 
but requires exponential size 
proofs. 
-connected cubic graph on 
vertices admit a partition into 
? 
is a directed graph with smallest directed cut of size 
. The representation function 
for 
is given by the rule 
. We call 
is never 
.
to be the maximum degree, 
to be the size of the largest 
to be the chromatic number of 
for every graph 
and every positive integer 
so that every simple 
-regular graph 
has a 
with 
. 
of 
and a (non-proper) 
such that edges with the same colour do not cross with respect to 
for some edges 
, then 
and 
receive distinct colours. 
is the minimum integer 
be the graph obtained by subdividing each edge of 
such that for every graph 
has an acyclic induced subdigraph of order at least 
. 
for some filter objects 
, 
. Particularly, is this formula true for 
? 
for some filter objects 
so that every abelian group 
with 
so that the 
has no clique or independent set of size 
. 
(first time when the players occupy the same point) which can be achieved assuming the two players must adopt the same strategy? 
, it is impossible to cover a square of side greater than 
with 
unit squares. 
be an abelian group. Is the 
. 
be a 
is connected. Then 
directed paths. 
.
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. 
, that every sufficiently large 
vertices whose deletion results in a 
. 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.
\item 
is a fixed recursive set of integers.
in this language.
, there is no polynomial-time algorithm for the following problem.
on 
clauses drawn uniformly at random from the set of formulas on 
simultaneously satisfiable clauses. 
vertices which contains no complete 
hyperedges. 
vertices which contains no complete 
hyperedges. 
to the edges of 
-geodesic cycle is 
with 
so that 
has a 
. 
Drupal
CSI of Charles University