Conjecture An endomorphism of a graph is a mapping on the vertex set of the graph which preserves edges. Among all the vertices' trees, the star with vertices has the most endomorphisms, while the path with vertices has the least endomorphisms.
Conjecture Let be an integer. For every integer , there exists an integer such that for every digraph , either has a pairwise-disjoint directed cycles of length at least , or there exists a set of at most vertices such that has no directed cycles of length at least .
Given a partition of a finite set , stabilizer of , denoted , is the group formed by all permutations of preserving each block in .
Problem () Find a sufficient condition for a sequence of partitions of to be universal, i.e. to yield the following decomposition of the symmetric group on : In particular, what about the sequence , where is a permutation of ?
Conjecture (Beneš) Let be a uniform partition of and be a permutation of such that . Suppose that the set is transitive, for some integer . Then
Conjecture For every set of points in the plane, not all collinear, there is a point in contained in at least lines determined by , for some constant .
Conjecture There is a finite upper bound on the multiplicities of entries in Pascal's triangle, other than the number .
The number appears once in Pascal's triangle, appears twice, appears three times, and appears times. There are infinite families of numbers known to appear times. The only number known to appear times is . It is not known whether any number appears more than times. The conjectured upper bound could be ; Singmaster thought it might be or . See Singmaster's conjecture.
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.
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 .
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?
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 ?
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.
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 There exists a fixed constant (probably suffices) so that every graft with minimum -cut size at least contains a -join packing of size at least .
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?
Conjecture For every fixed graph , there exists a constant , so that every graph without an induced subgraph isomorphic to contains either a clique or an independent set of size .
Conjecture The largest measure of a Lebesgue measurable subset of the unit sphere of containing no pair of orthogonal vectors is attained by two open caps of geodesic radius around the north and south poles.
Conjecture It has been shown that a -outerplanar embedding for which is minimal can be found in polynomial time. Does a similar result hold for -edge-outerplanar graphs?
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 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 ).
Conjecture Let be the disjoint union of the graphs and and let be a surface. Is it true that every optimal drawing of on has the property that and are disjoint?
Conjecture Polignac's Conjecture: For any positive even number n, there are infinitely many prime gaps of size n. In other words: There are infinitely many cases of two consecutive prime numbers with difference n.
In particular, this implies:
Conjecture Twin Prime Conjecture: There are an infinite number of twin primes.
login/create account
, we define 
to be the maximum degree, 
to be the size of the largest 
to be the chromatic number of 
for every graph 
-connected graph with a Hamilton cycle has a second Hamilton cycle. 
vertices' trees, the star with 
be an integer. For every integer 
, there exists an integer 
such that for every digraph 
, either 
, or there exists a set 
of at most 
vertices such that 
has no directed cycles of length at least 
such that the list chromatic number of any bipartite graph 
is at most 
.
of a finite set 
, stabilizer of 
, is the group formed by all permutations of 
.
) Find a sufficient condition for a sequence of partitions 
of 
on 
In particular, what about the sequence 
, where 
is a permutation of 
be a uniform partition of 
be a permutation of 
. Suppose that the set 
is transitive, for some integer 
. Then 
is prime and 
, we write 
if 
satisfies 
. The problem of finding such an integer 
(with 
) is the Discrete Log Problem.
of 
lines determined by 
. 
appears once in Pascal's triangle, 
appears twice, 
appears three times, and 
appears 
times is 
. It is not known whether any number appears more than 
. See 
be a matroid of rank 
, and for 
let 
be the number of closed sets of rank 
.
is unimodal. 
in the hypercube. 
are matroids on 
for every partition 
of 
with 
which is independent in every 
. 
, what is the smallest integer 
such that 
? 
. The representation function 
for 
is given by the rule 
. We call 
is never 
.
. 
. Suppose that 
and each vertex of 
colors. Then at least 
vertices of 
in 
, let the symmetry group of 
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 
. 
edges. Define a form parameter for a polyhedron as 
where 
is the number of vertices. What is the distribution of 
for 
? 
of graphs is 
-bounded if there exists a function 
so that every 
satisfies 
. 
where 
is the number of faces of 
we have 
. Then 
is graphic. 
-colorable. 
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 
monochromatic empty triangles. 
suffices) so that every graft with minimum 
. 
so that the power series 
is bounded for all 
. 
-
grid. The first player (if any) to occupy a set of 
, there exists a constant 
, so that every graph 
. 
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?
containing no pair of orthogonal vectors is attained by two open caps of geodesic radius 
around the north and south poles. 
be an integer and let 
. Then either 
minor for some 
or 
edges whose deletion destroys every odd cycle. 
-
points is contained in at most 
-edge-coloring so that any two edges which share 
be a 
is connected. Then 
and 
and let 
be a surface. Is it true that every optimal drawing of 
so that all pairwise distances between points in 
let 
. 
be a map, put 
and 
. Then 
Drupal
CSI of Charles University