An alternating walk in a digraph is a walk so that the vertex is either the head of both and or the tail of both and for every . A digraph is universal if for every pair of edges , there is an alternating walk containing both and
Question Does there exist a locally finite highly arc transitive digraph which is universal?
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 .
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.
Throughout this post, by projective plane we mean the set of all lines through the origin in .
Definition Say that a subset of the projective plane is octahedral if all lines in pass through the closure of two opposite faces of a regular octahedron centered at the origin.
Definition Say that a subset of the projective plane is weakly octahedral if every set such that is octahedral.
Conjecture Suppose that the projective plane can be partitioned into four sets, say and such that each set is weakly octahedral. Then each is octahedral.
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 ?
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 ?
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 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.
Problem Let be a -dimensional smooth submanifold of , diffeomorphic to . By the Jordan-Brouwer separation theorem, separates into the union of two compact connected -manifolds which share as a common boundary. The Schoenflies problem asks, are these -manifolds diffeomorphic to ? ie: is unknotted?
Conjecture Let be a sequence of points in with the property that for every , the points are distinct, lie on a unique sphere, and further, is the center of this sphere. If this sequence is periodic, must its period be ?
Problem Is there an algorithm which takes as input a triangulated 4-manifold, and determines whether or not this manifold is combinatorially equivalent to the 4-sphere?
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 What is the least integer such that every set of at least points in the plane contains collinear points or a subset of points in general position (no three collinear)?
login/create account
so that the vertex 
is either the head of both 
and 
or the tail of both 
. A digraph is universal if for every pair of edges 
, there is an alternating walk containing both 
and 
, there exists a constant 
, so that every graph 
without an induced subgraph isomorphic to 
. 
.
of the projective plane is octahedral if all lines in 
such that 
is octahedral. 
and 
such that each set 
is weakly octahedral. Then each 
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 
-
(mod 
) for every vertex 
. 
the only 3-connected matroid for which equality holds in the bound 
where 
is the circumference (i.e. largest circuit size) of 
? 
of 
is the graph whose vertices are all binary sequences of length 
has an acyclic induced subdigraph of order at least 
. 
satisfies 
. 
, then 
cycles of length 
. 
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. 
is a 2-transition system for 
has a compaible decomposition. 
is for every sets 
and 
be a prime natural number. Find all primes 
, such that 
.
-dimensional smooth submanifold of 
, 
. By the Jordan-Brouwer separation theorem, 
-manifolds which share 
? ie: is 
be a sequence of points in 
with the property that for every 
, the points 
are distinct, lie on a unique sphere, and further, 
is the center of this sphere. If this sequence is periodic, must its period be 
? 
edges whose deletion destroys every odd cycle. 
be a sequence of nonnegative integers which strictly decreases until 
.
with 
crossings, but not with less crossings. 
, every (loopless) graph 
. 
if 
if 
. Assume we start with some number 
. 
such that every set of at least 
Drupal
CSI of Charles University