Conjecture If is the adjacency matrix of a -regular graph, then there is a symmetric signing of (i.e. replace some entries by ) so that the resulting matrix has all eigenvalues of magnitude at most .
For and positive integers, the (mixed) van der Waerden number is the least positive integer such that every (red-blue)-coloring of admits either a -term red arithmetic progression or an -term blue arithmetic progression.
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 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?
Let be a graph. If and are two integers, a -colouring of is a function from to such that for each edge . Given a list assignment of , i.e.~a mapping that assigns to every vertex a set of non-negative integers, an -colouring of is a mapping such that for every . A list assignment is a --list-assignment if and for each vertex . Given such a list assignment , the graph G is --colourable if there exists a --colouring , i.e. is both a -colouring and an -colouring. For any real number , the graph is --choosable if it is --colourable for every --list-assignment . Last, is circularly -choosable if it is --choosable for any , . The circular choosability (or circular list chromatic number or circular choice number) of G is
Problem What is the best upper bound on circular choosability for planar graphs?
Problem What is the maximum number of colours needed to colour countries such that no two countries sharing a common border have the same colour in the case where each country consists of one region on earth and one region on the moon ?
Conjecture Let be a simple -uniform hypergraph, and assume that every set of points is contained in at most edges. Then there exists an -edge-coloring so that any two edges which share vertices have distinct colors.
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 a set of cells having no two cells in the same row or column is the winner. What is the outcome of the game given optimal play?
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.
Problem () Find a sufficient condition for a straight -stage graph to be rearrangeable. In particular, what about a straight uniform graph?
Conjecture () Let be a simple regular ordered -stage graph. Suppose that the graph is externally connected, for some . Then the graph is rearrangeable.
Conjecture Let be a sequence of points in with the property that for every , the points are distinct, lie on a unique sphere, and further, is the center of this sphere. If this sequence is periodic, must its period be ?
Conjecture For every fixed graph , there exists a constant , so that every graph without an induced subgraph isomorphic to contains either a clique or an independent set of size .
Conjecture If is a finite field with at least 4 elements and is an invertible matrix with entries in , then there are column vectors which have no coordinates equal to zero such that .
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?
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.
Conjecture Let and . Then for any neighborhood there is such that is periodic point of
There is an analogous conjecture for flows ( vector fields . In the case of diffeos this was proved by Charles Pugh for . In the case of Flows this has been solved by Sushei Hayahshy for . But in the two cases the problem is wide open for
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 .
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?
login/create account
is the adjacency matrix of a 
-regular graph, then there is a symmetric signing of 
entries by 
) so that the resulting matrix has all eigenvalues of magnitude at most 
. 
-degenerate graph (a forest) and a 
-degenerate graph is 
-colourable. 
and 
positive integers, the (mixed) van der Waerden number 
is the least positive integer 
such that every (red-blue)-coloring of ![$ [1,n] $](/files/tex/661d0acc09fbc5b62f49645a71cf7d831a26563f.png)
admits either a 
, 
. 
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? 
-graph if it has a bipartition 
so that every vertex in 
and every vertex in 
has degree 
. ![\[ F_n = 2^{2^{n } } + 1 \]](/files/tex/70ca73d7e82af2fee084a8417e172c58cf78b376.png)
Square-Free?
is a graph, we say that a partition of 
is unfriendly if every vertex has at least as many neighbors in the other classes as in its own. 
be a graph. If 
and 
are two integers, a 
-colouring of 
from 
to 
such that 
for each edge 
. Given a list assignment 
of 
a set of non-negative integers, an 
such that 
for every 
. A list assignment 
-
and 
for each vertex 
. Given such a list assignment 
, the graph 
exist a 
be a simple 
points is contained in at most 
edges. Then there exists an 
-edge-coloring so that any two edges which share 
is called a Diophantine 
-tuple if 
is a perfect square for all 
. 
is a Diophantine quadruple and 
, then 
grid. The first player (if any) to occupy a set of 
immerses 
. 
) Find a sufficient condition for a straight 
) Let 
is externally connected, for some 
. Then the graph 
is rearrangeable. 
are prime.
. 
be a sequence of points in 
with the property that for every 
, the points 
are distinct, lie on a unique sphere, and further, 
is the center of this sphere. If this sequence is periodic, must its period be 
? 
, so that every graph 
. 
is a finite field with at least 4 elements and 
matrix with entries in 
which have no coordinates equal to zero such that 
. 
, is the graph with vertex set 
and two points adjacent if the distance between them is an odd integer. 
? 
always rational? 
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.
for every endo-
? 
be integers. Set 
and 
for 
. Eventually we have 
; put 
.
, since 
, 
, 
, 
, 
, 
, 
, 
.
.
has a 
and 
. Then for any neighborhood 
there is 
such that 
vector fields . In the case of diffeos this was proved by Charles Pugh for 
. In the case of Flows this has been solved by Sushei Hayahshy for 
suffices) so that every graft with minimum 
-cut size at least 
. 
and 
be a surface. Is it true that every optimal drawing of 
points in the plane in general position contains a subset of 
so that the graph induced by 
is acyclic for 
. 
has a complete graph on 
vertices as a minor. 
, 
, what is the smallest integer 
such that 
? 
Drupal
CSI of Charles University