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.
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 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.
Problem The valency-variety of a graph is the number of different degrees in . Is the chromatic number of any graph with at least two vertices greater than
Conjecture Can all problems that can be computed by a probabilistic Turing machine (with error probability < 1/3) in polynomial time be solved by a deterministic Turing machine in polynomial time? That is, does P = BPP?
Given integers , the 2-stage Shuffle-Exchange graph/network, denoted , is the simple -regular bipartite graph with the ordered pair of linearly labeled parts and , where , such that vertices and are adjacent if and only if (see Fig.1).
Given integers , the -stage Shuffle-Exchange graph/network, denoted , is the proper (i.e., respecting all the orders) concatenation of identical copies of (see Fig.1).
Let be the smallest integer such that the graph is rearrangeable.
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 () Find a sufficient condition for a straight -stage graph to be rearrangeable. In particular, what about a straight uniform graph?
Conjecture () Let be a simple regular ordered -stage graph. Suppose that the graph is externally connected, for some . Then the graph is rearrangeable.
Question \item Does hold over graphs of bounded tree-width? \item Is included in over graphs? \item Does have a 0-1 law? \item Are properties of Hanf-local? \item Is there a logic (with an effective syntax) that captures ?
login/create account
. The representation function 
for 
is given by the rule 
. We call 
is never 
.
there is 
such that, for every large 
, there are 
and 
such that 
and 
. 
be an abelian group. Is the 
has chromatic number at most 
.
-degenerate if every subgraph of 
.
, the union of any 
-degenerate graph. 
are simple finite graphs, then 
. 
is the 
paths. 
of co-prime positive integers 
for 
. 
and 
it holds
if 
if 
; \item 
; \item 
. 
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. 
let 
. 
, let 
be a map, put 
and 
. Then 
vertices. 
of 
such that every set of at least 
into 
so that the graph induced by 
is acyclic for 
. 
-minor. 
of a graph 
be an integer and let 
denote the least integer 
, the 2-stage Shuffle-Exchange graph/network, denoted 
, is the simple 
of linearly labeled parts 
and 
, where 
, such that vertices 
and 
are adjacent if and only if 
(see Fig.1).
, the 
-stage Shuffle-Exchange graph/network, denoted 
, is the proper (i.e., respecting all the orders) concatenation of 
identical copies of 
be the smallest integer 
such that the graph 
. 
and 
are 
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 
) Find a sufficient condition for a straight 
-stage graph to be rearrangeable. In particular, what about a straight uniform graph? 
) Let 
-stage graph. Suppose that the graph 
is externally connected, for some 
. Then the graph 
is rearrangeable. 
, then 
cycles of length 
. 
for reloid 
for every funcoid 
(see below mentioned online article).
. 
hold over graphs of bounded tree-width? \item Is 
included in 
over graphs? \item Does 
Drupal
CSI of Charles University