Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
What is the curvature of a network? How to define it?
Let V_n be the standard Vandermonde matrix associated with (1,2,…,n), and let f_V be its associated permutation-sum function. Standard-Vandermonde value conjecture. For n ≥ 2, APD_n-1(f_V)=(n-1)!∏_k=1^n-1k!. The formula completely matches…
Can the Euclidean minimum spanning tree (MST) of n points in R^d be computed in time close to the lower bound of Ω(n log n)?
For an n-vertex graph G and a permutation σ of its vertex set, define I_G(σ)=|E(G)∩ E(σ(G))|, and let f(n,4) be the minimum possible value of |E(G)| over all n-vertex graphs satisfying I_G(σ)≥ 4 for every permutation σ. The problem asks…
Let G=(V,E,s) be an undirected sandpile graph. For U⊆ V, let G|_U be the subgraph induced by U. A connected k-partition of G is a partition Π=bigsqcup_i=1^k V_i such that each G|_V_i is connected. Let G_Π be the graph whose vertices are…
Conjecture For every positive integer k, every digraph with minimum out-degree at least 2k-1 contains k disjoint cycles.
Let G be a finite graph, and let e-positive mean that the chromatic symmetric function of G has a nonnegative expansion in the elementary symmetric-function basis. Induced claw-or-net conjecture. If G is not e-positive, then G contains an…
Let p_d(n) denote the relevant sequence of partition numbers. Hanna's conjecture. There exists a lower-triangular matrix T=(τ_ij), with i,j=0,1,2,…, whose entries are integers and whose diagonal entries are all one, such that…
The question is the following: Question 1. Does there exist an absolute constant c \in N such that for every d \in N the hypercube graph Qd admits a topological drawing in the plane such that there exists no collection of c pairwise…
Problem 3.15 (Brought by T. Tao, originally stated by I. Ruzsa). Choose A ⊆ Fn 2 such that |A + A| ≤ k|A|. Does there exist a subspace V ⊆ Fn 2 such that |V | < k c|A|, and |A ∩ V | ≥ k−c|A|?
For every nonnegative integer i and graph G, let cr_i(G) and tildecr_i(G) denote the minimum numbers of crossings in drawings of G on the orientable and nonorientable surfaces of genus i, respectively. The resulting finite sequences are…
Let G be a graph with vertex set V(G), edge set E(G), n=|V(G)| vertices, and m=|E(G)| edges. Its degree deviation measure is s(G)=∑_v∈ V(G)|deg_G(v)-2m/n|. For integers n and k, let CS(n,k) denote the complete split graph, and let H(n) be…
Let x_1,x_2 be two overlineQ-linearly independent complex numbers and y_1,y_2 be also two overlineQ-linearly independent complex numbers. Then at least one of the four numbers x_1y_1, x_1y_2, x_2y_1, x_2y_2 does not belong to widetildeL.
An n-nucleus is a minimal graph whose n-braid group is not a right-angled Artin group, whereas the n-braid group of every graph contained in it is a right-angled Artin group. Nuclei classification conjecture. There are exactly four…
Let F be a graph and α>1 be such that ex(n,F)=Ω(n^α). Then for any ε > 0 there is n_0 so that if n > n_0 and a graph H is the edge-disjoint union of m=⌈ ε n^α⌉ copies of F, then H contains another copy of F (i.e.\ has at least m+1 copies…
Let G be a snark, and let ω(G) denote its oddness. Oddness-four order conjecture. If ω(G)=4, then |V(G)|≥ 44. The conjecture would be sharp: the cited work constructs a snark with 44 vertices and oddness 4. The paper does not report a…
Let R_k^B(n) denote the number of signed permutations of size n whose burnt-pancake distance from the sorted stack is k. Polynomial formulas conjecture. If n≥1, then R^B_5(n)=1/6n(n-1)(n-2)(6n^2-17n+3),…
A dendrimer nanostar is the nanostar structure obtained by growing a dendrimer through a specified number of stages; a graph is a G_φ-graph if it is realized as G_φ(A) for an appropriate set A, using the Euler φ function as in the paper.…
A finite graph is r-regular if every vertex has degree r, and a Hamilton cycle is a cycle containing every vertex of the graph exactly once. Sheehan's conjecture. There is no finite r-regular graph with a unique Hamilton cycle for any r>2.…
Let G be a cubic graph, and let l be the length of a cycle in G. Cubic-graph cycle-length conjecture. There exist a cycle length l in G and a positive integer k such that 2l≤ 2^k<3l. The conjecture is motivated by the correspondence…