Problem Two players alternately write O's (first player) and X's (second player) in the unoccupied cells of an grid. The first player (if any) to occupy a set of cells having no two cells in the same row or column is the winner. What is the outcome of the game given optimal play?
Conjecture \item If is a 4-edge-connected locally finite graph, then its line graph is hamiltonian. \item If the line graph of a locally finite graph is 4-connected, then is hamiltonian.
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 ?
Given integers , let be the smallest integer such that the symmetric group on the set of all words of length over a -letter alphabet can be generated as ( times), where is the shuffle permutation defined by , and is the exchange group consisting of all permutations in preserving the first letters in the words.
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.
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 simple graph with vertices and list chromatic number . Suppose that and each vertex of is assigned a list of colors. Then at least vertices of can be colored from these lists.
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)?
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
Problem Does the following equality hold for every graph ?
The crossing number of a graph is the minimum number of edge crossings in any drawing of in the plane. In the pairwise crossing number, we minimize the number of pairs of edges that cross.
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 ?
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 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.
Consider a set of great circles on a sphere with no three circles meeting at a point. The arrangement graph of has a vertex for each intersection point, and an edge for each arc directly connecting two intersection points. So this arrangement graph is 4-regular and planar.
Conjecture Every arrangement graph of a set of great circles is -colourable.
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.
login/create account
can be replaced by a smaller value, we can also write the conjecture as, for any positive 
is a graph, we say that a partition of 
is unfriendly if every vertex has at least as many neighbors in the other classes as in its own. 
grid. The first player (if any) to occupy a set of 
cells having no two cells in the same row or column is the winner. What is the outcome of the game given optimal play? 
. The graph 
is defined to be the 
-power of the 
.
. Then 
. 
denote the pebbling number of a graph 
. 
has chromatic number at most 
. 
contains a complete bipartite subgraph with bipartition 
so that 
? 
of a locally finite graph 
\item 
is a fixed recursive set of integers.
and a closed formula 
in this language.
, let 
be the smallest integer 
such that the symmetric group 
on the set of all words of length 
(
times), where 
is the shuffle permutation defined by 
, and 
is the exchange group consisting of all permutations in 
letters in the words. 
, for all 
be a simple 
points is contained in at most 
edges. Then there exists an 
-edge-coloring so that any two edges which share 
be improved for the Maximum Edge Disjoint Paths problem (MaxEDP) in planar graphs or can an inapproximability result stronger than 
-hardness? 
. Suppose that 
and each vertex of 
colors. Then at least 
vertices of 
such that every set of at least 
matrix, then there is an 
of ![$ [A A] $](/files/tex/d1e9d82c656535b507686183e640178057fae455.png)
so that 
is nonzero. 
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 
. 
. Is it true that for large enough~
? ![\[ \text{pair-cr}(G) = \text{cr}(G) \]](/files/tex/8cece1e00bb0e9fc122e0a5cad0dab2681cf33a4.png)
of a graph 
, we minimize the number of pairs of edges that cross. 
the only 3-connected matroid for which equality holds in the bound 
where 
is the circumference (i.e. largest circuit size) of 
? 
satisfy 
. Then the elements of 
and 
so that the sums 
are pairwise distinct. 
be a digraph all of whose strong components are nontrivial. Then 
. 
is the maximum number of pairwise disjoint edges in 
is the size of the smallest set of vertices which meets every edge, then 
. 
of great circles on a sphere with no three circles meeting at a point. The arrangement graph of 
-colourable. 
, for 
a large prime, always contain a rainbow 
if each of the color classes is of size of either 
or 
? 
, their Tensor Product 
is the code that consists of the matrices whose rows are codewords of 
and whose columns are codewords of 
. The product 
Drupal
CSI of Charles University