Conjecture If is the adjacency matrix of a -regular graph, then there is a symmetric signing of (i.e. replace some entries by ) so that the resulting matrix has all eigenvalues of magnitude at most .
Let be a simple graph, and for every list assignment let be the maximum number of vertices of which are colorable with respect to . Define , where the minimum is taken over all list assignments with for all .
Conjecture [2] Let be a graph with list chromatic number and . Then
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?
The star chromatic index of a graph is the minimum number of colors needed to properly color the edges of the graph so that no path or cycle of length four is bi-colored.
Question Is it true that for every (sub)cubic graph , we have ?
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?
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 four cells at the vertices of a square with horizontal and vertical sides is the winner. What is the outcome of the game given optimal play? Note: Roland Bacher and Shalom Eliahou proved that every 15 x 15 binary matrix contains four equal entries (all 0's or all 1's) at the vertices of a square with horizontal and vertical sides. So the game must result in a winner (the first player) when n=15.
Conjecture Let be an eulerian graph of minimum degree , and let be an eulerian tour of . Then admits a decomposition into cycles none of which contains two consecutive edges of .
A nowhere-zero -flow on is an orientation of together with a function from the edge set of into the real numbers such that , for all , and . The circular flow number of is inf has a nowhere-zero -flow , and it is denoted by .
A graph with maximum vertex degree is a class 1 graph if its edge chromatic number is .
Conjecture Let be an integer and a -regular graph. If is a class 1 graph, then .
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 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 What is the largest connected planar graph of minimum degree 3 which has everywhere positive combinatorial curvature, but is not a prism or antiprism?
login/create account
is the adjacency matrix of a 
-regular graph, then there is a symmetric signing of 
entries by 
) so that the resulting matrix has all eigenvalues of magnitude at most 
. 
be a simple graph, and for every list assignment 
let 
be the maximum number of vertices of 
, where the minimum is taken over all list assignments 
for all 
. 
and 
. Then ![\[\frac{\lambda_r}{r}\geq\frac{\lambda_s}{s}.\]](/files/tex/47be18e956355dd433b88b66eabf01a9e3ed5f61.png)
of edges such that every vertex is incident to exactly one edge from 
of a graph 
? 
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 defined to be 
where 
is the number of faces of 
.
so that every convex 4-polytope has fatness at most 
-dimensional smooth submanifold of 
, 
. By the Jordan-Brouwer separation theorem, 
-manifolds which share 
? ie: is 
grid. The first player (if any) to occupy four cells at the vertices of a square with horizontal and vertical sides is the winner. What is the outcome of the game given optimal play? Note: Roland Bacher and Shalom Eliahou proved that every 15 x 15 binary matrix contains four equal entries (all 0's or all 1's) at the vertices of a square with horizontal and vertical sides. So the game must result in a winner (the first player) when n=15. 
be an eulerian tour of 
-flow 
on 
of 
from the edge set of 
, for all 
, and 
. The circular flow number of 
has a nowhere-zero 
, and it is denoted by 
.
is a class 1 graph if its edge chromatic number is 
be an integer and 
-regular graph. If 
. 
of 
is the graph whose vertices are all binary sequences of length 
be an elliptic curve over a number field 
. Then the order of the zeros of its 
-function, 
, at 
is the Mordell-Weil rank of 
. 
contains every oriented tree of order 
for 
. 
has a homomorphism to 
. 
? 
such that if 
and 
are any two vertices of 
is 
and a function 
such that if 
, then every saturated 
has cardinality at least 
? 
Drupal
CSI of Charles University