Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let G be a graph with n vertices, 2n-2 edges, and an exchange with i. The collapsed graph G' is obtained by identifying vertices 1 and i. Assume that G' has 2n-4 edges with an exchange. Meshkat–Sullivant's conjecture. The graph G has the…
For a graph G on n vertices, let S(G) be the set of real symmetric matrices whose off-diagonal zero pattern is prescribed by adjacency in G. Define mr(G) as the minimum rank of a matrix in S(G) and M(G)=n-mr(G) as the maximum nullity.…
Let A:f=0 be a line arrangement of degree d in the complex projective plane. Let mdr(f) denote the minimal degree of a Jacobian relation for f, and write r=mdr(f). Minimal-degree conjecture. For any line arrangement A:f=0, the integer r is…
Are there deletion-contraction formulas for the polymatroid Tutte polynomial?
For every finite graph G=(V,E), every edge-parameter vector (p_e)_e∈ E∈[0,1]^E, every q∈[0,1], and every pair of distinct edges e,f∈ E, the random-cluster measure φ_G, p,q satisfies φ_G, p,q(e is open,f is open)≤ φ_G, p,q(e is open) φ_G,…
Let T be a set of relatively prime pairs. For (α,β)∈ T, let s^α,β(n) denote the corresponding slow-walk function, define s_T(n)=max_(α,β)∈ Ts^α,β(n), S_T(n)=(α,β):s^α,β(n)=s_T(n), and let Γ=Γ_T=minγ_α,β:(α,β)∈ T, R_T'=(α,β)∈ T:γ_α,β<Γ^2.…
Problem 3.9 (A. Granville). Given a finite field F and an integer n ≥ 1, find the smallest size of a subset E ⊂ F n which determines all directions in Fn.PALO ALTO PROBLEMS 9
In mathematics, the Hales–Jewett theorem is a fundamental combinatorial result of Ramsey theory, named after Alfred W. Hales and Robert I. Jewett, that concerns the degree to which high-dimensional objects must necessarily exhibit some…
The list chromatic number χ_L(G) is defined to be the minimal k such that for any assignment of a list of k colours to each vertex of G (perhaps different lists for different vertices) a colouring of each vertex by a colour on its list can…
Let N_2^e(x) denote the number of integers n≤ x for which S(n)=2^e, and let r_ω_1(e) be the parameter used in the paper to state the preceding bounds. Suppose that r_ω_1(e)≥ 1. The order-of-growth conjecture. As x→∞, x/log x(loglog…
Let (vecU,≤,*,∨,∧) be a distributive universe of separations with an order function, and let overleftarrowx_i:i∈[n] be a set of separations in vecU. A set of separations is a star if its oriented separations point pairwise towards one…
A snark is a connected cubic graph with no proper 3-edge-colouring. A snark is cyclically 4-connected if no edge-cut of size at most 3 separates two subgraphs each containing a cycle. The oddness of a snark is the minimum number of odd…
Conjecture 6.14. For any k and any digraph G, define G∗ to be those vertices with |N +2 (v)| ≥ |N+(v)|. Then any vertex of out-degree k is at distance at most k from a vertex in G∗.Notes: He motivates this with the following remark: "If a…
Let reversible elementary second-order cellular automaton 115 (RESOCA 115) have finite configurations with periods. Two periods p and p+3 are called twins. Twin-period recurrence conjecture. Assume that p and p+3 are twin periods. Then the…
Let T_n denote the class of trees on n vertices, and let W[T_n] be the set of their Wiener indices. Define W^int[T_n] to be the largest interval of contiguous integers contained in W[T_n]. Wiener inverse interval conjecture. The…
Let G be a rigid graph. A graph is quadratically solvable if a generic framework can be solved using quadratic extensions, and radically solvable if a generic framework can be solved using radical extensions. Let F be the recursively…
How many simple graphs are there with a prescribed nonnegative degree sequence d?
For every odd prime p and k≥1, is s(p^k)=k? For k≥2, is d(p^k)=p^k-1d(p)?
Is there a polynomial-time algorithm to sample uniformly from closed 3-manifold triangulations with N tetrahedra, including when restricted to 3-spheres? How do the homotopy groups of clique complexes of exchangeable random graphs behave,…
Let G be a graph, and let P_k denote an induced path on k vertices. An induced path P is avoidable if every extension of P is contained in an induced cycle, where an extension is an induced path obtained by adding one edge to P at each…