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 .
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.
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.
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 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 Every complete geometric graph with an even number of vertices has a partition of its edge set into plane (i.e. non-crossing) spanning trees.
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 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 a finite family of graphs and an integer , the Turán number of is the largest integer such that there exists a graph on vertices with edges which contains no member of as a subgraph.
Conjecture For every finite family of graphs there exists an such that .
Conjecture Let be a circuit in a bridgeless cubic graph . Then there is a five cycle double cover of such that is a subgraph of one of these five cycles.
Problem Two players start at a distance of 2 on an (undirected) line (so, neither player knows the direction of the other) and both move at a maximum speed of 1. What is the infimum expected meeting time (first time when the players occupy the same point) which can be achieved assuming the two players must adopt the same strategy?
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 
. 
and every rational 
, there is no polynomial-time algorithm for the following problem.
on 
variables, for some 
clauses drawn uniformly at random from the set of formulas on 
simultaneously satisfiable clauses. 
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.
containing a Hamiltonian path.
which is slice, is it a ribbon knot?
) Find a sufficient condition for a straight 
-stage graph to be rearrangeable. In particular, what about a straight uniform graph? 
) Let 
be a simple regular ordered 
-stage graph. Suppose that the graph 
is externally connected, for some 
. Then the graph 
is rearrangeable. 
is a 
of 
of graphs and an integer 
of 
such that there exists a graph on 
such that 
.
generators and exponent 
is a tournament of order 
arc-disjoint transitive subtournaments of order 3. 
such that 
meets 
in at most one vertex, 
. 
are independent random variables with ![$ \mathbb{E}[X_i] \leq \mu $](/files/tex/e0268221532981debea25e9446c8ee6f112e1881.png)
, then ![$$\mathrm{Pr} \left( \sum X_i - \mathbb{E} \left[ \sum X_i \right ] < \delta \mu \right) \geq \min \left ( (1 + \delta)^{-1} \delta, e^{-1} \right).$$](/files/tex/03dc1130142ee6fefcc33888e2fb6137211bf327.png)
can be replaced by a smaller value, we can also write the conjecture as, for any positive 
be a circuit in a bridgeless cubic graph 
(probably 
suffices) so that every embedded (loopless) graph with edge-width 
has a 5-local-tension. 
. 
(first time when the players occupy the same point) which can be achieved assuming the two players must adopt the same strategy? 
let 
. 
be a matroid on 
, let 
be a map, put 
and 
. Then 
has a homomorphism to 
. 
, 
so that 
does not contain an odd edge-cut. 
denote the 
diagonal 
exists. 
Drupal
CSI of Charles University