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 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 all there is an integer such that every digraph of minimum outdegree at least contains a subdivision of a transitive tournament of order .
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 .
Problem Let be a -dimensional smooth submanifold of , diffeomorphic to . By the Jordan-Brouwer separation theorem, separates into the union of two compact connected -manifolds which share as a common boundary. The Schoenflies problem asks, are these -manifolds diffeomorphic to ? ie: is unknotted?
Conjecture The following statements are equivalent for every endofuncoid and a set : \item is connected regarding . \item For every there exists a totally ordered set such that , , and for every partion of into two sets , such that , we have .
Conjecture For every graph without a bridge, there is a flow .
Conjecture There exists a map so that antipodal points of receive opposite values, and so that any three points which are equidistant on a great circle have values which sum to zero.
A friendly partition of a graph is a partition of the vertices into two sets so that every vertex has at least as many neighbours in its own class as in the other.
Problem Is it true that for every , all but finitely many -regular graphs have friendly partitions?
Conjecture If is a non-empty graph containing no induced odd cycle of length at least , then there is a -vertex colouring of in which no maximum clique is monochromatic.
Problem Given a link in , let the symmetry group of be denoted ie: isotopy classes of diffeomorphisms of which preserve , where the isotopies are also required to preserve .
Now let be a hyperbolic link. Assume has the further `Brunnian' property that there exists a component of such that is the unlink. Let be the subgroup of consisting of diffeomorphisms of which preserve together with its orientation, and which preserve the orientation of .
There is a representation given by restricting the diffeomorphism to the . It's known that is always a cyclic group. And is a signed symmetric group -- the wreath product of a symmetric group with .
Let be a simple graph, and for every list assignment let be the maximum number of vertices of which are colorable with respect to . Define , where the minimum is taken over all list assignments with for all .
Conjecture [2] Let be a graph with list chromatic number and . Then
For and positive integers, the (mixed) van der Waerden number is the least positive integer such that every (red-blue)-coloring of admits either a -term red arithmetic progression or an -term blue arithmetic progression.
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 ?
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 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 .
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.
We say that a set is -universal if every vertex planar graph can be drawn in the plane so that each vertex maps to a distinct point in , and all edges are (non-intersecting) straight line segments.
Question Does there exist an -universal set of size ?
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 graph and let such that for any pair there are edge-disjoint paths from to in . Then contains edge-disjoint trees, each of which contains .
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.
Problem Two players alternately write O's (first player) and X's (second player) in the unoccupied cells of an grid. The first player (if any) to occupy a set of cells having no two cells in the same row or column is the winner. What is the outcome of the game given optimal play?
Problem Does there exist a polynomial time algorithm which takes as input a graph and for every vertex a subset of , and decides if there exists a partition of into so that only if and so that are independent, is a clique, and there are no edges between and ?
login/create account
-neighbour bootstrap process in the hypercube. 
be a digraph. If 
, then 
. 
, 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 
, then 
. 
is a prime iff 
? 
are matroids on 
and 
for every partition 
of 
with 
which is independent in every 
. 
is not an integer. 
vertices has an edge colouring such that:
-connected planar graph, then 
has a Hamilton cycle. 
such that every digraph of minimum outdegree at least 
contains 
a countable end of 
an infinite set of pairwise disjoint 
of pairwise disjoint 
-flow 
on 
from the edge set of 
, for all 
, and 
.
-regular graph 
for every 
with 
odd.
be an integer. If 
. 
be a 
, 
. By the Jordan-Brouwer separation theorem, 
? ie: is 
be a 
edges has a separator of size 
. 
be a 
is connected regarding 
.
and a set 
:
there exists a totally ordered set 
such that 
, 
, and for every partion 
of 
into two sets 
, 
such that 
, we have ![$ X \mathrel{[ \mu]^{\ast}} Y $](/files/tex/0ef560be389646efd1fdde5ebc9afc9ac98ee64e.png)
. 
.
so that antipodal points of 
receive opposite values, and so that any three points which are equidistant on a great circle have values which sum to zero. 
for every filter objects 
and 
and a funcoid 
? 
has a compaible decomposition. 
, every (loopless) graph 
immerses 
. 
, then there is a 
-vertex colouring of 
in 
ie: isotopy classes of diffeomorphisms of 
of 
is the unlink. Let 
be the subgroup of 
consisting of diffeomorphisms of 
given by restricting the diffeomorphism to the 
is a signed symmetric group -- the wreath product of a symmetric group with 
. 
is a tournament of order 
arc-disjoint transitive subtournaments of order 3. 
let 
be the maximum number of vertices of 
, where the minimum is taken over all list assignments 
for all 
. 
and 
. Then ![\[\frac{\lambda_r}{r}\geq\frac{\lambda_s}{s}.\]](/files/tex/47be18e956355dd433b88b66eabf01a9e3ed5f61.png)
positive integers, the (mixed) van der Waerden number 
is the least positive integer ![$ [1,n] $](/files/tex/661d0acc09fbc5b62f49645a71cf7d831a26563f.png)
admits either a 
, 
. 
where 
is the number of vertices. What is the distribution of 
for 
? 
is a finite set of points which is 2-colored, an empty triangle is a set 
with 
so that the convex hull of 
. We say that 
with the following property. If 
monochromatic empty triangles. 
, 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 
.
there is a sequence of tautologies of depth 
Frege system 
but requires exponential size 
proofs. 
is 
? 
vertices which contains no complete 
hyperedges. 
vertices which contains no complete 
hyperedges. ![\[ w(G) = \max_{H \subseteq G} \left\lceil \frac{ |E(H)| }{ \lfloor \tfrac{1}{2} |V(H)| \rfloor} \right\rceil. \]](/files/tex/d2391343543ce03d861e6eb2f4985d52e309525d.png)
. 
structurally stable diffeomorphism is hyperbolic. 
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 
such that for any pair 
there are 
edge-disjoint paths from 
to 
grid. The first player (if any) to occupy a set of 
of 
, and decides if there exists a partition of 
into 
so that 
only if 
and so that 
are independent, 
is a clique, and there are no edges between 
and 
? 
Drupal
CSI of Charles University