Problem Given two codes , their Tensor Product is the code that consists of the matrices whose rows are codewords of and whose columns are codewords of . The product is said to be robust if whenever a matrix is far from , the rows (columns) of are far from (, respectively).
The problem is to give a characterization of the pairs whose tensor product is robust.
Problem has the homotopy-type of a product space where is the group of diffeomorphisms of the 4-ball which restrict to the identity on the boundary. Determine some (any?) homotopy or homology groups of .
Conjecture If is a cubic graph not containing a triangle, then it is possible to color the edges of by five colors, so that the complement of every color class is a bipartite graph.
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.
Conjecture Define a array of positive integers where the first row consists of some distinct positive integers arranged in increasing order, and the second row consists of any positive integers in any order. Create a new array where the first row consists of all the integers that occur in the first array, arranged in increasing order, and the second row consists of their multiplicities. Repeat the process. For example, starting with the array , the sequence is: -> -> -> -> -> -> -> -> -> -> -> , and we now have a fixed point (loop of one array).
The process always results in a loop of 1, 2, or 3 arrays.
Let be a graph. If and are two integers, a -colouring of is a function from to such that for each edge . Given a list assignment of , i.e.~a mapping that assigns to every vertex a set of non-negative integers, an -colouring of is a mapping such that for every . A list assignment is a --list-assignment if and for each vertex . Given such a list assignment , the graph G is --colourable if there exists a --colouring , i.e. is both a -colouring and an -colouring. For any real number , the graph is --choosable if it is --colourable for every --list-assignment . Last, is circularly -choosable if it is --choosable for any , . The circular choosability (or circular list chromatic number or circular choice number) of G is
Problem What is the best upper bound on circular choosability for planar graphs?
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?
Given a finite family of graphs and an integer , the Turán number of is the largest integer such that there exists a graph on vertices with edges which contains no member of as a subgraph.
Conjecture For every finite family of graphs there exists an such that .
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.
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?
If is a finite set of points which is 2-colored, an empty triangle is a set with so that the convex hull of is disjoint from . We say that is monochromatic if all points in are the same color.
Conjecture There exists a fixed constant with the following property. If is a set of points in general position which is 2-colored, then it has monochromatic empty triangles.
Problem Given a link in , let the symmetry group of be denoted ie: isotopy classes of diffeomorphisms of which preserve , where the isotopies are also required to preserve .
Now let be a hyperbolic link. Assume has the further `Brunnian' property that there exists a component of such that is the unlink. Let be the subgroup of consisting of diffeomorphisms of which preserve together with its orientation, and which preserve the orientation of .
There is a representation given by restricting the diffeomorphism to the . It's known that is always a cyclic group. And is a signed symmetric group -- the wreath product of a symmetric group with .
Problem Consider the set of all topologically inequivalent polyhedra with edges. Define a form parameter for a polyhedron as where is the number of vertices. What is the distribution of for ?
Conjecture Any linear hypergraph with incidence poset of dimension at most 3 is the intersection hypergraph of a family of triangles and segments in the plane.
login/create account
is an invertible 
matrix, then there is an 
of ![$ [A A] $](/files/tex/d1e9d82c656535b507686183e640178057fae455.png)
so that 
is nonzero. 
, their Tensor Product 
is the code that consists of the matrices whose rows are codewords of 
and whose columns are codewords of 
. The product 
is far from 
be a sequence of nonnegative integers which strictly decreases until 
.
with 
crossings, but not with less crossings. 
has the homotopy-type of a product space 
where 
is the group of diffeomorphisms of the 4-ball which restrict to the identity on the boundary. Determine some (any?) homotopy or homology groups of 
so that every 
, every 
-diregular oriented graph on at most 
vertices has a Hamilton cycle. 
is a cubic graph not containing a triangle, then it is possible to color the edges of 
, is the smallest integer 
so that every sequence of elements of 
has a nontrivial subsequence which sums to zero.
array of positive integers where the first row consists of some distinct positive integers arranged in increasing order, and the second row consists of any positive integers in any order. Create a new array where the first row consists of all the integers that occur in the first array, arranged in increasing order, and the second row consists of their multiplicities. Repeat the process. For example, starting with the array ![$ [1; 1] $](/files/tex/73f8649de444361674c157a2fe98e0c5783f1c46.png)
, the sequence is: ![$ [1; 2] $](/files/tex/83c3d9d7589f716ed6b0f05d26d36dabe8ba47aa.png)
-> ![$ [1, 2; 1, 1] $](/files/tex/a6a696aec4e84df6bc046cf6d30a4df80e156a14.png)
-> ![$ [1, 2; 3, 1] $](/files/tex/98b2f3e4134422c8a286f0326fc2f57ca9be2ab7.png)
-> ![$ [1, 2, 3; 2, 1, 1] $](/files/tex/19a9d24510f4551fa45b950aed32efed0636b355.png)
-> ![$ [1, 2, 3; 3, 2, 1] $](/files/tex/b00d573110ba8c2472820409103dd4cbd7bff7cc.png)
-> ![$ [1, 2, 3; 2, 2, 2] $](/files/tex/2aae90b65ae3f116402a1c0143127f80d86acdf0.png)
-> ![$ [1, 2, 3; 1, 4, 1] $](/files/tex/d614399c4078a70fbffb24eb99816a0974423175.png)
-> ![$ [1, 2, 3, 4; 3, 1, 1, 1] $](/files/tex/bf4dd82eaf95bd71a88cb78d3367efa2c7e4c942.png)
-> ![$ [1, 2, 3, 4; 4, 1, 2, 1] $](/files/tex/a4ef5900a9dde9b32311afe7dee2b143f42c405f.png)
-> ![$ [1, 2, 3, 4; 3, 2, 1, 2] $](/files/tex/ff367376ed7bb74fc6207273d7157062b83a1be6.png)
-> ![$ [1, 2, 3, 4; 2, 3, 2, 1] $](/files/tex/81ba2b3608ddba2fc95d32b74b70279f3f5adc5b.png)
, and we now have a fixed point (loop of one array).
be a graph. If 
and 
are two integers, a 
-colouring of 
from 
to 
such that 
for each edge 
. Given a list assignment 
of 
a set of non-negative integers, an 
such that 
for every 
. A list assignment 
and 
for each vertex 
. Given such a list assignment 
, the graph 
of graphs and an integer 
, the Turán number 
of 
such that there exists a graph on 
such that 
.
Frege system 
but requires exponential size 
proofs. 
denote the graph with vertex set consisting of all lines through the origin in 
and two vertices adjacent in 
? 
be improved for the Maximum Edge Disjoint Paths problem (MaxEDP) in planar graphs or can an inapproximability result stronger than 
-hardness? 
is a finite set of points which is 2-colored, an empty triangle is a set 
with 
so that the convex hull of 
is disjoint from 
. We say that 
monochromatic empty triangles. 
, let the symmetry group of 
ie: isotopy classes of diffeomorphisms of 
of 
is the unlink. Let 
be the subgroup of 
consisting of diffeomorphisms of 
given by restricting the diffeomorphism to the 
is a signed symmetric group -- the wreath product of a symmetric group with 
. 
contains every 2-regular graph on 
be a digraph. If 
, then 
-connected finite graph, is there an assignment of lengths 
to the edges of 
-geodesic cycle is 
where 
for 
? 
-connected graph with a Hamilton cycle has a second Hamilton cycle. 
. The graph 
is defined to be the 
.
. Then 
. 
, we write 
if 
satisfies 
. The problem of finding such an integer 
(with 
) is the Discrete Log Problem.
contains 
, 
-graph if it has a bipartition 
so that every vertex in 
and every vertex in 
. 
be the flow polynomial of a graph 
equals the number of 
for every 2-edge-connected graph 
are independent random variables with ![$ \mathbb{E}[X_i] \leq \mu $](/files/tex/e0268221532981debea25e9446c8ee6f112e1881.png)
, then ![$$\mathrm{Pr} \left( \sum X_i - \mathbb{E} \left[ \sum X_i \right ] < \delta \mu \right) \geq \min \left ( (1 + \delta)^{-1} \delta, e^{-1} \right).$$](/files/tex/03dc1130142ee6fefcc33888e2fb6137211bf327.png)
Drupal
CSI of Charles University