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?
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 four cells at the vertices of a square with horizontal and vertical sides is the winner. What is the outcome of the game given optimal play? Note: Roland Bacher and Shalom Eliahou proved that every 15 x 15 binary matrix contains four equal entries (all 0's or all 1's) at the vertices of a square with horizontal and vertical sides. So the game must result in a winner (the first player) when n=15.
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 The valency-variety of a graph is the number of different degrees in . Is the chromatic number of any graph with at least two vertices greater than
Problem (2) Find a composite or which divides both (see Fermat pseudoprime) and the Fibonacci number (see Lucas pseudoprime), or prove that there is no such .
Conjecture If is a simple graph which is the union of pairwise edge-disjoint complete graphs, each of which has vertices, then the chromatic number of is .
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 \item If is a countable connected graph then its third power is hamiltonian. \item If is a 2-connected countable graph then its square is hamiltonian.
We are given a complete simple undirected weighted graph and its first arbitrary shortest spanning tree . We define the next graph and find on the second arbitrary shortest spanning tree . We continue similarly by finding on , etc. Let k be the smallest number of disjoint shortest spanning trees as defined above and let be the graph obtained as union of all disjoint trees.
Question 1. What is the smallest number of disjoint spanning trees creates a graph containing a Hamiltonian path.
Question 2. What is the smallest number of disjoint spanning trees creates a graph containing a shortest Hamiltonian path?
Questions 3 and 4. Replace in questions 1 and 2 a shortest spanning tree by a 1-tree. What is the smallest number of disjoint 1-trees creates a Hamiltonian graph? What is the smallest number of disjoint 1-trees creates a graph containing a shortest Hamiltonian cycle?
login/create account
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? 
grid. The first player (if any) to occupy four cells at the vertices of a square with horizontal and vertical sides is the winner. What is the outcome of the game given optimal play? Note: Roland Bacher and Shalom Eliahou proved that every 15 x 15 binary matrix contains four equal entries (all 0's or all 1's) at the vertices of a square with horizontal and vertical sides. So the game must result in a winner (the first player) when n=15. 
be an abelian group of odd order and let 
satisfy 
. Then the elements of 
and 
may be ordered 
and 
so that the sums 
are pairwise distinct. 
be a finite family of finite sets, not all empty, that is closed under taking unions. Then there exists 
such that 
on an even number of vertices can be decomposed into 
directed paths. 
-regular directed graph with no parallel arcs, then 
arc-disjoint directed cycles. 
of a graph 
for every filter objects 
and 
and a funcoid 
? 
? 
. 
always rational? 
or 
which divides both 
(see 
(see 
. 
and 
are 
, then 
be the unique integer (with respect to a fixed 
) such that
is a prime iff ![$$ \displaystyle \sum_{i=1}^{\left \lfloor \frac{\sqrt[3]p}{2} \right \rfloor} r_i = \left \lfloor \frac{\sqrt[3]p}{2} \right \rfloor $$](/files/tex/99af565f4cc4d3bab11eb3fbf54f78626678d484.png)
, every (loopless) graph 
immerses 
. 
be a surface. Is it true that every optimal drawing of 
which cannot be expressed as a union of 
triangle free graphs? 
, what is the smallest integer 
such that 
? 
and every positive integer 
so that every simple 
-regular graph 
has a 
with 
. 
are simple finite graphs, then 
. 
is the 
and its first arbitrary shortest spanning tree 
. We define the next graph 
and find on 
. We continue similarly by finding 
on 
, etc. Let k be the smallest number of disjoint shortest spanning trees as defined above and let 
be the graph obtained as union of all 
containing a Hamiltonian path.
be a matroid of rank 
let 
be the number of closed sets of rank 
.
is unimodal. 
, it is impossible to cover a square of side greater than 
unit squares. 
Drupal
CSI of Charles University