Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Define the first L^2 Betti number of a vertex-transitive graph G from the expected degree of a free spanning forest. Do G and its square G^2 have the same first L^2 Betti number?
Let n be an even integer, possibly nonpositive, and let j>0. Set v=(n,-1). Let t be either the sequence (-1)v^j-1 or the sequence v^j-1n; both have length 2j-1. The map C_-1,n(-1,-) is defined using the extension of C_m,n to distinct…
Let W(r,k) be the least N such that every coloring of 1,…,N with r colors contains a monochromatic arithmetic progression of length k. Determine the unknown exact values of W(r,k).
Let G be a graph, let k be fixed, and let stGk_r denote the r-restricted graphical Stirling number, where the restricted-set size is indexed by r. Restricted-number monotonicity conjecture. For any graph G and fixed k, the restricted…
For integers k≥ 1 and n≥ 2k+1, let QG(n,k) be the spanning subgraph of the Schrijver graph SG(n,k) constructed in Theorem 1.1, which is a quadrangulation of P^n-2k and satisfies χ(QG(n,k))=n-2k+2. A graph is edge-critical if deleting any…
Let T be a set of relatively prime pairs, and let (α,β)∈ R_T', where R_T'=(α,β)∈ T:γ_α,β<Γ^2, Γ=minγ_α,β:(α,β)∈ T. Let g_t^α,β denote the sequence associated with the (α,β)-walk, and let S_T(n) be the set of pairs attaining…
Let G be a bipartite graph with bipartition V=Asqcup B. Write Δ_A and Δ_B for the maximum degrees of vertices in A and B, respectively. The graph is (k_A,k_B)-choosable if every list assignment giving vertices of A lists of size k_A and…
Problem 1.2 (T. Tao). Is there a hypergraph regularity lemma for subsets of pseu-dorandom sparse hypergraphs of large density? If so, it would give a new proof that there are arbitrarily long arithmetic progressions among the primes, which…
Fix a positive integer m for which the equation m^2 + m_1^2 + m_2^2 = 3 mm_1m_2 has a solution in positive integers (m_1,m_2) with 0<m_1≤ m_2≤ m. Then such a pair (m_1,m_2) is unique.
Let G be an R-disjoint graph. Write B(G) for its bipartite part, and for each odd cycle C of G, let R(C) denote the subgraph associated with C. Determinantal factorization conjecture. Then det A(G)=det A(G[B(G)])∏_Cdet A(G[R(C)]). The…
For a point (x,y,z)∈Z^3, let T(x,y,z)=(x',y,z):x'≥ x∪(x,y',z):y'≥ y∪(x,y,z'):z'≥ z⊆Z^3, the union of the three axis-parallel rays of lattice points issuing from (x,y,z) in the positive coordinate directions; the point (x,y,z) is called the…
Let G_n be the set of graphs of order n. For a graph G with n vertices and m edges, let M_1(G) and M_2(G) denote its first and second Zagreb indices, respectively. Define A=G∈ G_n:M_1(G)/n>M_2(G)/m, B=G∈ G_n:M_1(G)/n=M_2(G)/m. The A–B…
Identify and solve tractable special cases of the signature problem described in the slides.
Let n be a positive integer, let ∇_* be the operator on symmetric functions in two alphabets defined by ∇_*widetilde H_μ=widetilde H_μ⊗widetilde H_μ, and let RTT_0(n) denote the relevant family of rooted tiered trees of size n. For each T,…
Given a prime p and a coprime to p, can ord_p(a) be computed in deterministic polynomial time?
Fishburn, Pekec, Reeds: How many comparisons are needed to determine a linear order of the Boolean poset? That is, what is the fewest number of questions of the form "Is S < T?" must one ask in order to find out a linear ordering of all…
Let a separating cut be a cut in a matchable graph whose contraction produces a graph, and let pf(G) denote the pfaffian number of a graph G. Separating-cut preservation problem. Characterize the separating cuts whose contractions preserve…
The crossing number cr(G) of G is the minimum number of crossings in all drawings of G in the plane. Conjecture cr(K_n) = frac 14 floorfrac n2 floorfracn-12 floorfracn-22 floorfracn-32
Let a food quiver be the directed graph whose vertices are foods and whose arrows record the relevant food-containment relations. An infinity-food is a recursively constructed food whose structure is encoded by such a quiver; a homological…
Let X be the space of k-regular Cayley graphs with the local-convergence topology and let T⊂ X be the closed subset of transient graphs. Is the Green function, equivalently the expected number of returns to the identity, continuous on T?