Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let G be vertex-transitive and let G_k be a k-net graph of G. Must h(G_k)≥ h(G) whenever G_k is not a single vertex?
Let M_n be the n-th order multiplication-table first-power lattice and let f_1 be its associated permutation-sum function. Define T_n-1=n(n-1)/2. Multiplication-table lattice value conjecture. For n ≥ 2, APD_T_n-1(f_1)=T_n-1!∏_k=1^n-1k!.…
What is the exact value of the Ramsey number R(5,5)?
Given a sign vector ε∈-1,1^k, can the least prime p satisfying (p_i/p)=ε_i for every i≤ k be found in deterministic polynomial time?
For majority dynamics on a given graph, if fixation occurs, how quickly is the final configuration reached, and is unanimity reached or do both opinions survive?
Let G=(V,E) be a finite graph, let T⊆ V(G), and let U=U_1,…,U_k be a partition of E into connected subgraphs. In the model E_4^T, U(G), all edges in each U_i receive the same color, red or blue, independently and with equal probability; a…
Let G_1=(V_1,E_1),…,G_q=(V_q,E_q) be graphs on n_1,…,n_q vertices, respectively, where each G_i is either a complete graph or a tree. Form G by bridge summing G_1 with G_2, G_2 with G_3, and so on, at arbitrary vertices. Let V'=V_1∪…∪ V_q…
Let G be a rooted graph on n vertices, with root r, and let cc_r(G) and CT_r(G) denote its cover cost and cover time from r. The path on n vertices rooted at an endpoint maximises the ratio cc_r(G)/CT_r(G) over all rooted graphs G on n…
For an infinite d-regular Ramanujan graph, does random-walk neighborhood sampling converge to the d-regular tree?
Let G=(V,E) be a finite simple bipartite graph without isolated vertices, with order n=|V| and domination number γ(G)=γ. A unique minimum dominating set is a minimum dominating set of G that is the only one. Define…
Let X_1 and X_2 be graphs on n vertices, and let D(X_i) denote the deck of vertex-deleted subgraphs of X_i. The decks are switching equivalent when there is a bijection between their cards that maps each card to a switching-equivalent…
Let G be a map on a genus g≥ 1 orientable surface. An edge, positive-vertex, positive-face angle labeling means a labeling with the edge condition and positive vertex and face conditions indicated by those parameters. A map is essentially…
Let G be a graph and let x be a vertex that is not a cut vertex of G. Write rm gp_rm o(G) for the outer general position number of G and deg_G(x) for the degree of x in G. Upper-bound conjecture. If x is not a cut vertex of G, then rm…
For an n-vertex graph G, let σ_2(G)=max_uv∈ E(G)(deg_G(u)+deg_G(v))/2. If G_1,G_2 are n-vertex graphs and (σ_2(G_1)+1)(Δ(G_2)+1)≤ n+1, must G_1 and G_2 pack?
The two numbers logα and α^β are algebraically independent over Q.
Let n be the order of a graph, and let a nut graph be a graph whose adjacency matrix is singular with one-dimensional null space spanned by an eigenvector having no zero entries. Vertex and edge orbits are the orbits of the automorphism…
Let G be a graph with no holes of length at least 5. A partition conjecture asserts that V(G) can be partitioned into two sets, neither of which contains a maximum clique of G. This conjecture would imply the bound chi(G) leq 2^omega(G)…
For every linear space L⊆P^n, determine the factorization of its principal matroid determinant E_L into irreducible polynomial factors, including the multiplicity of each factor. Conjecture 7.1 of Matsubara–Heo–Telen asserts an explicit…
Let G be an n-vertex graph, with minimum degree δ(G) and independence number α(G). A square of a Hamilton cycle is the graph obtained by joining vertices whose distance on the Hamilton cycle is at most two. Staden–Treglown conjecture. For…
Let G be a planar trivalent graph, and let M(G) be the moduli space of admissible decorations of G: each edge e is assigned a point D(e)∈CP^2, and at every vertex the decorations on the three incident edges are pairwise orthogonal. For an…