Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
How many congruent regular tetrahedra can touch at a point? Easy to show it's at least 20, and at most 22. Apparently, this has been open a long time.
Let G^* be an n-vertex connected class 1 Δ-regular graph with Δ>n/3. A vertex-splitting replaces a vertex by two adjacent vertices whose neighborhoods partition the original neighborhood into two nonempty subsets; suppose G is obtained…
Let P(2n+1,1) be the generalised Petersen graph, with n≥ 4. A matching is a set of pairwise vertex-disjoint edges of the graph. Maximum-size matching conjecture. Any matching in P(2n+1,1) has size at most n+1. The conjecture follows from…
Let k ≥ 3 and n ≥ 2k be integers, and let G be a matchable k-connected graph with n vertices. Zaks's conjecture. Every such graph satisfies Φ(G) ≥ k!; moreover, infinitely many graphs attain equality. The conjecture is disproved by the…
The sunflower conjecture is a famous conjecture in extremal combinatorics due to Erdös and Rado (1960). The report passage is retained verbatim as the relevant context for this extracted problem.
What is the size of the largest A⊆ 1,…,N such that all sums ∑_n∈ S1/n are distinct for S⊆ A?
(17) Caroline Klivans: "What are higher dimensional (in the sense of [18] and [17]) critical configurations?" (a) Sam Hopkins: "Are you looking specifically for analogs of stable recurrent configurations? Or do analogs of parking functions…
Let T be a tree of order n, and let P_n denote the path on n vertices. The equidistant dimension of a graph, denoted by eqdim, is the minimum cardinality of a distance-equalizer set. Tree equidistant dimension conjecture. eqdim(T)≤…
Let G be a finite simple graph. A 1-factor of G is a spanning 1-regular subgraph of G, i.e. a perfect matching. A 1-factorization of G is a partition of the edge set E(G) into 1-factors, and G is called 1-factorable if it admits a…
A circulant nut graph C(n,S) is a circulant graph on n vertices whose adjacency matrix has nullity one and whose nullvector has no zero entries; here S=a_1,a_2,…,a_6 specifies the six positive circulant steps, giving degree 12. The…
Does the 1-flowing conjecture hold: does the max-flow min-cut relation hold for every binary matroid with no minor in the excluded-minor set consisting of AG(3,2), T_11, and its dual?
A blow-up of a graph F is obtained by replacing each vertex of F by a non-empty independent set, possibly of a different size, and joining two such sets exactly when their corresponding vertices are adjacent in F. Common blow-up…
Let k≥ 4 and f_k(n) be the largest number of edges in a graph on n vertices which has chromatic number k and is critical (i.e. deleting any edge reduces the chromatic number). Is it true that f_k(n) ≫_k n^2? Is it true that f_6(n)~ n^2/4?…
Let G be a graph of order n, and let a forest cut mean a vertex cut M such that the subgraph G|_M induced by the cut vertices is a forest. Chernyshev–Rauch–Rautenbach conjecture. If G has fewer than 3n-6 edges, then G has a forest cut. The…
Let G and H be graphs, and let Gsquare H denote their Cartesian product. For a vertex u of a graph, let ε(u) be its eccentricity, let d(u,v) be the distance between vertices u and v, and let diam(Gsquare H) be the diameter of the product.…
Let G be a graph. A total weighting is a function ω:E(G)∪ V(G)→1,2, and its induced total vertex weight is w(v):=ω(v)+∑_u∈ N(v)ω(uv). The 1-2-Conjecture. For every graph G, there is a weighting ω:E(G)∪ V(G)→1,2 such that the induced total…
Conjecture The minimum k-norm of a path partition on a directed graph D is no more than the maximal size of an induced k-colorable subgraph.
Let f(A,B) be the partitioning-function quantity discussed in the paper, with A and B positive integers. The asymptotic conjecture for f(A,1). f(A,1)=A+o(A). The source notes that only f(1,1)=4 is known exactly and that the broader bound…
Let G be a connected vacuum Feynman graph, let α( G) denote its large-D exponent, and let P_ G be the associated polynomial. Write valP_ G for the valuation of this polynomial. Primary stranded-graph bound. One has α( G)≤ valP_ G. The…
Let F_n be the folded n-cube obtained from the hypercube Q_n by identifying each vertex u with its antipode; write β(F_n) for its metric dimension. Zhang's conjecture. If n≥ 5 is odd, then β(F_n)=n-1. Zhang et al. established the upper…