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?
Conjecture Let be a graph and let such that for any pair there are edge-disjoint paths from to in . Then contains edge-disjoint trees, each of which contains .
Conjecture For every fixed and fixed colouring of with colours, there exists such that every colouring of the edges of contains either vertices whose edges are coloured according to or vertices whose edges are coloured with at most colours.
Problem Given a link in , let the symmetry group of be denoted ie: isotopy classes of diffeomorphisms of which preserve , where the isotopies are also required to preserve .
Now let be a hyperbolic link. Assume has the further `Brunnian' property that there exists a component of such that is the unlink. Let be the subgroup of consisting of diffeomorphisms of which preserve together with its orientation, and which preserve the orientation of .
There is a representation given by restricting the diffeomorphism to the . It's known that is always a cyclic group. And is a signed symmetric group -- the wreath product of a symmetric group with .
Problem Given two codes , their Tensor Product is the code that consists of the matrices whose rows are codewords of and whose columns are codewords of . The product is said to be robust if whenever a matrix is far from , the rows (columns) of are far from (, respectively).
The problem is to give a characterization of the pairs whose tensor product is robust.
Let denote the set of all permutations of . Let and denote respectively the number of increasing and the number of decreasing sequences of contiguous numbers in . Let denote the set of subsequences of with length at least three. Let denote .
A permutation is called a Roller Coaster permutation if . Let be the set of all Roller Coaster permutations in .
Conjecture For ,
\item If , then . \item If , then with .
Conjecture (Odd Sum conjecture) Given ,
\item If , then is odd for . \item If , then for all .
For any simple digraph , we let be the number of unordered pairs of nonadjacent vertices (i.e. the number of non-edges), and be the size of the smallest feedback edge set.
Conjecture If is a simple digraph without directed cycles of length , then .
A nowhere-zero -flow on is an orientation of together with a function from the edge set of into the real numbers such that , for all , and . The circular flow number of is inf has a nowhere-zero -flow , and it is denoted by .
A graph with maximum vertex degree is a class 1 graph if its edge chromatic number is .
Conjecture Let be an integer and a -regular graph. If is a class 1 graph, then .
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?
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?
An -factor in a graph is a set of vertex-disjoint copies of covering all vertices of .
Problem Let be a fixed positive real number and a fixed graph. Is it NP-hard to determine whether a graph on vertices and minimum degree contains and -factor?
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?
login/create account
is a 
-connected finite graph, is there an assignment of lengths 
to the edges of 
-geodesic cycle is 
there is an integer 
such that every set of at least 
such that for any pair 
there are 
edge-disjoint paths from 
to 
in 
edge-disjoint trees, each of which contains 
. 
for every endo-
? 
hyperplanes in dimension 
is not greater than 
be an integer and let 
denote the least integer 
and fixed colouring 
of 
with 
colours, there exists 
such that every colouring of the edges of 
contains either 
vertices whose edges are coloured with at most 
colours. 
in 
, let the symmetry group of 
ie: isotopy classes of diffeomorphisms of 
of 
is the unlink. Let 
be the subgroup of 
consisting of diffeomorphisms of 
given by restricting the diffeomorphism to the 
is a signed symmetric group -- the wreath product of a symmetric group with 
. 
, their Tensor Product 
is the code that consists of the matrices whose rows are codewords of 
and whose columns are codewords of 
. The product 
is far from 
denote the set of all permutations of ![$ [n]=\set{1,2,\ldots,n} $](/files/tex/470bd09059264370b76b4da90b77dc370c7e0e7c.png)
. Let 
and 
denote respectively the number of increasing and the number of decreasing sequences of contiguous numbers in 
. Let 
denote the set of subsequences of 
denote 
.
is called a Roller Coaster permutation if 
. Let 
be the set of all Roller Coaster permutations in 
,
, then 
. \item If 
, then 
with 
. 
,
is odd for 
. \item If 
for all 
. The chromatic number of its square is
if 
, \item at most 
if 
, \item at most 
if 
. 
has a Hamilton cycle. 
-
of 
so that 
is 
-edge-connected and 
is 
-edge-connected? 
be the number of unordered pairs of nonadjacent vertices (i.e. the number of non-edges), and 
be the size of the smallest 
, then 
. 
-flow 
on 
of 
from the edge set of 
, for all 
, and 
. The circular flow number of 
has a nowhere-zero 
, and it is denoted by 
.
be an integer and 
-regular graph. If 
. 
of graphs is 
so that every 
satisfies 
. 
for every 
with 
odd.
be an integer. If 
. 
-factor in a graph 
be a fixed positive real number and 
contains and 
, then 
be improved for the Maximum Edge Disjoint Paths problem (MaxEDP) in planar graphs or can an inapproximability result stronger than 
-hardness? 
Drupal
CSI of Charles University