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 .
Conjecture For every graph without a bridge, there is a flow .
Conjecture There exists a map so that antipodal points of receive opposite values, and so that any three points which are equidistant on a great circle have values which sum to zero.
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 .
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 .
Setup Fix a tree and for every vertex a non-negative integer which we think of as the amount of gold at .
2-Player game Players alternate turns. On each turn, a player chooses a leaf vertex of the tree, takes the gold at this vertex, and then deletes . The game ends when the tree is empty, and the winner is the player who has accumulated the most gold.
Conjecture A Fermat prime is a Fermat number that is prime. The only known Fermat primes are F_0 =3,F_1=5,F_2=17,F_3 =257 ,F_4=65537 It is unknown if other fermat primes exist.
For a finite (additive) abelian group , the Davenport constant of , denoted , is the smallest integer so that every sequence of elements of with length has a nontrivial subsequence which sums to zero.
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?
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 .
An -factor in a graph is a set of vertex-disjoint copies of covering all vertices of .
Problem Let be a fixed positive real number and a fixed graph. Is it NP-hard to determine whether a graph on vertices and minimum degree contains and -factor?
Conjecture Suppose with is a connected cubic graph admitting a -edge coloring. Then there is an edge such that the cubic graph homeomorphic to has a -edge coloring.
login/create account
be a graph, 
a countable end of 
an infinite set of pairwise disjoint 
of pairwise disjoint 
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)
be an integer and let 
be a minor minimal 
. Then either 
minor for some 
or 
.
so that antipodal points of 
receive opposite values, and so that any three points which are equidistant on a great circle have values which sum to zero. 
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 
. 
there is 
such that, for every large 
, there are 
and 
. 
, so that every graph 
. 
and for every vertex 
a non-negative integer 
which we think of as the amount of gold at 
. 
denote the 
diagonal 
exists. ![\[ F_n = 2^{2^n } + 1 \]](/files/tex/0da5a50010e4e5df91c0d58080245ece34ec9ca6.png)
that is prime. The only known Fermat primes are F_0 =3,F_1=5,F_2=17,F_3 =257 ,F_4=65537 It is unknown if other fermat primes exist.
edge-disjoint triangles, then there is a set of 
edges whose deletion destroys every triangle. 
, is the smallest integer 
so that every sequence of elements of 
has a nontrivial subsequence which sums to zero.
of edges such that every vertex is incident to exactly one edge from 
with 
so that 
has a 
. 
be the number of unordered pairs of nonadjacent vertices (i.e. the number of non-edges), and 
be the size of the smallest 
, then 
. 
be a fixed positive real number and 
contains and 
is a connected cubic graph admitting a 
-edge coloring. Then there is an edge 
such that the cubic graph homeomorphic to 
has a 
denote the graph with vertex set consisting of all lines through the origin in 
and two vertices adjacent in 
? 
to the edges of 
-geodesic cycle is 
edges whose deletion destroys every odd cycle. 
is arbitrarily large? 
-size circuits compute the function 
on 
defined inductively by 
, 
, 
, and 
? 
Drupal
CSI of Charles University