Conjecture Let be the disjoint union of the graphs and and let be a surface. Is it true that every optimal drawing of on has the property that and are disjoint?
Question Can either of the following be expressed in fixed-point logic plus counting: \item Given a graph, does it have a perfect matching, i.e., a set of edges such that every vertex is incident to exactly one edge from ? \item Given a square matrix over a finite field (regarded as a structure in the natural way, as described in [BGS02]), what is its determinant?
Basic Question: Given any positive integer n, can any convex polygon be partitioned into n convex pieces so that all pieces have the same area and same perimeter?
Definitions: Define a Fair Partition of a polygon as a partition of it into a finite number of pieces so that every piece has both the same area and the same perimeter. Further, if all the resulting pieces are convex, call it a Convex Fair Partition.
Questions: 1. (Rephrasing the above 'basic' question) Given any positive integer n, can any convex polygon be convex fair partitioned into n pieces?
2. If the answer to the above is "Not always'', how does one decide the possibility of such a partition for a given convex polygon and a given n? And if fair convex partition is allowed by a specific convex polygon for a give n, how does one find the optimal convex fair partition that minimizes the total length of the cut segments?
3. Finally, what could one say about higher dimensional analogs of this question?
Conjecture: The authors tend to believe that the answer to the above 'basic' question is "yes". In other words they guess: Every convex polygon allows a convex fair partition into n pieces for any n
Begin with the generating function for unrestricted partitions:
(1+x+x^2+...)(1+x^2+x^4+...)(1+x^3+x^6+...)...
Now change some of the plus signs to minus signs. The resulting series will have coefficients congruent, mod 2, to the coefficients of the generating series for unrestricted partitions. I conjecture that the signs may be chosen such that all the coefficients of the series are either 1, -1, or zero.
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 .
In an edge-colored digraph, we say that a subgraph is rainbow if all its edges have distinct colors, and monochromatic if all its edges have the same color.
Problem Let be a tournament with edges colored from a set of three colors. Is it true that must have either a rainbow directed cycle of length three or a vertex so that every other vertex can be reached from by a monochromatic (directed) path?
Conjecture Let be a circuit in a bridgeless cubic graph . Then there is a five cycle double cover of such that is a subgraph of one of these five cycles.
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.
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 Let be natural numbers with . It follows from the pigeon-hole principle that there exist distinct subsets with . Is it possible to find such a pair in polynomial time?
login/create account
of 
is the minimum number of crossings in all drawings of 
is an invertible 
matrix, then there is an 
of ![$ [A A] $](/files/tex/d1e9d82c656535b507686183e640178057fae455.png)
so that 
is nonzero. 
contains a directed cycle of length at least 
. 
and 
and let 
be a surface. Is it true that every optimal drawing of 
of edges such that every vertex is incident to exactly one edge from 
. Is it true that for large enough~
? 
has distinct subset sums if distinct subsets of 
have distinct sums.
so that 
whenever 
has distinct subset sums. 
vertices can be decomposed into at most 
cycles. 
has an acyclic induced subdigraph of order at least 
. 
of 
has a complete graph on 
vertices as a minor. 
is prime and 
, we write 
if 
satisfies 
. The problem of finding such an integer 
(with 
) is the Discrete Log Problem.
so that every other vertex can be reached from 
, every digraph with minimum out-degree at least 
contains 
. The chromatic number of its square is
if 
, \item at most 
if 
, \item at most 
if 
. 
be a circuit in a bridgeless cubic graph 
for every endo-
? 
vertices, then 
. 
, their Tensor Product 
is the code that consists of the matrices whose rows are codewords of 
and whose columns are codewords of 
be natural numbers with 
. It follows from the pigeon-hole principle that there exist distinct subsets 
with 
. Is it possible to find such a pair 
in polynomial time? 
Drupal
CSI of Charles University