Conjecture Let be a graph and be a positive integer. The power of , denoted by , is defined on the vertex set , by connecting any two distinct vertices and with distance at most . In other words, . Also subdivision of , denoted by , is constructed by replacing each edge of with a path of length . Note that for , we have . Now we can define the fractional power of a graph as follows: Let be a graph and . The graph is defined by the power of the subdivision of . In other words . Conjecture. Let be a connected graph with and be a positive integer greater than 1. Then for any positive integer , we have . In [1], it was shown that this conjecture is true in some special cases.
Conjecture Let be a Cantor set embedded in . Is there a self-homeomorphism of for every greater than so that moves every point by less than and does not intersect ? Such an embedded Cantor set for which no such exists (for some ) is called "sticky". For what dimensions do sticky Cantor sets exist?
Conjecture \item If is a countable connected graph then its third power is hamiltonian. \item If is a 2-connected countable graph then its square is hamiltonian.
The problem concerns the extension of Monadic Second Order Logic (over a binary relation representing the edge relation) with the following atomic formulas:
\item \item
where is a fixed recursive set of integers.
Let us fix and a closed formula in this language.
Conjecture Is it true that the validity of for a graph of tree-width at most can be tested in polynomial time in the size of ?
Conjecture If a finite set of unit balls in is rearranged so that the distance between each pair of centers does not decrease, then the volume of the union of the balls does not decrease.
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 .
Conjecture For , let be the statement that given any exact -coloring of the edges of a complete countably infinite graph (that is, a coloring with colors all of which must be used at least once), there exists an exactly -colored countably infinite complete subgraph. Then is true if and only if , , or .
Conjecture There exists an integer such that every -arc-strong digraph with specified vertices and contains an out-branching rooted at and an in-branching rooted at which are arc-disjoint.
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 is a bridgelesscubic graph, then there exist 6 perfect matchings of with the property that every edge of is contained in exactly two of .
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 Let be a graph and let such that for any pair there are edge-disjoint paths from to in . Then contains edge-disjoint trees, each of which contains .
For any simple digraph , we let be the number of unordered pairs of nonadjacent vertices (i.e. the number of non-edges), and be the size of the smallest feedback edge set.
Conjecture If is a simple digraph without directed cycles of length , then .
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 .
Question I've been working on this for a long time and I'm getting nowhere. Could you help me or at least tell me where to look for help. Suppose D is an m-by-m diagonal matrix with integer elements all . Suppose X is an m-by-n integer matrix . Consider the partitioned matrix M = [D X]. Obviously M has full row rank so it has a right inverse of rational numbers. The question is, under what conditions does it have an integer right inverse? My guess, which I can't prove, is that the integers in each row need to be relatively prime.
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
login/create account
the following inequality holds 
be an integer and let 
be a minor minimal 
. Then either 
minor for some 
or 
be a graph and 
be a positive integer. The 
power of 
, is defined on the vertex set 
, by connecting any two distinct vertices 
and 
with distance at most 
. Also 
, is constructed by replacing each edge 
of 
, we have 
.
. The graph 
is defined by the 
power of the 
subdivision of 
.
and 
be a positive integer greater than 1. Then for any positive integer 
, we have 
.
of co-prime positive integers 
for 
. 
be a 
. Is there a self-homeomorphism 
of 
greater than 
so that 
does not intersect 
do sticky Cantor sets exist? 
is no more than the maximal size of an induced 
has a complete graph on 
vertices as a minor. 
has a Hamilton cycle. 
\item 
is a fixed recursive set of integers.
in this language.
is prime and 
, we write 
if 
satisfies 
. The problem of finding such an integer 
(with 
) is the Discrete Log Problem.
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)
-connected graph with a Hamilton cycle has a second Hamilton cycle. 
, 
so that 
does not contain an odd edge-cut. 
vertices admit a partition into 
? 
which cannot be expressed as a union of 
triangle free graphs? 
, let 
be the statement that given any exact 
-coloring of the edges of a complete countably infinite graph (that is, a coloring with 
, 
, or 
. 
and 
contains an out-branching rooted at 
is called a Diophantine 
is a perfect square for all 
. 
is a Diophantine quadruple and 
, then 
satisfy 
. Then the elements of 
may be ordered 
and 
so that the sums 
are pairwise distinct. 
of 
denote the graph with vertex set consisting of all lines through the origin in 
and two vertices adjacent in 
? 
it holds
if 
if 
; \item 
; \item 
. 
, the 2-stage Shuffle-Exchange graph/network, denoted 
, is the simple 
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 
. 
such that for any pair 
there are 
edge-disjoint paths from 
. 
and every positive integer 
so that every simple 
has a 
. 
is not an integer. 
contains a directed cycle of length at least 
. 
be the number of unordered pairs of nonadjacent vertices (i.e. the number of non-edges), and 
be the size of the smallest 
, then 
. 
if 
if 
. Assume we start with some number 
. 
has equivalence covering number 
. 
. Suppose X is an m-by-n integer matrix 
. Consider the partitioned matrix M = [D X]. Obviously M has full row rank so it has a right inverse of rational numbers. The question is, under what conditions does it have an integer right inverse? My guess, which I can't prove, is that the integers in each row need to be relatively prime.
, then 
cycles of length 
. 
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 
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?
Drupal
CSI of Charles University