Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let ( A,G,V) be a generic two-action game, with m players, Nash equilibrium set N, and C_l denoting the set of points of C_l-type. For each d∈0,1,…,m, one has ∑_l=0^d | N∩ C_l|≤ !m+∑_l=1^d m l · 2^l-1· !(m-l). Semicontinuity conjecture.…
Let G be a tree with minimal atom-bond connectivity (ABC) index among all trees of size n. The trees T_0,T_1,T_2,T_3,T_4,T_5,T_6 are the structures depicted in Figure~. Gutman–Furtula's revised conjecture. If n satisfies one of the…
Let E_k denote the limit of the expected width of the largest block-palindrome factorization of a length-n word over an alphabet of size k, whose existence is established for every k≥ 2. Let (a_i)_i≥ 1 be the coefficient sequence in the…
Let W_t be the join of the cycle C_t with K_1, let α(G) be the independence number, let χ_f(G) be the fractional chromatic number, and let Box denote the Cartesian product. Odd-wheel triangle-bound conjecture. For all t≥ 3 and all ℓ≥ 1,…
Let G be a graph on n≥ 9 vertices. It is 4-connected if its vertex connectivity is at least 4, and it is 2-cyclic if every vertex set of size at most 2 is dominating or has a cycle in its neighborhood. 4-connected 2-cyclic edge conjecture.…
Let W be any Coxeter group, and let Cay(W) be its undirected right Cayley graph with respect to the simple reflections. For vertices u,v,w, let Conv(u,v,w) denote their convex hull in this graph. The strong hull property is the inequality…
Let P be a d-dimensional polytope with n facets, and let bf c be a generic linear functional. Orient the graph of P according to increasing values of bf c, and denote this directed graph by G(P,bf c). Its unique minimum and maximum…
Let T be a tree on n vertices. For a set B⊆N, say that T is B-burnable if there is a sequence of vertices X=v_1,…,v_j such that bigcup_i∈1,…,jN_b_i[v_i]=V(T), where B=b_1,…,b_j. Here N_r[v] denotes the closed radius-r neighborhood of v.…
Conjecture 4. For a graph G and a non-negative integer g the following are equivalent (1) There exists a drawing of G on an orientable surface of genus g such that cr(M ) is even for every perfect matching M of G. (2) G is 4g -Pfaffian.…
Let p be a prime, and let G=P× A be a finite group where P∈Syl_p(G) is non-abelian and A is an abelian p'-group. Let H be a finite group whose non-commuting graph is isomorphic to that of G, and suppose that |Z(G)|≥ |Z(H)|. Grazian–Monetta…
Let D=(V,E) be a finite directed graph. For a set S⊆ V with S≠∅ and S≠ V, write ∂^+(S)= uv∈ E: u∈ S, v∈ V∖ S , ∂^-(S)= uv∈ E: u∈ V∖ S, v∈ S . Call ∂^+(S) a emphdicut of D if ∂^-(S)=∅, i.e. every edge crossing the partition S,V∖ S leaves S.…
Let G be a graph, let Y_G denote its strict realization space, and let R_ℓ denote the relevant matroid or independence structure. A graph is K_2,3^'-free if it contains no subgraph isomorphic to K_2,3^'. Strict realizability conjecture. If…
Let σ be a weakly consecutive sequence, meaning a permutation of 1,…,k such that if d divides σ(i), then d also divides σ(i± d) wherever these terms are defined. Endpoint-1 conjecture. Any WCS either begins or ends with the term 1;…
Let T be a well-covered tree and let G be a graph. Suppose their independence polynomials agree: I(T;x)=I(G;x). A graph is well-covered if all its maximal stable sets have the same cardinality. Independence-polynomial characterization…
Let G_∞ be the infinite grid, and for positive integers t and r let δ_t,r(G_∞) denote the optimal density of a (t,r) broadcast. Blessing et al.'s conjecture. For all t,r∈Z^+, the optimal (t,r) and (t+1,r+2) broadcast densities on G_∞ are…
Let G and H be graphs, and let K_2 denote the complete graph on two vertices. A pair (G,H) is Ramsey-finite if it has only finitely many Ramsey-minimal graphs. Burr–Erdős–Faudree–Rousseau–Schelp conjecture. If (G,H) is Ramsey-finite, then…
Compactness implies that for every ε>0 there is K>0 such that every finite graph can be approximated within error ε by a finite graph of size K. Give an estimate for K in terms of ε.
(6) Persi Diaconis: "When we play the explorers game and repeatedly explore from the origin on a square lattice in any dimension, the lim-iting shape is round. In dimensions d ≥ 3, the fluctuations after n steps from this ball of radius…
Let G be a nonempty graph, and write b(G) for its bondage number and Δ(G) for its maximum degree. Fink–Hartnell–Kirkland–Rall conjecture. b(G)leqslantΔ(G)+1. The source reports that Teschner disproved this conjecture using K_3× K_3, for…
Problem Find lim_n → ∞ (χ( H_n, 3)) ^ 1 / |V(H_n)| .