Conjecture There exists a fixed constant so that every abelian group has a subset with so that the Cayley graph has no clique or independent set of size .
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.
Problem Let be a graph, a countable end of , and an infinite set of pairwise disjoint -rays in . Prove that there is a set of pairwise disjoint -rays that devours such that the set of starting vertices of rays in equals the set of starting vertices of rays in .
Given integers , the 2-stage Shuffle-Exchange graph/network, denoted , is the simple -regular bipartite graph with the ordered pair of linearly labeled parts and , where , such that vertices and are adjacent if and only if (see Fig.1).
Given integers , the -stage Shuffle-Exchange graph/network, denoted , is the proper (i.e., respecting all the orders) concatenation of identical copies of (see Fig.1).
Let be the smallest integer such that the graph is rearrangeable.
Conjecture Suppose runners having distinct constant speeds start at a common point and run laps on a circular track with circumference 1. Then for any given runner, there is a time at which that runner is distance at least (along the track) away from every other runner.
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 ?
Problem Let be a -dimensional smooth submanifold of , diffeomorphic to . By the Jordan-Brouwer separation theorem, separates into the union of two compact connected -manifolds which share as a common boundary. The Schoenflies problem asks, are these -manifolds diffeomorphic to ? ie: is unknotted?
Conjecture For which values of and are there bi-colored graphs on vertices and different colors with the property that all the monochromatic colorings have unit weight, and every other coloring cancels out?
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.
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 .
Note that the above is a generalization of monotone Galois connections (with and replaced with suprema and infima).
Then we have the following diagram:
What is at the node "other" in the diagram is unknown.
Conjecture "Other" is .
Question What repeated applying of and to "other" leads to? Particularly, does repeated applying and/or to the node "other" lead to finite or infinite sets?
login/create account
. 
be an (additive) abelian group, and for every 
let 
. 
be a matroid on 
, let 
be a map, put 
and 
. Then 
so that every abelian group 
so that the 
has no clique or independent set of size 
. 
is for every sets 
and 
:
, then there is a 
-vertex colouring of 
a countable end of 
an infinite set of pairwise disjoint 
of pairwise disjoint 
suffices) so that every embedded (loopless) graph with edge-width 
has a 5-local-tension. 
, the 2-stage Shuffle-Exchange graph/network, denoted 
, is the simple 
-regular bipartite graph with the ordered pair 
of linearly labeled parts 
and 
, where 
, such that vertices 
and 
are adjacent if and only if 
(see Fig.1).
, the 
-stage Shuffle-Exchange graph/network, denoted 
, is the proper (i.e., respecting all the orders) concatenation of 
identical copies of 
be the smallest integer 
such that the graph 
. 
is 2-large, then 
with 
so that 
has a 
. 
(along the track) away from every other runner. 
for every 
with odd size.
for every 
-dimensional smooth submanifold of 
, 
. By the Jordan-Brouwer separation theorem, 
-manifolds which share 
? ie: is 
is at most 
.
are there bi-colored graphs on 
and every rational 
on 
clauses drawn uniformly at random from the set of formulas on 
simultaneously satisfiable clauses. 
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 
? 
. Is it true that for large enough~
? 
:
;
. 
and 
replaced with suprema and infima).
. 
and 
to "other" leads to? Particularly, does repeated applying 
Drupal
CSI of Charles University