Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
For each positive integer n≥ 1 there exists a positive number c(n) having the following property. Let α_1,…,α_n be multiplicatively independent algebraic numbers. Define D=[Q(α_1,…,α_n): Q]. Then ∏_i=1^nh(α_i)≥c(n)over D.
Conjecture For all positive integers g and k, there exists an integer d such that every graph of average degree at least d contains a subgraph of average degree at least k and girth greater than g.
Let G be a graph on at least three vertices. A graph is generically universally rigid in R^1 if every one-dimensional generic framework of it is universally rigid. Workshop characterization conjecture. The graph G is generically…
Let G be a connected triangle-free subcubic graph. Write calpha(G) for its independence number and rm diss(G) for its dissociation number, the maximum cardinality of a vertex set inducing a graph of maximum degree at most one. The…
Let l be a positive integer, and let P(x) be a real polynomial of degree n with leading coefficient a_n. Scaled generalized Tepper identity. One has ∑_k=0^n(-1)^k n choose kP(x-lk)=a_n l^n n!. The preceding theorem proves the case l=1 for…
A 1–3 tree is a tree in which every vertex has degree either 1 or 3. Narins–Pokrovskiy–Szabó conjecture. Every 1–3 tree T of order n has leaf-to-leaf paths of at least log(n+2)-1 distinct lengths. The source proves this claim as a…
Let G be a graph, and let R(G) denote its reconfiguration graph. Here, R(G) is the graph whose vertices represent minimal domination sets of G, with adjacency given by the reconfiguration relation defined in the paper. Let overlineK_n be…
Let k≥ 1. What is the best possible c_k such that R(C_2k+1,H)≤ c_k m for any graph H on m edges without isolated vertices?
Let G be an undirected graph. What is the complexity of computing the rotor-router action of the sandpile group of G on the spanning trees of G?
Let A⊂N be an additive basis of order k which is minimal, in the sense that if B⊂ A is any infinite set then Abackslash B is not a basis of order k. Must there exist an infinite B⊂ A such that Abackslash B is a basis of order k+1?",…
Polynomial Hirsch conjecture: for the family of superstrongly connected d-dimensional simplicial complexes with n vertices, there is a polynomial P in n and d that bounds the diameter of the dual graph of every member by P(n,d).
For each integer n≥ 1, define the Boros--Moll coefficients by P_n(x)=2^-2n∑_k=0^n2^kbinom2n+12k+1(x+1)^k=∑_i=0^nd_i(n)x^i. Extend the finite sequence by setting d_i(n)=0 for i∉0,…,n. Define the log-concavity operator L by…
Conjecture 3. For any nef divisor D on Xn , we have H i (WL , OWL (D|WL )) = 0 for all i > 0, and if further D|WL is big then H i (WL , OWL (KWL + D|WL )) = 0 for all i > 0.1 We highlight three partial results towards the conjecture…
Let H be a Kimura Hadamard matrix (KHM) of order 8k+4. An automorphism is a pair (R,S) acting on H by the relation RH=HS. The known automorphisms have block-diagonal form R=diag(R_1,R_2), S=diag(S_1,S_2), where R_1,S_1∈Mon_4(±1) and…
Let G be a connected graph of order n with m edges, where n-1≤ m≤ n-1choose 2. Define D=⌊frac2n+1-√17+8(m-n)2⌋, k=m-n-D+1choose 2-D+1. For n,D,k, let E_n,D,k be the graph constructed from a path u_0-u_1-…-u_D by joining every vertex of a…
Let (ε_k)_k≥ 0 be independently uniformly chosen at random from -1,1. If R_n counts the number of real roots of f_n(z)=∑_0≤ k≤ nε_k z^k then is it true that, almost surely, lim_n→ ∞R_n/log n=2/π?
For every positive integer t, the classes of K_{t+1}-topological-minor-free graphs and odd K_{t+1}-minor-free graphs are clustered t-colorable, meaning that all monochromatic components have a size bound independent of the graph.
Let A be an ℓ-arrangement and let H∈A. Write A'=A∖H, and let π(A;t) denote the Poincaré polynomial. Assume that A is free and that π(A^H;t) divides π(A;t). Equivalently, assume that π(A';t) divides π(A;t). Modified Orlik's conjecture.…
Let r≥ 3. For an r-uniform hypergraph G let τ(G) denote the covering number (or transversal number), the minimum size of a set of vertices which includes at least one from each edge in G. Determine the best possible t such that, if G is an…
Let T and T' be trees of respective orders n and n'. For each graph G, let f(G) denote the maximum number of vertices that induce a forest in G, and let S_n denote the star on n vertices. Wang–Wu's conjecture. f(T square T') ≤ f(S_n square…