Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let d4d8 be a non-trivial hereditary property, and let d4d2(d4d8) be the set of CRGs avoiding its forbidden graphs. For each p a[0,1], let g_K(p) denote the quadratic minimization function associated with a CRG K. Martin's finite CRG…
Let M=(V,E∪ A) be a mixed graph, with directed arcs A and undirected edges E. For U⊂ V, a pseudo dicut is δ_E(U) when no directed arc enters U. Its minimum pseudo dicut size is the smallest cardinality of a pseudo dicut. Mixed-graph…
For a connected nontrivial graph G of order n, let a metric basis be a resolving set of minimum cardinality, let dim(G) denote the metric dimension, and define bf(G)=|bigcapB:B is a metric basis of G|. Determine the maximum possible value…
Does there exist a constant C > 0 such that the following holds? Mubayi and Verstraete [3] noticed that Theorem 15 gives, via sampling from an appropriate C4 -free graph, a lower bound of Ω(t3/2 / log t) on the cycle-complete Ramsey number…
Extend the area-angular-momentum inequality A\geq 8\pi J_S to cosmological constant \Lambda\leq 0, determine the role of extremal anti-de Sitter geometries, and establish the rigidity statement in the area-charge inequality.
Let n and ν be fixed integers with 5≤ν≤ n-2. Let H_n,ν be the graph constructed from the star S_n by adding ν edges between a fixed pendent vertex and ν other pendent vertices. The Sombor index of a graph G is SO(G)=∑_uv∈…
Fix a tuple of graphs (G_1,…,G_d) on vertex set [r], and let W ⊂ (R^2)^⊗ d be the set described by this tuple. Assume that the tuple is a valid graphical description, so each G_j is a disjoint union of c_j complete bipartite graphs.…
Let P be a poset with n elements, and let A_1,…,A_k be the mutually different collections of type Comp(P,ω) for ω∈Σ_P. Suppose that A_i appears for l_i different P-listings, so that l_1+…+l_k=n!. Let A(P) denote the number of automorphisms…
For m∈N with m≥ 2, let U_m=i!:i=1,…,m. For k∈N, let S_U_m,k(n) be the weighted alternating sum associated with the U_m-partition polynomial. Factorial-set sign conjecture. For each k∈0,…,m-2, (-1)^lfloorn+1/2⌋S_U_m,k(n)≥ 0 for n≫0;…
Let G_n be the partition graph, let Ax_n and Sp_n denote its axial and spinal vertex sets, and let I_loc=deg,ω_loc,dim_loc be the specified family of local vertex invariants. For I∈ I_loc, write ρ_I^sp(n) for the spinal concentration…
If C,D⊆ R^2 then the distance between C and D is defined by δ(C,D)=inf_substackc∈ C d∈ D| c-d|. Let h(n) be the maximal number of unit distances between disjoint convex translates. That is, the maximal m such that there is a compact convex…
Let G be a k-chromatic triangle-free graph, and let n_k be the minimum number of vertices in a k-chromatic triangle-free graph. Near-Hamiltonian cycle conjecture. The graph G contains a cycle of length at least n_k-o(n_k). This conjecture…
Let G be a graph without isolated edges. Assign to every edge a list of three real numbers. A weighting from the lists is a function ω:E(G)→R such that each ω(e) belongs to the list assigned to e. Define the induced vertex weight by…
Let G be an n-vertex graph whose rooted balls of size k are all isomorphic. If k>n/2, or if k is within a fixed constant of diam(G), must G be vertex-transitive? Separately, for odd n, is the degree of a uniformly chosen vertex-transitive…
Let P be an integral polytope, and let c(P)=∑_F⊂ P(-1)^codim(F)(dim(F)+1)!Vol(F), where the sum runs over all nonempty faces F of P. Nonnegativity conjecture. The invariant c(P) is nonnegative: c(P)≥ 0. Numerical experiments and examples,…
Let K_a,b be a complete bipartite graph, and let B be a Ferrers board whose rook equivalence graph is K_a,b. Complete bipartite rook equivalence conjecture. Then a=b=1. This conjecture concerns which graphs can arise as rook equivalence…
Let ρ be the evaluation map used in the paper. Assuming the divisibility conjecture, for every integer n define the square matrix M_n by M_n(i,j)=ρ(x^i(1+x)^j)2^-⌊ j/2⌋, 0≤ i,j≤ n. Let d_n=det(M_n). Factorial determinant conjecture. For…
Let G be a graph, let α(G) be its independence number, and let r(G) be its graph radius. Graffiti's radius conjecture. α(G) ≥ r(G) The source verifies the intended bound for the listed graph classes from r(G)≤diam(G)≤ 3≤α(G), but does not…
For any rank-n matroid and bases B_1,\ldots,B_n, do there exist n pairwise disjoint transversal bases, each choosing one representative from every B_i?
For r-partite r-uniform hypergraphs, is the vertex cover number at most (r-1) times the matching number?