A directed graph is said to be \(k\)-linked if for any two ordered sets of vertices \((x_1, ..., x_k)\) and \((y_1, ..., y_k)\) there are disjoint paths joining \(x_i\) to \(y_i\) for all \(i\). In a directed graph \(D\), \(\delta^-(D)\) and \(\delta^+(d)\) denote the minimum in-degree and out-degree of vertices in \(D\). A directed graph is strongly connected it for any two vertices \(x\) and \(y\), there is a directed path from \(x\) to \(y\), and strongly \(k\)-connected if it remains strongly connected after deleting any \(k-1\) vertices.
Conjecture: For every \(k\), there is a \(d=d(k)\) such that the following holds. Every strongly \(2k\)-connected tournament with \(\delta^-(T), \delta^+(T)\geq d\) is \(k\)-linked.
It is known that every \(452\)-connected tournament is \(k\)-linked. If the above conjecture is true then the "\(2k\)" bound on the connectedness would be tight.
One motivation for the above conjecture is a related result of Bollobás and Tomason about undirected graphs which says that every \(2k\)-connected graph which is sufficiently dense is \(k\)-linked. Thus the above conjecture could be seen as asking for an analogue of this result for tournaments but with a minimum degree condition instead of an average degree condition.
Highly linked tournaments, A. Pokrovskiy, J. Combin. Theory Ser. B., 115 (2015) 339–347.Conjecture: Let \(G\) be a \(2\)-edge-coloured graph with minimum degree \(\delta(G)\).
The first part of the above conjecture is a separate conjecture of Balogh, Barát, Gerbner, Gyárfás, Sárközy. It has been solved by Letzter (after previously being proved in approximate forms by Balogh, Barát, Gerbner, Gyárfás, Sárközy and by DeBiasio and Nelsen.)
Conjecture: There is a constant \(\alpha>0\) and a function \(C(n)\) tending to infinity such that the following holds. Let \(G\) be a graph on \(n\) vertices with \(2n-2\) edges and no proper induced subgraphs of minimum degree \(3\). Then \(G\) contains cycles of at least \(\alpha C(n)\) distinct lengths between \(0\) and \(C(n)\).
Erdős, Faudree, Gyárfás, and Schelp conjectured that the above should hold with \(\alpha=1\). Together with Narins and Szabó we disproved this.
Conjecture: Let \(G\) be a graph on \(n\) vertices with \(2n-2\) edges and no proper induced subgraphs of minimum degree \(3\). Then \(G\) contains cycles of at least \(3\log_2 n + O(1)\) distinct lengths.
This is a variant of the Erdős-Faudree-Gyárfás-Schelp problem where one looks for many (not necessarily shory) cycle lengths.
Graphs without proper subgraphs of minimum degree 3 and short cycles, L. Narins, A. Pokrovskiy, T. Szabó, Combinatorica, (2016).Conjecture: There is a constant \(\alpha>0\) and a function \(C(n)\) tending to infinity such that the following holds. Let \(T\) be an \(n\) vertex tree all of whose degrees equal to \(1\) or \(3\). Then \(T\) contains at least \(\alpha C(n)\) of distinct leaf-to-leaf path lengths between \(0\) and \(C(n)\).
Conjecture: Let \(T\) be a tree with \(n\) vertices and all degrees equal to \(1\) or \(3\). Then \(T\) has leaf-to-leaf paths of at least \(\log_2 n\) distinct lengths.
These two conjectures arose during our study of cycle lengths in degree 3 critical graphs. They are strictly weaker that the two conjectures in the "cycle lengths in degree 3 critical graphs" section.
Graphs without proper subgraphs of minimum degree 3 and short cycles, L. Narins, A. Pokrovskiy, T. Szabó, Combinatorica, (2016).Conjecture: Every graph \(G\) has a cycle \(C\) such that for any adjacent vertices \(u,v\not\in C\) we have \(d_{G\setminus C}(u)+d_{G\setminus C}(v)\leq |G\setminus C|-2\).
The motivation for the above conjecture is that it would give an alternative proof of Lehel's Conjecture—that the vertices of every graph \(G\) can be partitioned into a cycle in \(G\) and a cycle in the complement of \(G\). Lehel's Conjecture was proved by Bessy and Thomassé after previously being proved for large graphs by Łuczak, Rödl, and Szemerédi, and by Allen.
A related result is true—every graph \(G\) has a cycle \(C\) such that \(\Delta(G[V(G)\setminus V(C))]\leq \frac{1}{2}(|V(G)\setminus V(C)|-1)\). This shows that the weakening of the above conjecture where one replaces "-2" by "-1" is true.
Partitioning a graph into a cycle and a sparse graph, A. Pokrovskiy, arXiv:1607.03348A \(d\)-regular hypergraph \(\mathcal{H}\) with vertex set \([n]\) has the MMS property if for any \(n\) real numbers \(x_1, \dots, x_n\) satisfying \(x_1 + \dots + x_n \geq 0\), there are \(d\) edges \(A\in \mathcal H\) satisfying \(\sum_{a\in A} a\geq 0\).
Problem: Classify all hypergraphs with the MMS property.
The motivation for the above problem is the Manickam-Miklós-Singhi Conjecture which is equivalent to the statement that for \(n\geq 4k\) the complete \(k\)-uniform \(n\)-vertex hypergraph has the MMS property. Thus a full solution to the above problem would be a big generalization of the Manickam-Miklós-Singhi Conjecture. Because of this, I consider the above problem to be very hard and would be interested in any large family of hypergraphs with the MMS property. One such family was found by Sudakov and Huang who proved that all sufficiently large hypergraphs with equal codegrees have the MMS property.
Problem: Classify all (2-uniform) graphs with the MMS property.
For an \(r\)-uniform hypergraph \(\mathcal H\), the strong Ramsey game, \(\mathcal{R}(\mathcal H, \infty)\), is a 2-player game played on the edges of the countably infinite \(r\)-uniform complete graph \(\mathcal K^r_{\infty}\). The two players alternate picking free edges of \(\mathcal K^r_{\infty}\). The first player to claim a copy of \(\mathcal H\) is the winner. If neither player can win (after any finite number of moves), then the game is declared to be a draw.
Question: Is there a (\(2\)-uniform) graph \(G\) such that \(\mathcal{R}(G, \infty)\) is a draw?
Question: For all \(\delta\geq 3\), is there an \(r\)-uniform hypergraph \(\mathcal{H}\) with minimum degree \(\delta\) such that \(\mathcal{R}(\mathcal{H}, \infty)\) is a draw?
It is known that there is a \(5\)-uniform hypergraph \(\mathcal H\) for which the strong Ramsey game \(\mathcal{R}(\mathcal H, \infty)\) ends in a draw. However the presence of a degree \(2\) vertex is cruicial to the drawing strategy, which leads to the above problem.
This area is motivated by a problem of Beck that \(\mathcal{R}(K_n, \infty)\) is a first player win for every complete graph \(K_n\).
Strong Ramsey Games: Drawing on an infinite board, D. Hefetz, C. Kusch, L. Narins, A. Pokrovskiy, C. Requilé, A. Sarid, arXiv:1605.05443Conjecture: For each \(r\) there is a constant \(c_r\), such that in every \(r\)-edge coloured complete graph \(K_n\), there are \(r\) vertex-disjoint monochromatic cycles covering \(n - c_r\) vertices in \(K_n\).
The Erdős-Gyárfás-Pyber Conjecture states that the above conjecture should be true with \(c_r=0\). Sadly, for \(r\geq3\), this was disproved which shows that \(c_r\geq 1\) for \(r\geq3\).
For \(r=2\), the above conjecture is true with \(c_r=0\) (this was proved by Łuczak, Rödl, and Szemerédi for large \(n\); by Allen for smaller but still large \(n\), and by Bessy and Thomassé for all \(n\).) For \(r=3\), the above conjecture was solved independently by Letzter and by me. My proof gives \(c_3\leq 43000\) for sufficiently large \(n\) and Letzter's proof gives \(c_3\leq 60\) for sufficiently large \(n\). I conjecture that \(c_3=1\).
Conjecture: Every \(3\)-edge coloured complete graph \(K_n\), has \(3\) vertex-disjoint monochromatic cycles covering \(n - 1\) vertices.
Partitioning a graph into a cycle and a sparse graph, A. Pokrovskiy, arXiv:1607.03348Conjecture: Suppose that the edges of \(K_{n,n}\) are coloured with \(r\) colours. There is a vertex-partition of \(K_{n,n}\) into \(2r-1\) monochromatic paths.
The \(r=2\) case of this conjecture is a classic result of Gyárfás and Lehel. For \(r=3\), an approximate version was proved by Lang, Schaudt, and Stein—they showed that it is always possible to cover \(2n-o(n)\) vertices of a \(3\)-edge-coloured \(K_{n,n}\) by 5 monochomatic cycles.
Partitioning edge-coloured complete graphs into monochromatic cycles and paths, A. Pokrovskiy, J. Combin. Theory Ser. B., 106 (2014), 70–97.Problem: For some fixed constant \(c\) and every \(r\) construct an \(r\)-uniform \(r\)-partite intersecting hypergraph with \(\tau(\mathcal{H})=r-c\).
This has been solved by Haxell and Scott with the very good constant \(c=4\). The motivation for this problem comes from Ryser's Conjecture a special case of which is that every \(r\)-uniform \(r\)-partite intersecting has \(\tau(\mathcal{H})\leq r-1\). Thus the above problem asks for hypergraphs which are close to extremal for Ryser's Conjecture. The next step in this area is to construct \(r\)-uniform \(r\)-partite intersecting hypergraph with \(\tau(\mathcal{H})=r-1\) for every \(r\).
A family of extremal hypergraphs for Ryser's conjecture, A. Abu-Khazneh, J. Barát, A. Pokrovskiy, T. Szabó, arXiv:1605.06361For a graph \(G\), the cube of \(G\), denoted \(G^3\) is the graph on \(V(G)\) formed by joining any two vertices within distance \(3\) on \(G\) by an edge.
Conjecture: For any \(d\)-regular graph \(G\) \(e(G^3)\geq 2e(G)\).
This was disproved by DeVos and Thomassé. In the same paper they showed that the minimum of the ratio \(\frac{e(G^3)}{e(G)}\) for \(n\)-vertex, \(d\)-regular graphs \(G\) is \(\frac{7}{4}-o(1)\). This solved the underlying problem which motivated the above conjecture.
Growth in graph powers, A. Pokrovskiy, arXiv:1005.2542v1A balanced complete \(k\)-partite graph is a graph whose vertex set is partitioned into \(k\) sets \(V_1, \dots, V_k\) of equal sizes with \(xy\) an edge whenever \(x\in V_i\) and \(y\in V_j\) for \(i\neq j\).
Conjecture: The vertices of every balanced complete \(3\)-partite graph can be covered by \(2\) vertex-disjoint monochromatic paths.
This has been proved by Schaudt and Stein in their paper "Partitioning two-coloured complete multipartite graphs into monochromatic paths".
Calculating Ramsey numbers by partitioning coloured graphs, Annual Berlin-Poznań Seminar, Hamburg, 23/05/2014.
