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.
Conjecture Let if is odd and if is even. Let . Assume we start with some number and repeatedly take the of the current number. Prove that no matter what the initial number is we eventually reach .
For and positive integers, the (mixed) van der Waerden number is the least positive integer such that every (red-blue)-coloring of admits either a -term red arithmetic progression or an -term blue arithmetic progression.
A -page book embedding of consists of a linear order of and a (non-proper) -colouring of such that edges with the same colour do not cross with respect to . That is, if for some edges , then and receive distinct colours.
One can think that the vertices are placed along the spine of a book, and the edges are drawn without crossings on the pages of the book.
The book thickness of , denoted by bt is the minimum integer for which there is a -page book embedding of .
Let be the graph obtained by subdividing each edge of exactly once.
Conjecture There is a function such that for every graph ,
Conjecture Let be a finite family of finite sets, not all empty, that is closed under taking unions. Then there exists such that is an element of at least half the members of .
An -factor in a graph is a set of vertex-disjoint copies of covering all vertices of .
Problem Let be a fixed positive real number and a fixed graph. Is it NP-hard to determine whether a graph on vertices and minimum degree contains and -factor?
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.
Problem (2) Find a composite or which divides both (see Fermat pseudoprime) and the Fibonacci number (see Lucas pseudoprime), or prove that there is no such .
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.
login/create account
and 
, the graph 
has equivalence covering number 
. 
has a decomposition into a spanning tree, a family of cycles and a matching. 
to be the maximum degree, 
to be the size of the largest 
to be the chromatic number of 
for every graph 
such that 
or prove that such integers do not exist. 
. Suppose that 
and each vertex of 
colors. Then at least 
vertices of 
is unfriendly if every vertex has at least as many neighbors in the other classes as in its own. 
such that its fundamental group has an element of finite order?
if 
if 
. Assume we start with some number 
of the current number. Prove that no matter what the initial number is we eventually reach 
. 
denote the 
diagonal 
exists. 
be a matroid of rank 
, and for 
let 
be the number of closed sets of rank 
.
is unimodal. 
for every filter objects 
and 
and a funcoid 
? 
is defined to be 
where 
is the number of faces of 
so that every convex 4-polytope has fatness at most 
is called a Diophantine 
-tuple if 
is a perfect square for all 
. 
is a Diophantine quadruple and 
, then 
and 
are 
, then 
positive integers, the (mixed) van der Waerden number 
is the least positive integer ![$ [1,n] $](/files/tex/661d0acc09fbc5b62f49645a71cf7d831a26563f.png)
admits either a 
, 
. 
, is the graph with vertex set 
and two points adjacent if the distance between them is an odd integer. 
? 
has chromatic number at most 
.
are invertible 
matrices with entries in 
for a prime 
, then there is a 
submatrix 
of ![$ [B_1 B_2 \ldots B_p] $](/files/tex/86661dc2948aeca789b4392c2e2a9cbf7d96f735.png)
so that 
of 
such that edges with the same colour do not cross with respect to 
for some edges 
, then 
and 
receive distinct colours. 
is the minimum integer 
be the graph obtained by subdividing each edge of 
be a finite family of finite sets, not all empty, that is closed under taking unions. Then there exists 
such that 
-factor in a graph 
contains and 
, 
does not divide 
where 
is the Legendre symbol. 
structurally stable diffeomorphism is hyperbolic. 
there is a sequence of tautologies of depth 
Frege system 
but requires exponential size 
proofs. 
or 
which divides both 
(see 
(see 
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).
Drupal
CSI of Charles University