Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
What is the structure of the graph in 1? The report passage is retained verbatim as the relevant context for this extracted problem.
Let T_1 and T_2 be trees of order n. Write T_1triangleleft T_2 when the independence polynomial order satisfies the strict relation, and T_2trianglelefteq T_1 for the corresponding non-strict relation. Oboudi's comparability conjecture. Is…
For every integer n\geq 1, does every graph of minimum degree at least n contain an immersion of the complete graph K_n?
There exist two positive absolute constants c_1 and c_2 with the following property. Let λ_1,…,λ_m be logarithms of algebraic numbers with α_i=e^λ_i \ (1≤ i≤ m), let β_0,…, β_m be algebraic numbers, D the degree of the number field…
Let N=e_1=a_1+…+a_m be the word length, let a^*=max_j a_j, and set N_*=N-a^*. For a uniformly random word with a_j occurrences of the letter j, let M_a_1,…,a_m be its number of inversions, with mean μ=μ(a_1,…,a_m) and standard deviation…
For integers α,β,γ,δ, define G_α,β,γ,δ(n):=det_0≤ i,j≤ n-1(2^i+βbinomi+4j+γ4j+α+binom-i+4j+δ4j+α). Shifted G-determinant identities. For all n≥3, the three chains of identities displayed in the source hold:…
Conjecture Every strong oriented graph in which each vertex has indegree and outdegree at least d contains a directed cycle of length at least 2d+1.
For any ε>0, there exists a constant C(ε)>0 such that, for any nonzero rational integers a_1,…,a_m, b_1,…,b_m with a_1^b_1… a_m^b_mnot=1, |a_1^b_1… a_m^b_m-1|≥ C(ε)^m Bover (|b_1|… |b_m|· |a_1|… |a_m|)^1+ε, where B=max_1≤ i≤ m|b_i|.
For every fixed integer k≥ 2, there exists a constant C_k such that every graph G on n vertices with at least C_k n edges contains pairwise edge-disjoint cycles C_1,…,C_k satisfying V(C_k)⊆…⊆ V(C_1), and such that, for each i∈1,…,k-1, the…
Conjecture: every Laurent polynomial that is Hodge--Tate at infinity is extremal.
David Conlon Question 14. Let g(n) be the smallest number of colors necessary to edge-color Kn such that there are no two vertex-disjoint color-isomorphic triangles. Estimate g(n). \sqrt{ } It is not hard to show that c n \leq g(n) \leq n…
Let r and j be parameters, let z_i be positive integers, and let c_i be coefficients. Define F=∑_s≥ 0a_s(r,j)/n^s+∑_i c_i j(j-1)…(j-z_i+1)frac1n^z_ir^z_i∑_s≥ 0a_s(r,j-z_i)/n^s, with a_0=1. The Awesome conjecture. The coefficients of ln(F)…
For integers n≥ 45 and 13≤ k≤ n-13, let [ n k ]=∑_r a_rq^r be the Gaussian binomial coefficient, so that a_r=[q^r][ n k ]. The sequence of coefficients is log-concave at r when a_r^2≥ a_r-1a_r+1. Central log-concavity conjecture. For any…
We conjecture that for Random Graphs: Combinatorics, Complex Networks and Disordered Systems 903
Let C_2s+1 be the cycle graph on 2s+1 vertices, and let K[C_2s+1] denote its toric ring. Write its h-vector as a sequence with entries h_1,h_2,…,h_s-1 appearing in the indicated positions. The h-vector form conjecture. The h-vector of…
Let a critical graph be a graph minimal with respect to having no good edge-labeling, let its girth be the length of its shortest cycle, and let its average degree be the average of its vertex degrees. For every real number c<4, consider…
Suppose A⊂ F_p[x] is of finite size, and every element of A is a square. Show that |A+A|≥ |A|^1+ε for some constant ε.
Let G be a graph with chromatic number χ(G)=4, and let G.cycleLengths be the set of its cycle lengths. Can the gaps between distinct cycle lengths be arbitrarily large; that is, is it true that for every k∈ N there exist a type V and a…
Let D(n,t) denote the graph used in the construction, let F_3 and F_5 be the graphs shown in the paper, and let Box denote the Cartesian product of graphs. A nut graph is a graph whose adjacency matrix has nullity one and whose…
Let (V,d) be a finite metric space with n points. For distinct points x,y,z∈ V, say that z lies between x and y when d(x,y)=d(x,z)+d(z,y). For distinct x,y∈ V, define the line generated by x and y by overlinexy=x,y∪z∈ V:…