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 Let be a finite family of finite sets, not all empty, that is closed under taking unions. Then there exists such that is an element of at least half the members of .
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?
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.
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.
Problem Let be a graph, a countable end of , and an infinite set of pairwise disjoint -rays in . Prove that there is a set of pairwise disjoint -rays that devours such that the set of starting vertices of rays in equals the set of starting vertices of rays in .
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.
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 ?
If is a finite set of points which is 2-colored, an empty triangle is a set with so that the convex hull of is disjoint from . We say that is monochromatic if all points in are the same color.
Conjecture There exists a fixed constant with the following property. If is a set of points in general position which is 2-colored, then it has monochromatic empty triangles.
Conjecture Let be the complete funcoid corresponding to the usual topology on extended real line . Let be the order on this set. Then is a complete funcoid.
Proposition It is easy to prove that is the infinitely small right neighborhood filter of point .
If proved true, the conjecture then can be generalized to a wider class of posets.
Problem Let be natural numbers with . It follows from the pigeon-hole principle that there exist distinct subsets with . Is it possible to find such a pair in polynomial time?
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.
login/create account
is a connected graph on 
vertices, then 
for 
. 
-minor. ![\[ F_n = 2^{2^{n } } + 1 \]](/files/tex/70ca73d7e82af2fee084a8417e172c58cf78b376.png)
Square-Free?
does there exists a 
such that every graph with average degree smaller than 
be a digraph all of whose strong components are nontrivial. 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 
be a finite family of finite sets, not all empty, that is closed under taking unions. Then there exists 
such that 
the following inequality holds 
contains a directed path of length 
. 
? 
-regular graph, where 
, then 
with 
so that 
has a 
. 
of great circles on a sphere with no three circles meeting at a point. The arrangement graph of 
-colourable. 
a countable end of 
an infinite set of pairwise disjoint 
of pairwise disjoint 
such that the vertices of any digraph with minimum outdegree 
let 
denote the minimal number 
such that there is a rainbow 
in every equinumerous 
-coloring of 
for every 
, 
. 
is a finite set of points which is 2-colored, an empty triangle is a set 
with 
so that the convex hull of 
is disjoint from 
. We say that 
with the following property. If 
monochromatic empty triangles. 
be the complete funcoid corresponding to the usual topology on extended real line ![$ [-\infty,+\infty] = \mathbb{R}\cup\{-\infty,+\infty\} $](/files/tex/3252019c60a83f00ff396d823dbff8040639f409.png)
. Let 
be the order on this set. Then 
is a complete funcoid. 
is the infinitely small right neighborhood filter of point ![$ x\in[-\infty,+\infty] $](/files/tex/4e57a21194d8d5a659e259a111ed13a9c23b52a1.png)
. 
be natural numbers with 
. It follows from the pigeon-hole principle that there exist distinct subsets 
with 
. Is it possible to find such a pair 
in polynomial time? 
for every 
with odd size.
for every 
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. 
be abelian groups and let 
and 
satisfy 
and 
. If there is a 
to 
, then every graph with a B-flow has a B'-flow. 
Drupal
CSI of Charles University