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.
To divide a given 2D convex region C into a specified number n of convex pieces all of equal area (perimeters could be different) such that the total perimeter of pieces is (1) maximized (2) minimized.
Remark: It appears maximizing the total perimeter is the easier problem.
The crossing number of is the minimum number of crossings in all drawings of in the plane.
The -dimensional (hyper)cube is the graph whose vertices are all binary sequences of length , and two of the sequences are adjacent in if they differ in precisely one coordinate.
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?
Given integers , let be the smallest integer such that the symmetric group on the set of all words of length over a -letter alphabet can be generated as ( times), where is the shuffle permutation defined by , and is the exchange group consisting of all permutations in preserving the first letters in the words.
Problem Two players start at a distance of 2 on an (undirected) line (so, neither player knows the direction of the other) and both move at a maximum speed of 1. What is the infimum expected meeting time (first time when the players occupy the same point) which can be achieved assuming the two players must adopt the same strategy?
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.
login/create account
, there exist positive integers 
, 
, 
such that 
.
, for 
a large prime, always contain a rainbow 
if each of the color classes is of size of either 
or 
? 
there is an integer 
such that every set of at least 
collinear points or an empty hexagon. 
, the Davenport constant of 
, is the smallest integer 
so that every sequence of elements of 
has a nontrivial subsequence which sums to zero.
of 
-dimensional (hyper)cube 
is the graph whose vertices are all binary sequences of length 
to be the maximum degree, 
to be the size of the largest 
to be the chromatic number of 
for every graph 
. 
concentrated on a single value? 
be an integer and let 
denote the least integer 
such that there exists a simple graph on 
spanning trees. Then 
and 
are 
denote the 
? 
for every filter objects 
and 
and a funcoid 
? 
let 
. 
be a matroid on 
, let 
be a map, put 
and 
. Then 
in the hypercube. 
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 
containing a Hamiltonian path.
, we write 
if 
satisfies 
. The problem of finding such an integer 
(with 
) is the Discrete Log Problem.
, let 
be the smallest integer 
such that the symmetric group 
on the set of all words of length 
(
is the shuffle permutation defined by 
, and 
is the exchange group consisting of all permutations in 
letters in the words. 
, for all 
(first time when the players occupy the same point) which can be achieved assuming the two players must adopt the same strategy? 
. 
. 
-neighbour bootstrap process in the hypercube. 
Frege system 
but requires exponential size 
proofs. 
is unfriendly if every vertex has at least as many neighbors in the other classes as in its own. 
Drupal
CSI of Charles University