Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let p_d^n denote the partition-counting numbers considered in the paper, with n and d indexing the relevant family. Sparsity conjecture. Fix integers d,e with 2<d<e. If p_d^n=p_e^m for some integers n,m, then d=3. The conjecture asserts…
Let a Latin square be reduced if its first row and first column are the identity permutation. Let R_n^E and R_n^O denote the numbers of even and odd reduced Latin squares of order n, respectively. Reduced Latin-square parity conjecture.…
Let p≥ 3, let cal A_p be an alphabet of p letters, and let A,B∈cal A_p. For n≥ 2, consider vertices labeled A^n and B^n. A vertex on a path is special if its label has the form A^n-iX^i for some X∈cal A_p∖A,B. Special-vertex conjecture.…
Give an effective input representation for a principally polarized abelian threefold suitable for deciding whether it is a Jacobian.
Let G be a graph with n vertices, m edges and no isolated vertices. The parameter g_0(G) is the corresponding set-mapping parameter defined in the paper. Conjecture on g_0(G). One has g_0(G)=O(m/√ n+n). This is proposed as an upper bound…
For positive integers N,q,a, let Q(N;q,a)=# n∈Z: 0≤ n≤ N-1, qn+a is a perfect square , that is, the number of perfect squares among the N terms a, q+a, 2q+a, …, (N-1)q+a of the arithmetic progression qn+a, and set Q(N)=max Q(N;q,a): q≥ 1,…
For a directed cycle vecC_k, call a directed graph a fractalizer if its extremal induced-copy density is attained by iterated balanced blow-ups of vecC_k. Directed-cycle fractalizer conjecture. For all k≥ 4, vecC_k is a fractalizer. The…
Can we formalize in what sense we believe that conjectured “hard” regions are hard? There are some caveats here because, for instance, statistical physics and the sum-of-squares hierarchy both predict a hard phase for XOR-SAT even though…
Question Do common graphs have bounded chromatic number?
A graph is distance antimagic if and only if all the vertices have a distinct neighborhood.
What is the outcome of a perfectly played game of chess?
Let G be any family of non-complete graphs, and let M_G denote the homoscedastic linear structural equation model associated with G∈G. Generic identifiability conjecture. The graph parameter G of the family M_G_G∈G is generically…
For every Cayley graph G, does there exist r=r(G) such that G covers every graph whose radius-r balls are all isomorphic to the radius-r ball in G?
Let G be a connected graph on n≥ 3 vertices. Let barl denote its average distance and let π denote its proximity, the minimum average distance from a vertex to all other vertices. Three-path conjecture. Among all such graphs, the…
For positive integers a,b,m, if a graph is (a:b)-choosable, must it also be (am:bm)-choosable? Here (a:b)-choosable means that from every assignment of an a-element colour list to each vertex one can choose a b-element subset at each…
: A graph G is said to be uniquely colorable it has only one optimal coloring up to permutation of the colors. (That is, there is only one partition into a minimum number of independent sets.) Is it false that G(n,1/2) is uniquely…
Let us say that two rectangles in the place are independent if both their x- and y-axis projections are disjoint. A set of rectangles is then independent if the rectangles are pairwise independent. Suppose that a collection of…
For every constant C>0, does there exist c>0 such that every graph G on n vertices with no clique or independent set of size at least Clog n contains a nonempty induced regular subgraph on at least clog n vertices?
Let G be a minimal three edge connected simple graph. A twisted graph has the form T=(vecG,G,<,A), where vecG is a directed graph on G, < is a total order, and A is the associated constraint set; it is constraining when the corresponding…
Conjecture 6. 2 9. (Lichiardopol's Conjecture) Every digraph D has some minimal feedback arc set F which contains a path of length δ+ D. 10 Notes: This implies Ho´ ang & Reed (6.20), Caccetta-H¨ aggkvist (2.1), Bermond-Thomassen (6.19),…