Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let G be a graph, and let K=K_i be a covering of G by subgraphs such that every edge, 3-cycle, and 4-cycle of G is contained in some K_i. Let C^ K(G) denote the cubical chain complex generated by cubes whose images are contained in some…
If a graph G contains at most k pairwise edge-disjoint triangles, can all triangles of G be destroyed by deleting at most 2k edges?
Does there exist a 3-critical 3-uniform hypergraph in which every vertex has degree at least 7?
Determine the graphs F for which there exists epsilon greater than 0 such that, for all sufficiently large Delta, some Delta-regular graph G_Delta satisfies d_x(G_Delta,F) less than (1-epsilon)d_x(K_Delta,F).
Let G be an infinite vertex-transitive graph of bounded degree, with every edge assigned length 1 and the resulting graph metric. Let Π_0(G) place one node at each vertex, and let Π_t(G) be obtained by moving these nodes independently…
For each positive integer m, let E_m be the set of exceptional normalized words of length m, and let NW_m be the set of normalized words of length m. Here, a word is exceptional when its hare-fertility exceeds its tortoise-fertility. The…
Let R be a solution of the quantum Yang–Baxter equation (QYBE). Let ε=(ε_i,j)_1≤ i,j≤ n be a transitive n× n matrix with ε_i,j∈1,-1, and define R^(ε):=(R_1,2n^(ε_n,1)… R_n,2n^(ε_n,n))(R_1,2n-1^(ε_n-1,1)……
Let k∈N, and let G be a graph. Write δ(G) and Δ(G) for its minimum and maximum degrees, respectively. Havet–Reed–Stein–Wood conjecture. If δ(G)≥ ⌊2k/3⌋ and Δ(G)≥ k, then every tree with k edges is a subgraph of G. This conjecture proposes…
Let n and k be positive integers, let K_2kn be the complete graph on 2kn vertices, and let [k]=1,2,dotsc,k. A colouring ccolon E(K_2kn)→ [k] is colour-balanced when every colour is used on the same number of edges. For a perfect matching M…
Let G be a finite undirected graph, let Δ(G) denote its maximum degree, and let π(G,z) be its chromatic polynomial. Series-parallel chromatic-root bound. There exists a universal constant C<∞ such that, for every series-parallel graph G of…
For a hyperbolic exponential function f(z)=\lambda e^z, is the finite Hausdorff measure H^h on each finite-width horizontal strip extremal in the sense of Kleinbock, Lindenstrauss, and Barak Weiss?
Devise combinatorial polynomial-time algorithms for the following two problems. Given a graph G, find a subgraph H with O(n) edges such that d_H(X) ≥ Ω(n/m) d_G(X) for every X ⊆ V Given a graph G, find a subgraph H with Ω(n) edges such…
Let W(k,n) be the set of maximal collections of pairwise weakly separated k-subsets of [1… n], and let a (2,4)-move replace one of the two indicated members of a maximal collection by the other while preserving weak separability and…
Let G=(V,E) be an undirected graph and let (s_1,t_1), (s_2,t_2) be two node pairs. Give a combinatorial, polynomial-time algorithm to find edge-disjoint s_1-t_1 and s_2-t_2 paths with minimum total length.
Let M be the class of finite maximal planar graphs. For G∈M, an edge card is a graph of the form G-e, where e∈ E(G). Define ern_M(G) to be the least integer k for which there exist edges e_1,…,e_k∈ E(G) such that the cards G-e_1,…,G-e_k…
Let (G_i) be an infinite family of finite groups. Is it possible to choose generating sets of uniformly bounded size so that the corresponding Cayley graphs form an expander family?
Let G be a (2× n)-game with generic payoff matrices, and let P_G be its correlated equilibrium polytope. A polytope is full-dimensional when it has maximal dimension in its ambient correlated equilibrium space. Smaller-game conjecture. If…
Let P_moblong P_n be the rectangular grid graph, and let its automorphism group act naturally on its vertices. An equitable partition is a partition in which every vertex in a cell has the same number of neighbors in each cell. Grid-graph…
Use number theory to prove non-malleability properties for real-world RSA key-generation algorithms.
Can free spanning forests be used to prove basic properties of the first L^2 Betti number, such as multiplicativity upon passage to a finite-index subgroup?