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 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 ?
Problem Ian Agol and Matthias Goerner observed that the 4x5 chessboard complex is the complement of many distinct links in the 3-sphere. Their observation is non-constructive, as it uses the resolution of the Poincare Conjecture. Find specific links that have the 4x5 chessboard complex as their complement.
Conjecture Is it possible to color edges of the complete graph using colors, so that the coloring is proper and no 4-cycle and no 4-edge path is using only two colors?
Equivalently: is the star chromatic index of linear in ?
Problem Does the following equality hold for every graph ?
The crossing number of a graph is the minimum number of edge crossings in any drawing of in the plane. In the pairwise crossing number, we minimize the number of pairs of edges that cross.
Conjecture Let be a cubic graph with no bridge. Then there is a coloring of the edges of using the edges of the Petersen graph so that any three mutually adjacent edges of map to three mutually adjancent edges in the Petersen graph.
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 .
A nowhere-zero -flow on is an orientation of together with a function from the edge set of into the real numbers such that , for all , and . The circular flow number of is inf has a nowhere-zero -flow , and it is denoted by .
A graph with maximum vertex degree is a class 1 graph if its edge chromatic number is .
Conjecture Let be an integer and a -regular graph. If is a class 1 graph, then .
Throughout this post, by projective plane we mean the set of all lines through the origin in .
Definition Say that a subset of the projective plane is octahedral if all lines in pass through the closure of two opposite faces of a regular octahedron centered at the origin.
Definition Say that a subset of the projective plane is weakly octahedral if every set such that is octahedral.
Conjecture Suppose that the projective plane can be partitioned into four sets, say and such that each set is weakly octahedral. Then each is octahedral.
Conjecture Denote by the number of non-Hamiltonian 3-regular graphs of size , and similarly denote by the number of non-Hamiltonian 3-regular 1-connected graphs of size .
Problem What is the largest connected planar graph of minimum degree 3 which has everywhere positive combinatorial curvature, but is not a prism or antiprism?
login/create account
is a simple loopless 
. Is it true that for large enough~
? 
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)
the following inequality holds 
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 
?
. The graph 
is defined to be the 
-power of the 
.
. Then 
. 
contains a directed cycle of length at least 
. 
which is slice, is it a ribbon knot?
has chromatic number at most 
.
using 
colors, so that the coloring is proper and no 4-cycle and no 4-edge path is using only two colors?
-spheres bound (rational) homology 
-balls?
be the flow polynomial of a graph 
, the value 
equals the number of 
for every 2-edge-connected graph ![\[ \text{pair-cr}(G) = \text{cr}(G) \]](/files/tex/8cece1e00bb0e9fc122e0a5cad0dab2681cf33a4.png)
of a graph 
, we minimize the number of pairs of edges that cross. 
for reloid 
. 
for every funcoid 
(see below mentioned online article).
(probably 
suffices) so that every graft with minimum 
-cut size at least 
. 
of 
-flow 
on 
of 
from the edge set of 
, for all 
, and 
. The circular flow number of 
has a nowhere-zero 
, and it is denoted by 
.
be an integer and 
-regular graph. If 
. 
.
, the union of any 
-degenerate graph. 
.
of the projective plane is octahedral if all lines in 
such that 
is octahedral. 
and 
such that each set 
is weakly octahedral. Then each 
with 
so that 
has a 
. 
the number of non-Hamiltonian 3-regular graphs of size 
, and similarly denote by 
the number of non-Hamiltonian 3-regular 1-connected graphs of size 
? 
Drupal
CSI of Charles University