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 For every , the sequence in consisting of copes of and copies of has the fewest number of distinct subsequence sums over all zero-free sequences from of length .
Conjecture For every fixed graph , there exists a constant , so that every graph without an induced subgraph isomorphic to contains either a clique or an independent set of size .
Conjecture If a finite set of unit balls in is rearranged so that the distance between each pair of centers does not decrease, then the volume of the union of the balls does not decrease.
Conjecture Is the approximation ratio for the Maximum Edge Disjoint Paths (MaxEDP) or the Maximum Integer Multiflow problem (MaxIMF) bounded by a constant in -outerplanar graphs or tree-width graphs?
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 Let and . Then for any neighborhood there is such that is periodic point of
There is an analogous conjecture for flows ( vector fields . In the case of diffeos this was proved by Charles Pugh for . In the case of Flows this has been solved by Sushei Hayahshy for . But in the two cases the problem is wide open for
Conjecture Let be a complex projective variety. Then every Hodge class is a rational linear combination of the cohomology classes of complex subvarieties of .
Question \item Does hold over graphs of bounded tree-width? \item Is included in over graphs? \item Does have a 0-1 law? \item Are properties of Hanf-local? \item Is there a logic (with an effective syntax) that captures ?
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?
Conjecture The following statements are equivalent for every endofuncoid and a set : \item is connected regarding . \item For every there exists a totally ordered set such that , , and for every partion of into two sets , such that , we have .
An oriented colouring of an oriented graph is assignment of colours to the vertices such that no two arcs receive ordered pairs of colours and . It is equivalent to a homomorphism of the digraph onto some tournament of order .
login/create account
of graphs is 
-bounded if there exists a function 
so that every 
satisfies 
. 
, the family of graphs with no induced subgraph isomorphic to 
, the sequence in 
consisting of 
copes of 
and 
copies of 
has the fewest number of distinct subsequence sums over all zero-free sequences from 
. 
we have 
. Then 
is graphic. 
of 
is the minimum number of crossings in all drawings of 
is a 2-transition system for 
has a compaible decomposition. 
the following inequality holds 
, there exists a constant 
, so that every graph 
. 
does there exists a 
such that every graph with average degree smaller than 
is rearranged so that the distance between each pair of centers does not decrease, then the volume of the union of the balls does not decrease. 
is not an integer. 
and a function 
such that if 
, then every saturated 
-Sperner system 
has cardinality at least 
? 
-minor-free graph is 
-list-colourable for some constant 
. 
. 
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 
?
and 
. Then for any neighborhood 
there is 
such that 
is periodic point of 
vector fields . In the case of diffeos this was proved by Charles Pugh for 
. In the case of Flows this has been solved by Sushei Hayahshy for 
be a complex projective variety. Then every Hodge class is a rational linear combination of the cohomology classes of complex subvarieties of 
be a set of ![\[m(A) = - \min_x \sum_{a \in A} \cos(ax).\]](/files/tex/7a772ebd0b7fd98eeab7fda3a5e9674b1dc4c984.png)
What is 
? 
let 
denote the minimal number 
such that there is a rainbow 
in every equinumerous 
for every 
, 
. ![$ p \in {\mathbb Q}[x] $](/files/tex/a72fcb0a006c3c2afb3ba69722ccdb2599b83e90.png)
rationally derived if all roots of 
hold over graphs of bounded tree-width? \item Is 
included in 
over graphs? \item Does 
be a 
is connected regarding 
.
and a set 
:
there exists a totally ordered set 
such that 
, 
, and for every partion 
of 
such that 
, we have ![$ X \mathrel{[ \mu]^{\ast}} Y $](/files/tex/0ef560be389646efd1fdde5ebc9afc9ac98ee64e.png)
. 
of colours to the vertices such that no two arcs receive ordered pairs of colours 
and 
. It is equivalent to a homomorphism of the digraph onto some tournament of order 
be a digraph all of whose strong components are nontrivial. Then 
. 
in the hypercube. 
Drupal
CSI of Charles University