Conjecture Let if is odd and if is even. Let . Assume we start with some number and repeatedly take the of the current number. Prove that no matter what the initial number is we eventually reach .
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 .
Problem Determine a computable set of invariants that allow one to determine, given a compact boundaryless 3-manifold, whether or not it embeds smoothly in the 4-sphere. This should include a constructive procedure to find an embedding if the manifold is embeddable.
Let be a class of finite relational structures. We denote by the number of structures in over the labeled set . For any class definable in monadic second-order logic with unary and binary relation symbols, Specker and Blatter showed that, for every , the function is ultimately periodic modulo .
Question Does the Blatter-Specker Theorem hold for ternary relations.
Conjecture For every set of points in the plane, not all collinear, there is a point in contained in at least lines determined by , for some constant .
If is a finite set of points which is 2-colored, an empty triangle is a set with so that the convex hull of is disjoint from . We say that is monochromatic if all points in are the same color.
Conjecture There exists a fixed constant with the following property. If is a set of points in general position which is 2-colored, then it has monochromatic empty triangles.
Question Is the MSO-alternation hierarchy strict for pictures that are balanced, in the sense that the width and the length are polynomially (or linearly) related.
The deck of a graph is the multiset consisting of all unlabelled subgraphs obtained from by deleting a vertex in all possible ways (counted according to multiplicity).
Conjecture If two graphs on vertices have the same deck, then they are isomorphic.
Problem Is there a minimum integer such that the vertices of any digraph with minimum outdegree can be partitioned into two classes so that the minimum outdegree of the subgraph induced by each class is at least ?
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?
Let be a positive integer. We say that a graph is strongly -colorable if for every partition of the vertices to sets of size at most there is a proper -coloring of in which the vertices in each set of the partition have distinct colors.
Conjecture If is the maximal degree of a graph , then is strongly -colorable.
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.
Conjecture There is an integer-valued function such that if is any -connected graph and and are any two vertices of , then there exists an induced path with ends and such that is -connected.
Question Can either of the following be expressed in fixed-point logic plus counting: \item Given a graph, does it have a perfect matching, i.e., a set of edges such that every vertex is incident to exactly one edge from ? \item Given a square matrix over a finite field (regarded as a structure in the natural way, as described in [BGS02]), what is its determinant?
Conjecture Every surreal number has a unique sign expansion, i.e. function , where is some ordinal. This is the length of given sign expansion and also the birthday of the corresponding surreal number. Let us denote this length of as .
Conjecture Can the approximation ratio be improved for the Maximum Edge Disjoint Paths problem (MaxEDP) in planar graphs or can an inapproximability result stronger than -hardness?
login/create account
be a finite graph, let 
, and let 
be the edge set of a forest chosen uniformly at random from all forests of ![\[ {\mathbb P}(e \in F \mid f \in F}) \le {\mathbb P}(e \in F) \]](/files/tex/1fe7ac9c579238670e3aa16ae401e8194e1c3da3.png)
of graphs is 
-bounded if there exists a function 
so that every 
satisfies 
. 
, the family of graphs with no induced subgraph isomorphic to 
if 
is odd and 
if 
. Assume we start with some number 
of the current number. Prove that no matter what the initial number is we eventually reach 
. 
or 
which divides both 
(see 
(see 
, for 
a large prime, always contain a rainbow 
if each of the color classes is of size of either 
or 
? 
denote the 
diagonal 
exists. 
always rational? 
be a class of finite relational structures. We denote by 
the number of structures in 
. For any class 
, the function 
. 
of 
lines determined by 
. 
such that every planar graph has obstacle number at most 
concentrated on a single value? 
is a finite set of points which is 2-colored, an empty triangle is a set 
with 
so that the convex hull of 
. We say that 
monochromatic empty triangles. 
vertices have the same deck, then they are isomorphic. 
such that the vertices of any digraph with minimum outdegree 
can be partitioned into two classes so that the minimum outdegree of the subgraph induced by each class is at least 
grid. The first player (if any) to occupy a set of 
be a positive integer. We say that a graph 
is the maximal degree of a graph 
-colorable. 
we have 
. Then 
is graphic. 
be integers. Set 
and 
for 
. Eventually we have 
; put 
.
, since 
, 
, 
, 
, 
, 
, 
, 
.
.
of a locally finite graph 
are prime.
such that if 
and 
are any two vertices of 
is 
of edges such that every vertex is incident to exactly one edge from 
, where 
is some ordinal. This 
as 
.
denote the graph with vertex set consisting of all lines through the origin in 
and two vertices adjacent in 
? 
be improved for the Maximum Edge Disjoint Paths problem (MaxEDP) in planar graphs or can an inapproximability result stronger than 
-hardness? 
Drupal
CSI of Charles University