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?
For a graph , let denote the cardinality of a maximum cycle packing (collection of vertex disjoint cycles) and let denote the cardinality of a minimum feedback vertex set (set of vertices so that is acyclic).
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 For all positive integers and , there exists an integer such that every graph of average degree at least contains a subgraph of average degree at least and girth greater than .
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 ?
Suppose is a finite group, and is a positive integer dividing . Suppose that has exactly solutions to . Does it follow that these solutions form a subgroup of ?
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 Find a constant such that for any there is a sequence of tautologies of depth that have polynomial (or quasi-polynomial) size proofs in depth Frege system but requires exponential size proofs.
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.
Let be a simple graph, and for every list assignment let be the maximum number of vertices of which are colorable with respect to . Define , where the minimum is taken over all list assignments with for all .
Conjecture [2] Let be a graph with list chromatic number and . Then
Conjecture There is a finite upper bound on the multiplicities of entries in Pascal's triangle, other than the number .
The number appears once in Pascal's triangle, appears twice, appears three times, and appears times. There are infinite families of numbers known to appear times. The only number known to appear times is . It is not known whether any number appears more than times. The conjectured upper bound could be ; Singmaster thought it might be or . See Singmaster's conjecture.
login/create account
so that all pairwise distances between points in 
are rational? 
so that every 
be improved for the Maximum Edge Disjoint Paths problem (MaxEDP) in planar graphs or can an inapproximability result stronger than 
-hardness? 
which cannot be expressed as a union of 
triangle free graphs? 
, the number of even latin squares of order 
for some filter objects 
, 
. Particularly, is this formula true for 
? 
for some filter objects 
, let 
denote the cardinality of a maximum cycle packing (collection of vertex disjoint cycles) and let 
denote the cardinality of a minimum feedback vertex set (set of vertices 
so that 
is acyclic). 
. 
in the hypercube. 
be the number of unordered pairs of nonadjacent vertices (i.e. the number of non-edges), and 
be the size of the smallest 
, then 
. 
-uniform hypergraph on 
vertices which contains no complete 
hyperedges. 
vertices which contains no complete 
hyperedges. 
be a set of ![\[m(A) = - \min_x \sum_{a \in A} \cos(ax).\]](/files/tex/7a772ebd0b7fd98eeab7fda3a5e9674b1dc4c984.png)
What is 
? 
and 
such that every graph of average degree at least 
to the edges of 
-geodesic cycle is 
\item 
is a fixed recursive set of integers.
in this language.
. Suppose that 
. Does it follow that these solutions form a subgroup of 
has chromatic number at most 
. 
has equivalence covering number 
. 
for principal funcoid 
and a set 
Frege system 
but requires exponential size 
proofs. 
. Does the fragment 
have the finite model property? 
such that its fundamental group has an element of finite order?
edges whose deletion destroys every odd cycle. 
let 
be the maximum number of vertices of 
, where the minimum is taken over all list assignments 
for all 
. 
and 
. Then ![\[\frac{\lambda_r}{r}\geq\frac{\lambda_s}{s}.\]](/files/tex/47be18e956355dd433b88b66eabf01a9e3ed5f61.png)
, there exist positive integers 
, 
, 
such that 
.
. 
appears once in Pascal's triangle, 
appears three times, and 
appears 
times. There are infinite families of numbers known to appear 
times is 
. It is not known whether any number appears more than 
. See 
the following inequality holds 
denote the pebbling number of a graph 
. 
Drupal
CSI of Charles University