Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Is there a meaningful com- binatorial formula (in the spirit of Theorem 1) for the functions WΓ− (X, T ) which is valid for all graphs on a given vertex set? One attempt at answering the previous question is to relate the order complex…
How often is the group of a random elliptic curve over F_q cyclic?
Let Λ_n be the integer grid with vertex set Z^n, with adjacency given by Lee distance 1. Let P_k be the path on k vertices, and let an r-PDDS[P_k] mean an r-perfect distance-dominating set whose components are isomorphic to P_k. Perfect…
Let G be a graph, and let fbarX_G denote its Kromatic symmetric function. Two graphs are isomorphic when they differ only by a relabeling of their vertices. Pierson's conjecture. There do not exist nonisomorphic graphs G and H with…
Let d be sufficiently large, and let n be sufficiently large relative to d. Suppose that G is a connected graph with n vertices and minimum degree at least d, and let T be a uniformly random spanning tree of G. Sharp anticoncentration…
Let n≥ 0 and q≥ 1, and let W^q_n denote the set of Fibonacci q-decreasing words of length n. A 1-Gray code for W^q_n is an ordering of its words in which consecutive words differ in exactly one position. The 1-Gray code conjecture. For any…
Let G be a graph with at least three vertices, and let e be an edge of G. Write G.e for the graph obtained by contracting e. The Wiener index is W(G)=∑_u,v⊂ V(G)d_G(u,v), and the eccentricity of G is ε(G)=∑_u∈ V(G)ε_G(u).…
Popular Furstenberg-Sárközy (Furstenberg-Sárközy) For all ε>0, there exists N_0=N_0(ε) such that for all N≥ N_0, A⊆ [N] with |A|≥ δ N, there exists y≠ 0 such that |x : x,x+y^2∈ A|≥ (δ^2-ε)N, with N_0(ε)≤ e^1/ε^c. (1) Prove lower bounds of…
Adapt Schoof's method to compute zeta functions of curves without unfavorable dependence on the genus.
For each fixed m∈N, let d_l,m:0≤ l≤ m be the coefficient sequence discussed above. For a sequence a_j of positive numbers, define L(a_j)=a_j^2-a_j-1a_j+1. A nonnegative sequence is infinitely log-concave if every number of applications of…
Is there an absolute constant C>0 such that every n-vertex graph with at least Cr^2n edges contains a subdivision of K_r?
Let p=q=1/2, and let W_n,0,0(x) be the probability generating function for the two-player pile game with boundary, with n the initial pile size. Define the first player's winning probability by barw(n):=W_n,0,0(1). A sequence is holonomic…
Open problem 2. In particular, does there exist some constant c > 0 such that every me- dian graph of cube-dimension d has all its radius functions that are Gc\cdotd -unimodal? 2. Perspectives It was asked during the talk whether the…
Let a graph be (anti)palindromic if it has the palindromic or antipalindromic symmetry defined in the paper, and let its order be its number of vertices. Order divisibility conjecture. Every (anti)palindromic graph has order multiple of…
Let G and H be graphs, let I(G;x) denote the independence polynomial of G, and let G∘ H denote their lexicographic product. Symmetry characterization. I(G∘ H;x) is symmetric for every graph G if and only if H=K_r-e for some r≥ 2. This…
Does every planar bipartite graph G satisfy χ_L(G)≤3?
Let n be even, and let Q_n be a random n by n (0,1) matrix whose rows are independent vectors with exactly n/2 zero components. Fixed-row-sum singularity probability conjecture. The probability that Q_n is singular satisfies bf P(Q_n is…
Let n≥ 0, and let f be a polynomial of the form f=∑_k=0^n a_k t^k(1+t)^n-k, a_k≥ 0 (0≤ k≤ n). Let * E:R[t]→R[t] be the Eulerian transformation defined by * E(t^m)=A_m(t), where A_m(t) is the m-th Eulerian polynomial. The paper's…
Given an absolute constant c and polynomials P_1,…,P_m with a total of N coefficients and no common complex zeros, there is no program to find, in at most N^c step, the coefficients of polynomials A_i satisfying B'ezout's relation…
Let ∑_i=0^n b_ix^i be a real rooted polynomial with b_i≥ 0 for all i and let A_i(x) denote the ith Eulerian polynomial. Is the polynomial ∑_i=0^nb_iA_i(x) real rooted? Determine this in general or for particular families of real-rooted…