Problem Is there a minimum integer such that the vertices of any digraph with minimum outdegree can be partitioned into two classes so that the minimum outdegree of the subgraph induced by each class is at least ?
For a graph , let denote the cardinality of a maximum cycle packing (collection of vertex disjoint cycles) and let denote the cardinality of a minimum feedback vertex set (set of vertices so that is acyclic).
In an edge-colored digraph, we say that a subgraph is rainbow if all its edges have distinct colors, and monochromatic if all its edges have the same color.
Problem Let be a tournament with edges colored from a set of three colors. Is it true that must have either a rainbow directed cycle of length three or a vertex so that every other vertex can be reached from by a monochromatic (directed) path?
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 ?
If , are graphs, a function is called cycle-continuous if the pre-image of every element of the (binary) cycle space of is a member of the cycle space of .
Problem Does there exist an infinite set of graphs so that there is no cycle continuous mapping between and whenever ?
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.
For a finite (additive) abelian group , the Davenport constant of , denoted , is the smallest integer so that every sequence of elements of with length has a nontrivial subsequence which sums to zero.
Conjecture If every second positive integer except 2 is remaining, then every third remaining integer except 3, then every fourth remaining integer etc. , an infinite number of the remaining integers are prime.
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.
Problem Consider the set of all topologically inequivalent polyhedra with edges. Define a form parameter for a polyhedron as where is the number of vertices. What is the distribution of for ?
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.
Problem Is there an algorithm which takes as input a triangulated 4-manifold, and determines whether or not this manifold is combinatorially equivalent to the 4-sphere?
Throughout this post, by projective plane we mean the set of all lines through the origin in .
Definition Say that a subset of the projective plane is octahedral if all lines in pass through the closure of two opposite faces of a regular octahedron centered at the origin.
Definition Say that a subset of the projective plane is weakly octahedral if every set such that is octahedral.
Conjecture Suppose that the projective plane can be partitioned into four sets, say and such that each set is weakly octahedral. Then each is octahedral.
Conjecture Let be a simple -uniform hypergraph, and assume that every set of points is contained in at most edges. Then there exists an -edge-coloring so that any two edges which share vertices have distinct colors.
Conjecture For all there is an integer such that every digraph of minimum outdegree at least contains a subdivision of a transitive tournament of order .
login/create account
such that the vertices of any digraph with minimum outdegree 
can be partitioned into two classes so that the minimum outdegree of the subgraph induced by each class is at least 
, let 
denote the cardinality of a maximum cycle packing (collection of vertex disjoint cycles) and let 
denote the cardinality of a minimum feedback vertex set (set of vertices 
so that 
is acyclic). 
. 
of 
so that every other vertex can be reached from 
into 
so that the graph induced by 
is acyclic for 
. 
is a sequence of elements from a multiplicative group of order 
, then there exist 
so that 
. 
are graphs, a function 
is called cycle-continuous if the pre-image of every element of the (binary) cycle space of 
so that there is no cycle continuous mapping between 
and 
whenever 
? 
be an elliptic curve over a number field 
. Then the order of the zeros of its 
-function, 
, at 
is the Mordell-Weil rank of 
. 
, is the smallest integer 
so that every sequence of elements of 
has a nontrivial subsequence which sums to zero.
satisfies 
. 
and every rational 
, there is no polynomial-time algorithm for the following problem.
on 
clauses drawn uniformly at random from the set of formulas on 
simultaneously satisfiable clauses. 
edges. Define a form parameter for a polyhedron as 
where 
for 
? 
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).
. The representation function 
for 
is given by the rule 
. We call 
is never 
.
for reloid 
. 
for every funcoid 
(see below mentioned online article).
.
of the projective plane is octahedral if all lines in 
such that 
is octahedral. 
and 
such that each set 
is weakly octahedral. Then each 
points is contained in at most 
edges. Then there exists an 
-edge-coloring so that any two edges which share 
always rational? 
such that every digraph of minimum outdegree at least 
Drupal
CSI of Charles University