Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Is it true that any K_r-free graph on n vertices with average degree t contains an independent set on ≫_r log t/tn many vertices?
Babai's problem: which groups are Babai invariant groups?
Let n≥ 1, let p be the number of vertices, and let K be a pure n-simplicial complex. For some 0≤ m≤ n-1, an (m,n)-simplicial cycle sequence is the cycle-sequence notion used in the paper, and α_k(K) denotes the number of k-simplices of K.…
Does there exist a set S⊂N of positive lower asymptotic density for which complete factorization of every input n∈ S is in deterministic polynomial time?
Let L_n be the Morse link numbers, let C_n be the Catalan numbers, let s_2(n) denote the sum of the binary digits of n, and let ξ_2 denote the 2-adic valuation. Let α=dotsc 010111_2 be a 2-adic integer. Postnikov's 2-adic valuation…
Suppose G is a finite group, and let A ⊂ G × G be a subset of density α. Are there ≫_α |G|^3 triples x, y, g such that (x, y), (gx, y), (x, gy) all lie in A?
A BEL gadget is the graph-theoretic gadget used to establish computability of s(H) for a graph H. The parameter s(H) is the minimum degree among all Ramsey H-minimal graphs. BEL-gadget conjecture. Every 2-connected graph has BEL gadgets.…
Let CR(N,c) be a chordal ring graph with diameter k, and let N(k) denote the maximum number of vertices among chordal ring graphs of diameter k. For even k>2, the conjecture concerns the largest possible order of such a graph.…
Let d be a positive integer and let G be a graph. The graph G is d-distinguishing critical if its distinguishing number is d and every proper induced subgraph of G has distinguishing number less than d. Regularity and component conjecture.…
Let G and G' be gap-free graphs. An (im,reg)-invariant extension is a graph G' obtained from G by adding one new vertex, restricting to G on the original vertices, and satisfying im(G')=im(G) and reg(I(G'))=reg(I(G)). Invariant-extension…
Let G be a graph and let ψ be an activity. The activity ψ is strongly Tutte-descriptive if it is Tutte-descriptive and induces a partition 2^E(G)=biguplus_T spanning tree of G[Tbackslash ψ(T),T∪ ψ(T)]. Characterization of strongly…
A cubic graph is a graph in which every vertex has degree three. A cubic graph H is a spanning minor of a cubic graph G if some subdivision of H is a spanning subgraph of G. A Kotzig graph is a cubic graph with a 3-edge-coloring such that…
For which graphs H does the following implication hold: if a graph sequence (G_n) satisfies t_{K_2}(G_n)=(1+o(1))p and t_H(G_n)=(1+o(1))p^{|E(H)|}, then (G_n) is quasirandom with density p?
Let G be a connected graph. The notation Λ_n denotes the class of graphs whose P_n-line graph sequences converge, and G_1,G_2 are subgraphs of G. Non-isomorphic subgraph conjecture. If G_1not≅ G_2 and G_1,G_2∈Λ_n, then G has a sequence…
For R∈N, let f_R(n) be the minimum number of cops needed to catch a robber of speed R on an n× n grid, where the cops move at unit speed. Here “sufficiently large” refers to the robber speed parameter R. Fast-robber grid conjecture. For…
Let K_n be the complete graph on n vertices, let E_c(K_n) denote its complete expansion graph, and let pn(G) be the pagenumber of a graph G. For a positive integer m, set n=2m+1. The pagenumber conjecture. pn(E_c(K_n))=lceiln/2⌉. The…
Let G_1 and G_2 be graphs, and let their bridge-free matroids be the graphical matroids of their respective Δ-subgraphs. Bridge-free matroid criterion. The algebras C_G_1^T and C_G_2^T are isomorphic if and only if their bridge-free…
Let λ be a strict partition and let μ be a partition. The paper defines sets of pairs of tableaux, including overlineT(μ^t,μ,s(T_λ)) and overlineT(μ,μ^t,s(T_λ)), together with a map S^μ^t,μ,tildeλ_s(T_λ),U_μ,U_μ^t,s(T_λ). The…
For every integer r≥ 2, does there exist a constant c_r>0 and an infinite family of bipartite graphs B_n such that ω(B_n^r)→∞ and χ(B_n^r)≥ c_r ω(B_n^r)^2 for all n, where B_n^r is the rth graph power? Equivalently, is the known quadratic…
Let P_m denote the path of order m, and let Box denote the Cartesian graph product. For a graph G, let EISPN(G) denote its efficient isolated private-neighborhood number. EISPN path-product conjectures. If k ≥ 1, then EISPN(P_3 mathbinBox…