Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Conjecture All real roots of nonzero flow polynomials are at most 4.
Problem 3.6 (Brought by V. Lev). Given a prime p, how large can a set A ⊆ Fp be given that the difference between any two elements of A is a quadratic residue modulo p?
Let xi_ℓ,r,c denote the integer in the reduced Gr_2-simplex in layer ℓ, row r, and NE-SW diagonal c, and set ξ_ℓ,r,c=0 when there is no entry in that position. Reduced Gr_2-simplex recurrence conjecture.…
Fix N and let G∈DC_N be a connected DC graph. Let Z'_G be the partial cyclic order obtained by requiring that, for every maximal edge (i,j) of G, the tuples (i,i+1,…,j), (i,i-1,j) and (j,i,j+1) are Z'_G-chains. A circular extension of Z'_G…
Let bmathbbG_∞ be a fixed graph of uniformly bounded degrees on which simple random walk is recurrent, and let bmathbbG_t be non-decreasing subgraphs with bmathbbG_tuparrowbmathbbG_∞. Fixed-graph recurrence conjecture. Simple random walk…
Let T=T_1,1,…,1 be the hedgehog rooted tree (or star rooted tree) with n rays, and let f be a delay function whose values are 1 or 2. The plucking polynomial with delay function is denoted by Q(T,f). Unimodality conjecture. The polynomial…
Let n≥ 1 and m≥ 2. Consider the m-row shapes λ=(n,…,n), widetildeλ=(n+1,n,…,n,n-1). For each integer i, let S_i(λ) and S_i-m+1(widetildeλ) denote the corresponding sets of tableaux with the indicated inversion numbers, and let T_m-2 be the…
Let R(n)=R(n,n) denote the diagonal Ramsey number. Is it true that there exists a constant c>0 such that, for all sufficiently large n, R(n+1)/R(n)≥ 1+c? Is it also true that R(n+1)-R(n)≫ n^2?
This talk considers some of the recent results on n-independent, n-correct, and GCn sets, concerning the Gasca-Maeztu conjecture. Along with the maximal line we consider also line passing through exactly n- nodes, as well as the subset of…
Let m_1≤…≤ m_k and n be sufficiently large. If T is a tree on n vertices and G is the complete multipartite graph with vertex class sizes m_1,…,m_k then prove that R(T,G)≤ (χ(G)-1)(R(T,K_m_1,m_2)-1)+m_1.
For integers n≥ 1 and k, let C^n_1,k be the graph on vertices identified with 1,…,n, obtained from the cycle by adding the edges i,i+k, with vertex labels taken modulo n. Let N_2(G) denote the coefficient of t^2 in Speyer's matroid…
Problem 1.14 (R. Graham). Instead of k-term arithmetic progressions, one could consider a more flexible structure, namely weak k-term arithmetic progressions, which are sets of the form {b nα + βc: 1 ≤ n ≤ k} (for some α ≥ 1 and β). Since…
What can be said about the global or large-scale geometry of graphs and its relationship with differential geometry on manifolds?
For positive integers z,d, let S_z,d be the Q-span of the box products u_ nboxast u_ℓ with len(ℓ)=d and total weight z+d, and write s_z,d=dim_QS_z,d. Dimension conjecture. For all z,d∈Z_>0, s_z,d=binomz+d-1minz,d-1. The claim is based on…
For a large class of random graph models, can semidefinite programs be approximately solved by local algorithms, with comparable performance for problems such as minimum bisection and community detection?
Let P_m and P_n be paths on m and n vertices, respectively, and let P_msquare P_n denote their Cartesian product. For a graph G, write σ_(p,q)(G) for its (p,q)-spreading number. Spreading-number equality conjecture. If m,n≥ 3, then…
Let H be a graph with order h and chromatic number r. Let χ_cr(H) denote its critical chromatic number and let hcf(H) denote its highest common factor. For a balanced r-partite graph G, let barδ(G) be its pairwise minimum degree.…
Let n,m,k be positive integers with m≥ 2. For a positive integer, its base-m expansion is the representation using digits from 0 through m-1; a non-zero digit is a digit in this expansion that is not 0. Sun's conjecture. (I) There are at…
Let q_1 and q_2 be two nonzero algebraic numbers in the unit open disc. Suppose that there is an irreducible element P∈Q[X,Y] such that P(J(q_1),J(q_2))=0. Then there exist a constant c and a positive integer s such that P=cΦ_s, where Φ_s…
Obtain a proof of the following theorem using the polynomial method. Theorem. There is an absolute constant c>0 that the following holds. If A⊂ F_p^n and |A+A|≤ |A|^1+c then A contains a 3AP.