Question Is the binary affine cube the only 3-connected matroid for which equality holds in the bound where is the circumference (i.e. largest circuit size) of ?
Problem Is there a problem that can be computed by a Turing machine in polynomial space and unbounded time but not in polynomial time? More formally, does P = PSPACE?
Problem Is there a minimum integer such that the vertices of any digraph with minimum outdegree can be partitioned into two classes so that the minimum outdegree of the subgraph induced by each class is at least ?
For and positive integers, the (mixed) van der Waerden number is the least positive integer such that every (red-blue)-coloring of admits either a -term red arithmetic progression or an -term blue arithmetic progression.
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 .
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).
The crossing number of is the minimum number of crossings in all drawings of in the plane.
The -dimensional (hyper)cube is the graph whose vertices are all binary sequences of length , and two of the sequences are adjacent in if they differ in precisely one coordinate.
Conjecture For every , there exists an integer such that if is a digraph whose arcs are colored with colors, then has a set which is the union of stables sets so that every vertex has a monochromatic path to some vertex in .
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.
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 .
login/create account
the only 3-connected matroid for which equality holds in the bound 
where 
is the circumference (i.e. largest circuit size) of 
? 
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?
such that the vertices of any digraph with minimum outdegree 
can be partitioned into two classes so that the minimum outdegree of the subgraph induced by each class is at least 
such that 
-
(mod 
) for every vertex 
. 
is defined to be 
where 
is the number of faces of 
.
so that every convex 4-polytope has fatness at most 
we have 
. Then 
is graphic. 
is for every sets 
and 
, there exists a Fibonacci number divisible by 
, 
does not divide 
where 
is the Legendre symbol. 
and 
positive integers, the (mixed) van der Waerden number 
is the least positive integer ![$ [1,n] $](/files/tex/661d0acc09fbc5b62f49645a71cf7d831a26563f.png)
admits either a 
, 
. 
is a 
of 
-graph is an 
for every 
with odd size.
for every 
can be replaced by a smaller value, we can also write the conjecture as, for any positive 
has equivalence covering number 
. 
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). 
. 
of 
is the graph whose vertices are all binary sequences of length 
such that if 
is a digraph whose arcs are colored with 
set which is the union of 
which cannot be expressed as a union of 
triangle free graphs? 
so that all pairwise distances between points in 
is a connected cubic graph admitting a 
-edge coloring. Then there is an edge 
such that the cubic graph homeomorphic to 
has a ![$ p \in [0,1] $](/files/tex/1d076f7332523eb59bd7deae19667f83f0a3b6e0.png)
, we let 
denote a subgraph of 
? 
contains every 2-regular graph on 
vertices as a minor. 
is at most 
.
. 
, let 
be the statement that given any exact 
-coloring of the edges of a complete countably infinite graph (that is, a coloring with 
-colored countably infinite complete subgraph. Then 
, 
, or 
.
Drupal
CSI of Charles University