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.
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 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 For which values of and are there bi-colored graphs on vertices and different colors with the property that all the monochromatic colorings have unit weight, and every other coloring cancels out?
Question What is the least integer such that every set of at least points in the plane contains collinear points or a subset of points in general position (no three collinear)?
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.
Conjecture Define a array of positive integers where the first row consists of some distinct positive integers arranged in increasing order, and the second row consists of any positive integers in any order. Create a new array where the first row consists of all the integers that occur in the first array, arranged in increasing order, and the second row consists of their multiplicities. Repeat the process. For example, starting with the array , the sequence is: -> -> -> -> -> -> -> -> -> -> -> , and we now have a fixed point (loop of one array).
The process always results in a loop of 1, 2, or 3 arrays.
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 ).
A strong edge-colouring of a graph is a edge-colouring in which every colour class is an induced matching; that is, any two vertices belonging to distinct edges with the same colour are not adjacent. The strong chromatic index is the minimum number of colours in a strong edge-colouring of .
Conjecture \item If is a countable connected graph then its third power is hamiltonian. \item If is a 2-connected countable graph then its square is hamiltonian.
Conjecture If is a finite field with at least 4 elements and is an invertible matrix with entries in , then there are column vectors which have no coordinates equal to zero such that .
Problem Let be positve integer Does there exists an integer such that every -strong tournament admits a partition of its vertex set such that the subtournament induced by is a non-trivial -strong for all .
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.
Conjecture A Fermat prime is a Fermat number that is prime. The only known Fermat primes are F_0 =3,F_1=5,F_2=17,F_3 =257 ,F_4=65537 It is unknown if other fermat primes exist.
Problem Does the following equality hold for every graph ?
The crossing number of a graph is the minimum number of edge crossings in any drawing of in the plane. In the pairwise crossing number, we minimize the number of pairs of edges that cross.
login/create account
and every rational 
, there is no polynomial-time algorithm for the following problem.
on 
variables, for some 
clauses drawn uniformly at random from the set of formulas on 
simultaneously satisfiable clauses. 
-flow 
on 
is an orientation 
of 
from the edge set of 
, for all 
, and 
. The circular flow number of 
has a nowhere-zero 
, and it is denoted by 
.
is a class 1 graph if its edge chromatic number is 
be an integer and 
-regular graph. If 
. 
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 
and a function 
such that if 
, then every saturated 
has cardinality at least 
? 
are there bi-colored graphs on 
such that every set of at least 
Frege system 
but requires exponential size 
proofs. 
array of positive integers where the first row consists of some distinct positive integers arranged in increasing order, and the second row consists of any positive integers in any order. Create a new array where the first row consists of all the integers that occur in the first array, arranged in increasing order, and the second row consists of their multiplicities. Repeat the process. For example, starting with the array ![$ [1; 1] $](/files/tex/73f8649de444361674c157a2fe98e0c5783f1c46.png)
, the sequence is: ![$ [1; 2] $](/files/tex/83c3d9d7589f716ed6b0f05d26d36dabe8ba47aa.png)
-> ![$ [1, 2; 1, 1] $](/files/tex/a6a696aec4e84df6bc046cf6d30a4df80e156a14.png)
-> ![$ [1, 2; 3, 1] $](/files/tex/98b2f3e4134422c8a286f0326fc2f57ca9be2ab7.png)
-> ![$ [1, 2, 3; 2, 1, 1] $](/files/tex/19a9d24510f4551fa45b950aed32efed0636b355.png)
-> ![$ [1, 2, 3; 3, 2, 1] $](/files/tex/b00d573110ba8c2472820409103dd4cbd7bff7cc.png)
-> ![$ [1, 2, 3; 2, 2, 2] $](/files/tex/2aae90b65ae3f116402a1c0143127f80d86acdf0.png)
-> ![$ [1, 2, 3; 1, 4, 1] $](/files/tex/d614399c4078a70fbffb24eb99816a0974423175.png)
-> ![$ [1, 2, 3, 4; 3, 1, 1, 1] $](/files/tex/bf4dd82eaf95bd71a88cb78d3367efa2c7e4c942.png)
-> ![$ [1, 2, 3, 4; 4, 1, 2, 1] $](/files/tex/a4ef5900a9dde9b32311afe7dee2b143f42c405f.png)
-> ![$ [1, 2, 3, 4; 3, 2, 1, 2] $](/files/tex/ff367376ed7bb74fc6207273d7157062b83a1be6.png)
-> ![$ [1, 2, 3, 4; 2, 3, 2, 1] $](/files/tex/81ba2b3608ddba2fc95d32b74b70279f3f5adc5b.png)
, and we now have a fixed point (loop of one array).
-connected cubic graph and let 
be a 
is connected. Then 
, every (loopless) graph 
immerses 
. 
is the minimum number of colours in a strong edge-colouring of 
? 
. The representation function 
for 
is given by the rule 
. We call 
is never 
.
is a finite field with at least 4 elements and 
is an invertible 
matrix with entries in 
which have no coordinates equal to zero such that 
. 
be positve integer Does there exists an integer 
such that every 
admits a partition 
of its vertex set such that the subtournament induced by 
is a non-trivial 
-strong for all 
. ![$ p \in [0,1] $](/files/tex/1d076f7332523eb59bd7deae19667f83f0a3b6e0.png)
, we let 
denote a subgraph of 
.
so that 
? 
. Suppose that 
and each vertex of 
vertices of 
there is an integer 
such that every set of at least 
collinear points or an empty hexagon. 
, such that 
.
![\[ F_n = 2^{2^n } + 1 \]](/files/tex/0da5a50010e4e5df91c0d58080245ece34ec9ca6.png)
that is prime. The only known Fermat primes are F_0 =3,F_1=5,F_2=17,F_3 =257 ,F_4=65537 It is unknown if other fermat primes exist.
-size circuits compute the function 
on 
defined inductively by 
, 
, 
, and 
? 
with 
so that 
has a 
. ![\[ \text{pair-cr}(G) = \text{cr}(G) \]](/files/tex/8cece1e00bb0e9fc122e0a5cad0dab2681cf33a4.png)
of a graph 
, we minimize the number of pairs of edges that cross. 
. 
Drupal
CSI of Charles University