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 .
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 If in a bridgeless cubic graph the cycles of any -factor are odd, then , where denotes the oddness of the graph , that is, the minimum number of odd cycles in a -factor of .
An alternating walk in a digraph is a walk so that the vertex is either the head of both and or the tail of both and for every . A digraph is universal if for every pair of edges , there is an alternating walk containing both and
Question Does there exist a locally finite highly arc transitive digraph which is universal?
Conjecture For every fixed and fixed colouring of with colours, there exists such that every colouring of the edges of contains either vertices whose edges are coloured according to or vertices whose edges are coloured with at most colours.
Basic Question: Given any positive integer n, can any convex polygon be partitioned into n convex pieces so that all pieces have the same area and same perimeter?
Definitions: Define a Fair Partition of a polygon as a partition of it into a finite number of pieces so that every piece has both the same area and the same perimeter. Further, if all the resulting pieces are convex, call it a Convex Fair Partition.
Questions: 1. (Rephrasing the above 'basic' question) Given any positive integer n, can any convex polygon be convex fair partitioned into n pieces?
2. If the answer to the above is "Not always'', how does one decide the possibility of such a partition for a given convex polygon and a given n? And if fair convex partition is allowed by a specific convex polygon for a give n, how does one find the optimal convex fair partition that minimizes the total length of the cut segments?
3. Finally, what could one say about higher dimensional analogs of this question?
Conjecture: The authors tend to believe that the answer to the above 'basic' question is "yes". In other words they guess: Every convex polygon allows a convex fair partition into n pieces for any n
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 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?
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.
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 There is an integer-valued function such that if is any -connected graph and and are any two vertices of , then there exists an induced path with ends and such that is -connected.
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.
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 ?
Conjecture \item If is a 4-edge-connected locally finite graph, then its line graph is hamiltonian. \item If the line graph of a locally finite graph is 4-connected, then 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.
login/create account
, 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 
.
. 
appears once in Pascal's triangle, 
appears twice, 
appears three times, and 
appears 
times. There are infinite families of numbers known to appear 
times is 
. It is not known whether any number appears more than 
. See 
of graphs is 
-bounded if there exists a function 
so that every 
satisfies 
. 
, the family of graphs with no induced subgraph isomorphic to 
the cycles of any 
, where 
denotes the oddness of the graph 
so that the vertex 
is either the head of both 
and 
or the tail of both 
. A digraph is universal if for every pair of edges 
, there is an alternating walk containing both 
and 
are simple finite graphs, then 
. 
is the 
.
and fixed colouring 
with 
colours, there exists 
such that every colouring of the edges of 
contains either 
vertices whose edges are coloured according to 
vertices whose edges are coloured with at most 
colours. 
be a 
, 
. By the Jordan-Brouwer separation theorem, 
? ie: is 
to be the maximum degree, 
to be the chromatic number of 
for every graph 
and 
and let 
be a surface. Is it true that every optimal drawing of 
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 
points in general position which is 2-colored, then it has 
monochromatic empty triangles. 
a countable end of 
an infinite set of pairwise disjoint 
of pairwise disjoint 
-regular graph, where 
, then 
, what is the smallest integer 
such that 
? 
such that if 
and 
are any two vertices of 
with ends 
is 
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. 
and 
integers, determine whether or not there are 
values 
so that 
The best known worst-case algorithm runs in time 
times a polynomial in 
?
so that every simple 
has a 
. 
of a locally finite graph 
, is the smallest integer 
so that every sequence of elements of 
has a nontrivial subsequence which sums to zero.
Square free? 
Drupal
CSI of Charles University