The famous 0-1 Knapsack problem is: Given and integers, determine whether or not there are values so that The best known worst-case algorithm runs in time times a polynomial in . Is there an algorithm that runs in time ?
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 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 ?
Conjecture There is an integer-valued function such that if is any -connected graph and and are any two vertices of , then there exists an induced path with ends and such that is -connected.
Conjecture Let be an eulerian graph of minimum degree , and let be an eulerian tour of . Then admits a decomposition into cycles none of which contains two consecutive edges of .
For and positive integers, the (mixed) van der Waerden number is the least positive integer such that every (red-blue)-coloring of admits either a -term red arithmetic progression or an -term blue arithmetic progression.
Let be a non-empty finite set. Given a partition of , the stabilizer of , denoted , is the group formed by all permutations of preserving each block of .
Problem () Find a sufficient condition for a sequence of partitions of to be complete, i.e. such that the product of their stabilizers is equal to the whole symmetric group on . In particular, what about completeness of the sequence , given a partition of and a permutation of ?
Conjecture (Beneš) Let be a uniform partition of and be a permutation of such that . Suppose that the set is transitive, for some integer . Then
Conjecture Can all problems that can be computed by a probabilistic Turing machine (with error probability < 1/3) in polynomial time be solved by a deterministic Turing machine in polynomial time? That is, does P = BPP?
A friendly partition of a graph is a partition of the vertices into two sets so that every vertex has at least as many neighbours in its own class as in the other.
Problem Is it true that for every , all but finitely many -regular graphs have friendly partitions?
login/create account
and 
integers, determine whether or not there are 
values 
so that 
The best known worst-case algorithm runs in time 
times a polynomial in 
. Is there an algorithm that runs in time 
?
such that for every hexagonal graph 
and vertex weighting 
, 
.
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. 
such that if 
and 
are any two vertices of 
with ends 
is 
-connected. 
vertices, then 
. 
there is 
such that, for every large 
such that 
and 
. 
-flow. 
and a function 
such that if 
, then every saturated 
has cardinality at least 
? 
denote the 
diagonal 
exists. 
, and let 
be an eulerian tour of 
positive integers, the (mixed) van der Waerden number 
is the least positive integer ![$ [1,n] $](/files/tex/661d0acc09fbc5b62f49645a71cf7d831a26563f.png)
admits either a 
, 
. 
be a non-empty finite set. Given a partition 
of 
, is the group formed by all permutations of 
.
) Find a sufficient condition for a sequence of partitions 
of 
is equal to the whole symmetric group 
on 
, given a partition 
of 
be a uniform partition of 
be a permutation of 
. Suppose that the set 
is transitive, for some integer 
. Then 
is unfriendly if every vertex has at least as many neighbors in the other classes as in its own. 
for every endo-
? 
, all but finitely many 
be a digraph. If 
, then 
be abelian groups and let 
and 
satisfy 
and 
. If there is a 
to 
, then every graph with a B-flow has a B'-flow. 
edges whose deletion destroys every triangle. 
Drupal
CSI of Charles University