Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let hatG_2n+1 be the graph whose components A have labeled edges, and let η be a label of a component A. A component spanning tree of A is a spanning tree using vertices of A and edges of the component. Label-avoiding spanning-tree…
Let G be a bipartite graph with at least one edge, and consider its two bipartition classes. A vertex is low-frequency if it lies in at most half of the maximal stable sets of G. Frankl's graph conjecture. Each bipartition class of G…
A graph class is hereditary if it is closed under taking induced subgraphs. Such a class is finitely defined if it can be characterised by a finite set of minimal forbidden induced subgraphs. A class is well-quasi-ordered by the induced…
Let G=G(n) be a sequence of simple graphs with even degree sequence d=d(n). Write d_hm for the harmonic mean degree, and let ρ(G) denote the residual entropy and widehatρ(G) the Pauling estimate. Asymptotic Pauling estimate. If d_hm→∞ as…
Beck: Show that the discrepancy of any hypergraph H is at most c|E(H)|^(1/2)
For k∈N, let [k]=1,…,k and let S_k(n) be the set of words in [k]^2n that can be partitioned into two disjoint, identical subwords. A word in S_k(n) is a shuffle square, and n is its semi-length. Since |S_k(n)| is supermultiplicative in n,…
Kolakoski: There is (essentially) a unique sequence over {1,2} which is its own run-length encoding. Is the density of 1's in this sequence 1/2? See this.
Let G be a graph on n vertices with non-abelian automorphism group G=Aut(G) of order n, and let x be a single observation of a graph-filtered signal. Refined non-Abelian dominance hypothesis. The group G achieves strictly higher expected…
(1) Let S⊂R^2 with no three points collinear. Then S determines at least |S|/2 distinct distances. (2) Given n points in R^2 with no three collinear. Then one can remove O(1)-many points so that the number of isosceles triangles is at most…
Let R_piv(k) be the minimum n such that every n-vertex graph contains an independent set or clique of size k as a pivot-minor. Pivot-minor Ramsey conjecture. R_piv(k) ≤ poly(k). This conjecture would imply the polynomial bound for the…
Is curvature related to clustering?
Let G be a 3-connected cubic graph of order n, and let ml(G) denote its minimum leaf number. Minimum-leaf conjecture for 3-connected cubic graphs. ml(G)≤lceiln/16+frac12⌉. The conjecture is presented as open; constructions in the paper are…
Chromatic splitting conjecture: for the p-local sphere spectrum, with chromatic layers L_nS and common fiber F_n\simeq F(L_{n-1}S,L_nS), the map L_{n-1}S\to L_{n-1}L_{K(n)}S should include a wedge summand, so that L_{n-1}L_{K(n)}S\simeq…
Let F_1=F_2=1 and F_n=F_n-1+F_n-2 for n 3. Consider a 3-regular, 3-edge connected, acyclic directed graph with a unique source and a unique sink on 2n vertices. Fibonacci upper-bound conjecture. Such a graph has at most F_n+2+1…
Let G be a graph on n vertices, and let I_f^σ(G) denote the entropy associated with the sphere function. A graph is highly connected here when it is obtained from the complete graph K_n by removing a small number of edges.…
Let Γ be a metric graph of genus g. A minimal rank-determining set is a rank-determining set of Γ that has no proper subset that is rank-determining. Cardinality bound conjecture. Every minimal rank-determining set of Γ has cardinality at…
Can one efficiently reduce the number of bits in the coefficients of an n-variable linear threshold function from, say, n100 bits down to n2 bits? Can one find PC/SA/SOS degree lower bounds for graph iso- morphism formulas ISO(G, H) that do not…
Let G and H be graphs with an identified vertex v. Write G makebox[0ex][l]+ makebox[2ex]_{v} H for their vertex sum at v. Suppose that Z(G)=P(G) and Z(H)=P(H). Vertex-sum conjecture. Then Z(G makebox[0ex][l]+ makebox[2ex]_v H)=P(G…
Let (m,n)→ k mean that every m matchings of size n in any graph have a rainbow matching of size k. The notation (m,n)→_B k has the same meaning for bipartite graphs. Rainbow matching conjecture. (2n,n)→ n. If n is odd, then (2n-1,n)→ n.…
Let e(n,r) be minimal such that every graph on n vertices with at least e(n,r) edges, each edge contained in at least one triangle, must have an edge contained in at least r triangles. Let r≥ 2. Is it true that e(n,r+1)-e(n,r)→ ∞ as n→ ∞?…