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 ?
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 For every prime , there is a constant (possibly ) so that the union (as multisets) of any bases of the vector space contains an additive basis.
Question Can either of the following be expressed in fixed-point logic plus counting: \item Given a graph, does it have a perfect matching, i.e., a set of edges such that every vertex is incident to exactly one edge from ? \item Given a square matrix over a finite field (regarded as a structure in the natural way, as described in [BGS02]), what is its determinant?
Given integers , let be the smallest integer such that the symmetric group on the set of all words of length over a -letter alphabet can be generated as ( times), where is the shuffle permutation defined by , and is the exchange group consisting of all permutations in preserving the first letters in the words.
Problem Ian Agol and Matthias Goerner observed that the 4x5 chessboard complex is the complement of many distinct links in the 3-sphere. Their observation is non-constructive, as it uses the resolution of the Poincare Conjecture. Find specific links that have the 4x5 chessboard complex as their complement.
Conjecture Let be the space of Diffeomorphisms on the connected , compact and boundaryles manifold M and the space of vector fields. There is a dense set ( ) such that exhibit a finite number of attractor whose basins cover Lebesgue almost all ambient space
This is a very Deep and Hard problem in Dynamical Systems . It present the dream of the dynamicist mathematicians .
Conjecture Let is a -separable (the same as for symmetric transitive) compact funcoid and is a uniform space (reflexive, symmetric, and transitive endoreloid) such that . Then .
The main purpose here is to find a direct proof of this conjecture. It seems that this conjecture can be derived from the well known theorem about existence of exactly one uniformity on a compact set. But that would be what I call an indirect proof, we need a direct proof instead.
The direct proof may be constructed by correcting all errors an omissions in this draft article.
Direct proof could be better because with it we would get a little more general statement like this:
Conjecture Let be a -separable compact reflexive symmetric funcoid and be a reloid such that \item ; \item .
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 .
Conjecture Let be a simple graph with vertices and list chromatic number . Suppose that and each vertex of is assigned a list of colors. Then at least vertices of can be colored from these lists.
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 
?
and 
, whether there exists a homomorphism from 
for some constant 
? 
, 
on an even number of vertices can be decomposed into 
directed paths. 
rectangular 
inside an 
? 
the following inequality holds 
contains and 
, there is a constant 
(possibly 
) so that the union (as multisets) of any 
contains an additive basis. 
of edges such that every vertex is incident to exactly one edge from 
, let 
be the smallest integer 
such that the symmetric group 
on the set of all words of length 
-letter alphabet can be generated as 
(
times), where 
is the shuffle permutation defined by 
, and 
is the exchange group consisting of all permutations in 
letters in the words. 
, for all 
in the hypercube. 
can be represented as the sum of an odd prime number and an odd 
be the space of 
Diffeomorphisms on the connected , compact and boundaryles manifold M and 
the space of 
(
) such that 
exhibit a finite number of attractor whose basins cover Lebesgue almost all ambient space 
is a 
-separable (the same as 
for symmetric transitive) compact funcoid and 
is a uniform space (reflexive, symmetric, and transitive endoreloid) such that 
. Then 
. 
. 
. 
such that its fundamental group has an element of finite order?
, and let 
be the edge set of a forest chosen uniformly at random from all forests of ![\[ {\mathbb P}(e \in F \mid f \in F}) \le {\mathbb P}(e \in F) \]](/files/tex/1fe7ac9c579238670e3aa16ae401e8194e1c3da3.png)
, and for 
let 
be the number of closed sets of rank 
.
is unimodal. 
be the number of unordered pairs of nonadjacent vertices (i.e. the number of non-edges), and 
be the size of the smallest 
, then 
. 
. Suppose that 
and each vertex of 
colors. Then at least 
vertices of 
-
of 
so that 
is 
-edge-connected and 
is ![$ p \in {\mathbb Q}[x] $](/files/tex/a72fcb0a006c3c2afb3ba69722ccdb2599b83e90.png)
rationally derived if all roots of 
Drupal
CSI of Charles University