Given a finite family of graphs and an integer , the Turán number of is the largest integer such that there exists a graph on vertices with edges which contains no member of as a subgraph.
Conjecture For every finite family of graphs there exists an such that .
Let denote the set of all permutations of . Let and denote respectively the number of increasing and the number of decreasing sequences of contiguous numbers in . Let denote the set of subsequences of with length at least three. Let denote .
A permutation is called a Roller Coaster permutation if . Let be the set of all Roller Coaster permutations in .
Conjecture For ,
\item If , then . \item If , then with .
Conjecture (Odd Sum conjecture) Given ,
\item If , then is odd for . \item If , then for all .
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 .
An alternating walk in a digraph is a walk so that the vertex is either the head of both and or the tail of both and for every . A digraph is universal if for every pair of edges , there is an alternating walk containing both and
Question Does there exist a locally finite highly arc transitive digraph which is universal?
Conjecture For every , the sequence in consisting of copes of and copies of has the fewest number of distinct subsequence sums over all zero-free sequences from of length .
An oriented colouring of an oriented graph is assignment of colours to the vertices such that no two arcs receive ordered pairs of colours and . It is equivalent to a homomorphism of the digraph onto some tournament of order .
We say that a set is -universal if every vertex planar graph can be drawn in the plane so that each vertex maps to a distinct point in , and all edges are (non-intersecting) straight line segments.
Question Does there exist an -universal set of size ?
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 .
A covering design, or covering, is a family of -subsets, called blocks, chosen from a -set, such that each -subset is contained in at least one of the blocks. The number of blocks is the covering’s size, and the minimum size of such a covering is denoted by .
Problem Find a closed form, recurrence, or better bounds for . Find a procedure for constructing minimal coverings.
login/create account
![\[ w(G) = \max_{H \subseteq G} \left\lceil \frac{ |E(H)| }{ \lfloor \tfrac{1}{2} |V(H)| \rfloor} \right\rceil. \]](/files/tex/d2391343543ce03d861e6eb2f4985d52e309525d.png)
satisfies 
. 
. 
. The graph 
is defined to be the 
-power of the 
-subdivision of 
.
. Then 
. 
with 
so that 
has a 
. 
of graphs and an integer 
of 
such that 
.
be a matroid of rank 
, and for 
let 
be the number of closed sets of rank 
.
is unimodal. 
denote the set of all permutations of ![$ [n]=\set{1,2,\ldots,n} $](/files/tex/470bd09059264370b76b4da90b77dc370c7e0e7c.png)
. Let 
and 
denote respectively the number of increasing and the number of decreasing sequences of contiguous numbers in 
. Let 
denote the set of subsequences of 
denote 
.
is called a Roller Coaster permutation if 
. Let 
be the set of all Roller Coaster permutations in 
,
, then 
. \item If 
, then 
with 
. 
,
is odd for 
. \item If 
for all 
, and let 
be an eulerian tour of 
, whether there exists a homomorphism from 
for some constant 
? 
so that the vertex 
is either the head of both 
and 
or the tail of both 
. A digraph is universal if for every pair of edges 
, there is an alternating walk containing both 
and 
, the sequence in 
consisting of 
copes of 
and 
copies of 
has the fewest number of distinct subsequence sums over all zero-free sequences from 
. 
is for every sets 
and 
of 
, there is an integer 
so that every strongly 
edge-disjoint Hamilton cycles. 
and 
. It is equivalent to a homomorphism of the digraph onto some tournament of order 
is 
, and all edges are (non-intersecting) straight line segments. 
? 
is 2-large, then 
and 
are 
, then 
of 
. The representation function 
for 
is given by the rule 
. We call 
is never 
.
covering design, or covering, is a family of 
-set, such that each 
.
. Find a procedure for constructing minimal coverings. 
Drupal
CSI of Charles University