Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
For list Ramsey numbers, are R_L(K_k,2)=R(K_k,2) for every k, and is R_L(K_3,r)=R(K_3,r) for every r?
Let G be an abelian group. A pair of finite subsets A,B⊆ G with #A=#B and A∩(A+B)=∅ has an acyclic matching if there is a matching f:A→ B such that m_f≠ m_g for every other matching g:A→ B. Weak acyclic matching conjecture. Every abelian…
Let mgeqslant 0 and let R_m,m be the real representation of the Clifford algebra. A transversal graph is an induced complete subgraph on 2^m vertices whose edges represent pairs of basis matrices with disjoint support; the edges are…
(11) Lionel Levine: "Suppose I give you a stable, periodic sandpile con-figuration c on the square grid Z2. Is it decidable whether there is an integer n such that c + nδ 0 (i.e. the addition of n grains of sand to the origin) is not…
Let G be a finite connected simple graph, and fix a vertex of G. The Terwilliger algebra of G is the matrix algebra generated by the adjacency matrix of G and the idempotents corresponding to the distance partition with respect to the…
Let (X^*,d^*) be a finite ultrametric space. Write bf US for the class of finite ultrametric spaces generated by labeled star graphs, and say that two ultrametric spaces are weakly similar if there is a bijection between them whose…
Let G) be a d-regular graph on at most 2d vertices. Nash-Williams' conjecture. G contains ⌊ d/2 ⌋ edge-disjoint Hamilton cycles. Nash-Williams proposed this as a best-possible strengthening of the known lower bound for graphs of minimum…
A triangulation is a plane graph in which every face, including the outer face, is bounded by a triangle. A dominating set of a graph is a set containing every vertex or a neighbor of every vertex. The n/6 domination conjecture. There…
Let f_r(n) be maximal such that, if a graph G has the property that every subgraph H on m vertices is the union of a graph with chromatic number r and a graph with ≤ f_r(m) edges, then G has chromatic number ≤ r+1. Is it true that f_2(n) ≫…
Let D be a normalized difference set with parameters ((q^s+1)(q^2s+1),q^2s+q^s+1,q^s+1) in an abelian group G. A difference set with parameters ((q+1)(q^2+1),q^2+q+1,q+1) is called a minimal difference set when q=p^r, where p is prime and…
Let D_K be a K-IC structure, and let t≥ 1 be the number of bits in each message. Write ℓ_ICC(D_K) for the scalar linear index-code length of the ICC scheme, and let β(D_K) and β_t(D_K) denote the corresponding index-coding broadcast rates.…
Let G=(V,E) be a graph, with the energy game assigning each coalition its graph energy and with φ denoting the Shapley value. Energy-game core conjecture. For the energy game, the Shapley value is in the core. This conjecture asks whether…
Let k≤ n be positive integers. Write Z_n for the integers modulo n, and let Z_n^(k) be the set of k-element subsets of Z_n. A wreath is a set of the form F_π obtained from a permutation π of Z_n by taking the cyclically indexed blocks of k…
Let G be an undirected, connected multigraph with genus g≥ 1 and n≥ 2 vertices. Let N_G, rm Crit_triangle(L_G) and rm Crit_bartriangle(L_G) be the three sets associated with the graph Laplacian, and let P_1,λ be the stated polytope.…
Let a directed graph on k+1 vertices have its arcs partitioned into k arborescences F_1,\ldots,F_k, each with k arcs. Must there always be an arborescence F^\subseteq A such that |F^\cap F_i|=1 for every i?
Let cal F_k(K_n) be the supertoken graph whose vertices represent configurations of k indistinguishable tokens on the complete graph K_n, with adjacency given by moving one token along an edge of K_n. The metric dimension of a graph is the…
Let G be an essentially 6-edge-connected 4-regular graph with a transition system T. A compatible cycle decomposition is a cycle decomposition compatible with the transitions prescribed by T. Fleischner's conjecture. The pair (G,T) has no…
Given a bipartite graph G with edge weights, can we find in polynomial time a maximum weight k-element matching in G that can be extended to a perfect matching?
Question For every d does there exists a g such that every graph with average degree smaller than d and girth at least g has a matching-cut?
(36) Lionel Levine: "The graph Laplacian is the generator of a random walk on a graph. Does the Laplacian of a simplicial complex generate some kind of stochastic process on this higher-dimensional object?" (a) Caroline Klivans: "Look up…