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 Let be the open unit disk in the complex plane and let be open sets such that . Suppose there are injective holomorphic functions such that for the differentials we have on any intersection . Then those differentials glue together to a meromorphic 1-form on .
Let be a positive integer. We say that a graph is strongly -colorable if for every partition of the vertices to sets of size at most there is a proper -coloring of in which the vertices in each set of the partition have distinct colors.
Conjecture If is the maximal degree of a graph , then is strongly -colorable.
Note that the above is a generalization of monotone Galois connections (with and replaced with suprema and infima).
Then we have the following diagram:
What is at the node "other" in the diagram is unknown.
Conjecture "Other" is .
Question What repeated applying of and to "other" leads to? Particularly, does repeated applying and/or to the node "other" lead to finite or infinite sets?
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 ?
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.
Conjecture Let be an -uniform-partite hypergraph. If is the maximum number of pairwise disjoint edges in , and is the size of the smallest set of vertices which meets every edge, then .
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 .
Conjecture For , let be the statement that given any exact -coloring of the edges of a complete countably infinite graph (that is, a coloring with colors all of which must be used at least once), there exists an exactly -colored countably infinite complete subgraph. Then is true if and only if , , or .
The star chromatic index of a graph is the minimum number of colors needed to properly color the edges of the graph so that no path or cycle of length four is bi-colored.
Question Is it true that for every (sub)cubic graph , we have ?
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?
Problem Is there a problem that can be computed by a Turing machine in polynomial space and unbounded time but not in polynomial time? More formally, does P = PSPACE?
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 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 If is a cubic graph not containing a triangle, then it is possible to color the edges of by five colors, so that the complement of every color class is a bipartite graph.
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?
Consider a set of great circles on a sphere with no three circles meeting at a point. The arrangement graph of has a vertex for each intersection point, and an edge for each arc directly connecting two intersection points. So this arrangement graph is 4-regular and planar.
Conjecture Every arrangement graph of a set of great circles is -colourable.
Conjecture Any linear hypergraph with incidence poset of dimension at most 3 is the intersection hypergraph of a family of triangles and segments in the plane.
login/create account
? 
, the sequence in 
consisting of 
copes of 
and 
copies of 
has the fewest number of distinct subsequence sums over all zero-free sequences from 
. 
in the hypercube. 
is a sequence of elements from a multiplicative group of order 
, then there exist 
so that 
. 
has an acyclic induced subdigraph of order at least 
. 
so that all pairwise distances between points in 
are rational? 
be open sets such that 
. Suppose there are injective holomorphic functions 
such that for the differentials we have 
on any intersection 
. Then those differentials glue together to a meromorphic 1-form on 
and 
has equivalence covering number 
. 
be a positive integer. We say that a graph 
is strongly 
is the maximal degree of a graph 
-colorable. 
:
;
. 
and 
replaced with suprema and infima).
. 
and 
to "other" leads to? Particularly, does repeated applying 
does there exists a 
such that every graph with average degree smaller than 
and 
integers, determine whether or not there are 
values 
so that 
The best known worst-case algorithm runs in time 
times a polynomial in 
?
denote the 
diagonal 
exists. 
in the 
be positive semidefinite, by Jensen's inequality, it is easy to see ![$ [tr(A^s+B^s)]^{\frac{1}{s}}\leq [tr(A^r+B^r)]^{\frac{1}{r}} $](/files/tex/f5fa90ccf8c1dde9b9bf1f21399b3b5428dab81d.png)
, whenever 
.
, is it still valid?
, 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)
, 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 
be an 
is the maximum number of pairwise disjoint edges in 
is the size of the smallest set of vertices which meets every edge, then 
. 
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 
, let 
be the statement that given any exact 
-coloring of the edges of a complete countably infinite graph (that is, a coloring with 
-colored countably infinite complete subgraph. Then 
, 
, or 
. 
of a graph 
? 
which cannot be expressed as a union of 
triangle free graphs? 
? 
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 
? 
is the only 
. The representation function 
for 
is given by the rule 
. We call 
is never 
.
be the flow polynomial of a graph 
equals the number of 
for every 2-edge-connected graph 
we have 
. Then 
is graphic. 
be a prime natural number. Find all primes 
, such that 
.
arc-disjoint directed cycles. 
. In other words, simplify this formula. 
denote the pebbling number of a graph 
. 
be improved for the Maximum Edge Disjoint Paths problem (MaxEDP) in planar graphs or can an inapproximability result stronger than 
-hardness? 
concentrated on a single value? 
directed paths. 
-colourable. 
be integers. Set 
and 
for 
. Eventually we have 
; put 
.
, since 
, 
, 
, 
, 
, 
, 
, 
.
.
Drupal
CSI of Charles University