Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Conjecture If M_1,…,M_k are matroids on E and ∑_i=1^k rk_M_i(X_i) ≥ ℓ (k-1) for every partition X_1,…,X_k of E, then there exists X ⊆ E with |X| = ℓ which is independent in every M_i.
Let G and H be graphs, and let G' and H' be chromatic core subgraphs of G and H, respectively. The strong product Gboxtimes H has vertex set V(G)× V(H), with adjacency given by adjacency in either factor while the other coordinate is…
Let T be a tree of order m, and let G be a k-connected graph. Write δ(G) for the minimum degree of G. A tree subgraph is k-redundant if it has the redundancy property intended in the source. Redundant-tree conjecture. If δ(G)≥⌊3k/2⌋+m-1,…
(19) Andrea Sportiello and Jordan Ellenberg: "Can we develop a chip-firing model for cell complexes that includes chips on cells of different dimensions and features interaction between dimensions? Probably, chip configurations and firing…
Study unimodality of families of palindromic polynomials via alternating γ-vectors. Some polynomials to consider are sums over partitions with distinct parts or n choose k_q.
Let (n,r,b) be integers with 0<r≤ n and 1≤ b≤binomnr. An (n,r,b)-matroid is a matroid with n elements, rank r, and exactly b bases. Mayhew–Royle's conjecture. An (n,r,b)-matroid exists for all 0<r≤ n and 1≤ b≤binomnr except…
Let λ be a partition, let λ'⊆λ denote a subpartition in the paper's sense, and let S^2(λ') be the set of score sequences of 2-tournaments with shape λ'. A sequence is deficient according to the paper's preceding definition.…
For a graph H on n vertices, call G ε-far from H if at least ε n^2 edge changes are required to obtain a graph isomorphic to H. A Turán graph is a complete multipartite graph whose parts are as equal in size as possible. Let λ_2 denote the…
Let Q_n be the n-dimensional cube graph, whose vertices are binary strings of length n. For a vertex u, write bar u for the vertex obtained by complementing every bit, and call u and bar u antipodal. An antipodal edge-coloring of Q_n is a…
Let G be a graph of order n, and let k be an integer at least 2. A partition P of V(G) is k-proper if every part P∈P induces a k-connected subgraph of G, where a graph is k-connected if it has more than k vertices and deleting any set of…
Let Gha be a finite cubic vertex transitive graph, and let M be a perfect matching in Gha. Write Gha backslash M for the graph obtained by deleting the edges of M. Lovász's conjecture. There exists a perfect matching M in Gha such that Gha…
Let C_n denote the Catalan triangular array. A matrix is vertically recurrent when it satisfies the paper's vertical recurrence relation. The Catalan-array conjecture. The Catalan array C_n is a vertically-recurrent matrix. This conjecture…
Let G be a finite undirected graph with the following four properties: G is planar: it can be embedded in the Euclidean plane with no two edges crossing. 2. G is 3-vertex-connected: G has at least 4 vertices and, for every set S of at most…
Given C>0, must every red-blue colouring of the pairs from 2,…,n, for all sufficiently large n, contain a monochromatic set X satisfying ∑_x∈ X1/log x≥ C?
Let N_1 denote the positive integers, and let the Loosened Collatz Graph be the graph whose vertices and cycles are defined by the Loosened Collatz Function. Cycle-vertex conjecture. For all n ≠ 0 (mod 3) ∈ N_1, n is a vertex of a cycle.…
Let G be an undirected cop-win graph, and consider optimal play, meaning that the cop minimizes capture time while the robber maximizes it. Hahn's conjecture. The distance between the cop and robber does not increase in consecutive rounds…
Let G be a graph. For vertices u,v and an integer a, let n_a(u,v) be the number of vertices whose distance difference relative to u and v equals a. Call G NT-balanced when n_a(u,v)=n_a(v,u) for every pair of vertices u,v and every relevant…
Let G be the star graph on n vertices, and let H_1,0(G) denote its degree-zero chromatic symmetric homology component. Let S_2^2 1^n-4 be the Specht module indexed by the partition with two parts equal to 2 and n-4 parts equal to 1. Star…
Let G be a bridgeless graph, and let Φ_G(Q) denote its flow polynomial. Haggard–Pearce–Royle conjecture. For any bridgeless graph G, Φ_G(Q)>0 for Q∈[5,∞). This is a proposed weakening of Welsh's conjecture after the explicit counterexample…
Problem Does every connected vertex-transitive graph have a Hamiltonian path?