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.
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.
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
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.
Conjecture Any linear hypergraph with incidence poset of dimension at most 3 is the intersection hypergraph of a family of triangles and segments in the plane.
Conjecture For every positive integer , there exists an integer so that every polytope of dimension has a -dimensional face which is either a simplex or is combinatorially isomorphic to a -dimensional cube.
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?
An -factor in a graph is a set of vertex-disjoint copies of covering all vertices of .
Problem Let be a fixed positive real number and a fixed graph. Is it NP-hard to determine whether a graph on vertices and minimum degree contains and -factor?
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.
Suppose is a finite group, and is a positive integer dividing . Suppose that has exactly solutions to . Does it follow that these solutions form a subgroup of ?
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 .
Let be a hypergraph. A strongly maximal matching is a matching so that for every matching . A strongly minimal cover is a (vertex) cover so that for every cover .
Conjecture If is a (possibly infinite) hypergraph in which all edges have size for some integer , then has a strongly maximal matching and a strongly minimal cover.
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 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 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.
login/create account
is a 
-regular directed graph with no parallel arcs, then 
arc-disjoint directed cycles. 
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)
, every 
-diregular oriented graph on at most 
vertices has a Hamilton cycle. 
, then there is a 
-vertex colouring of 
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?
has a 
, let 
be the smallest integer 
such that the symmetric group 
on the set of all words of length 
over a 
(
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? 
-factor in a graph 
be a fixed positive real number and 
contains and 
for some filter objects 
, 
. Particularly, is this formula true for 
? 
for some filter objects 
of a locally finite graph 
. Suppose that 
. Does it follow that these solutions form a subgroup of 
be a finite family of finite sets, not all empty, that is closed under taking unions. Then there exists 
such that 
so that 
for every matching 
. A strongly minimal cover is a (vertex) cover 
so that 
for every cover 
. 
for some integer 
such that 
meets 
in at most one vertex, 
. 
containing no pair of orthogonal vectors is attained by two open caps of geodesic radius 
around the north and south poles. 
is unfriendly if every vertex has at least as many neighbors in the other classes as in its own. 
denote the graph with vertex set consisting of all lines through the origin in 
and two vertices adjacent in 
? 
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. 
Drupal
CSI of Charles University