Conjecture There exists a fixed constant (probably suffices) so that every graft with minimum -cut size at least contains a -join packing of size at least .
Conjecture There is an integer-valued function such that if is any -connected graph and and are any two vertices of , then there exists an induced path with ends and such that is -connected.
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 I've been working on this for a long time and I'm getting nowhere. Could you help me or at least tell me where to look for help. Suppose D is an m-by-m diagonal matrix with integer elements all . Suppose X is an m-by-n integer matrix . Consider the partitioned matrix M = [D X]. Obviously M has full row rank so it has a right inverse of rational numbers. The question is, under what conditions does it have an integer right inverse? My guess, which I can't prove, is that the integers in each row need to be relatively prime.
Let be a set, be the set of filters on ordered reverse to set-theoretic inclusion, be the set of principal filters on , let be an index set. Consider the filtrator .
Conjecture If is a completary multifuncoid of the form , then is a completary multifuncoid of the form .
See below for definition of all concepts and symbols used to in this conjecture.
Refer to this Web site for the theory which I now attempt to generalize.
Conjecture Let be a simple -uniform hypergraph, and assume that every set of points is contained in at most edges. Then there exists an -edge-coloring so that any two edges which share vertices have distinct colors.
Question What is the Waring rank of the determinant of a generic matrix?
For simplicity say we work over the complex numbers. The generic matrix is the matrix with entries for . Its determinant is a homogeneous form of degree , in variables. If is a homogeneous form of degree , a power sum expression for is an expression of the form , the (homogeneous) linear forms. The Waring rank of is the least number of terms in any power sum expression for . For example, the expression means that has Waring rank (it can't be less than , as ).
The generic determinant (or ) has Waring rank . The Waring rank of the generic determinant is at least and no more than , see for instance Lower bound for ranks of invariant forms, Example 4.1. The Waring rank of the permanent is also of interest. The comparison between the determinant and permanent is potentially relevant to Valiant's "VP versus VNP" problem.
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 ?
Conjecture The sequence {L(n) mod m}, where L(n) are the Lucas numbers, contains a complete residue system modulo m if and only if m is one of the following: 2, 4, 6, 7, 14, 3^k, k >=1.
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?
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.
Let be a set of points in the plane. Two points and in are visible with respect to if the line segment between and contains no other point in .
Conjecture For all integers there is an integer such that every set of at least points in the plane contains at least collinear points or pairwise visible points.
The famous 0-1 Knapsack problem is: Given and integers, determine whether or not there are values so that The best known worst-case algorithm runs in time times a polynomial in . Is there an algorithm that runs in time ?
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?
Conjecture Let be a cubic graph with no bridge. Then there is a coloring of the edges of using the edges of the Petersen graph so that any three mutually adjacent edges of map to three mutually adjancent edges in the Petersen graph.
Let be a non-empty finite set. Given a partition of , the stabilizer of , denoted , is the group formed by all permutations of preserving each block of .
Problem () Find a sufficient condition for a sequence of partitions of to be complete, i.e. such that the product of their stabilizers is equal to the whole symmetric group on . In particular, what about completeness of the sequence , given a partition of and a permutation of ?
Conjecture (Beneš) Let be a uniform partition of and be a permutation of such that . Suppose that the set is transitive, for some integer . Then
Conjecture Let be the open unit disk in the complex plane and let be open sets such that . Suppose there are injective holomorphic functions such that for the differentials we have on any intersection . Then those differentials glue together to a meromorphic 1-form on .
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)?
Conjecture Let be an -uniform-partite hypergraph. If is the maximum number of pairwise disjoint edges in , and is the size of the smallest set of vertices which meets every edge, then .
Conjecture If is a non-empty graph containing no induced odd cycle of length at least , then there is a -vertex colouring of in which no maximum clique is monochromatic.
login/create account
(probably 
suffices) so that every graft with minimum 
-cut size at least 
contains a 
. 
, what is the smallest integer 
such that 
? 
-graph is an 
with the property that 
for every 
with odd size.
for every 
-flow. 
hyperplanes in dimension 
is not greater than 
such that if 
and 
are any two vertices of 
with ends 
is 
such that the vertices of any digraph with minimum outdegree 
. Suppose X is an m-by-n integer matrix 
. Consider the partitioned matrix M = [D X]. Obviously M has full row rank so it has a right inverse of rational numbers. The question is, under what conditions does it have an integer right inverse? My guess, which I can't prove, is that the integers in each row need to be relatively prime.
into 
so that the graph induced by 
is acyclic for 
. 
be a set, 
be the set of filters on 
be the set of principal filters on 
.
is a completary multifuncoid of the form 
, then 
is a completary multifuncoid of the form 
. 
and a function 
such that if 
, then every saturated 
has cardinality at least 
? 
be a simple 
points is contained in at most 
-edge-coloring so that any two edges which share 
generic matrix? 
for 
. Its determinant is a homogeneous form of degree 
variables. If 
is a homogeneous form of degree 
, the 
(homogeneous) linear forms. The Waring rank of 
means that 
has Waring rank 
(it can't be less than 
).
generic determinant 
(or 
) has Waring rank 
. The Waring rank of the 
generic determinant is at least 
and no more than 
, see for instance 
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 
? 
. 
-connected cubic planar graph can be decomposed into two Hamilton cycles. 
always rational? 
it holds
if 
if 
; \item 
; \item 
. 
(first time when the players occupy the same point) which can be achieved assuming the two players must adopt the same strategy? 
of 
is the graph whose vertices are all binary sequences of length 
be a set of points in the plane. Two points 
and 
in 
there is an integer 
collinear points or 
for every endo-
the following inequality holds 
and 
integers, determine whether or not there are 
values 
so that 
The best known worst-case algorithm runs in time 
times a polynomial in 
?
? 
be improved for the Maximum Edge Disjoint Paths problem (MaxEDP) in planar graphs or can an inapproximability result stronger than 
-hardness? 
? 
be a non-empty finite set. Given a partition 
of 
, is the group formed by all permutations of 
.
) Find a sufficient condition for a sequence of partitions 
of 
is equal to the whole symmetric group 
on 
, given a partition 
of 
be a uniform partition of 
be a permutation of 
. Suppose that the set 
is transitive, for some integer 
. Then 
, every 
vertices has a Hamilton cycle. 
with 
so that 
has a 
. 
be the open unit disk in the complex plane and let 
be open sets such that 
. Suppose there are injective holomorphic functions 
such that for the differentials we have 
on any intersection 
. Then those differentials glue together to a meromorphic 1-form on 
such that every set of at least 
is the maximum number of pairwise disjoint edges in 
is the size of the smallest set of vertices which meets every edge, then 
. 
vertices which contains no complete 
hyperedges. 
vertices which contains no complete 
hyperedges. 
has chromatic number at most 
. 
be an elliptic curve over a number field 
. Then the order of the zeros of its 
-function, 
, at 
is the Mordell-Weil rank of 
. 
, then there is a 
has distinct subset sums if distinct subsets of 
whenever 
has distinct subset sums. 
be an indexed family of sets.
for 
.
on the lattice 
of all finite unions of products.
a bijection from hyperfuncoids 
defining the inverse bijection? If not, characterize the image of the function 
of complements of elements of the set 
Drupal
CSI of Charles University