Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
The cochromatic number of G, denoted by ζ(G), is the minimum number of colours needed to colour the vertices of G such that each colour class induces either a complete graph or empty graph. The dichromatic number of G, denoted by δ(G), is…
For a graph, say that a path spans a subgraph if the vertices of the path are the vertex set of that subgraph. Path-spanning 3-colorability conjecture. If each path of a graph spans a subgraph with chromatic number at most 3, then the…
Let K_k denote the complete graph on k vertices. A relational structure G is irreducible when, whenever A× B→ G, one has A→ G or B→ G. Hedetniemi's irreducibility conjecture. The complete graph K_k is irreducible for every positive integer…
onsider the A_n-1 vector partition function. \begin{itemize} \item How many pieces are there? This is known for n≤ 7, and there is known lower bound of 2^⌊ n/2⌋. \item Understand why some polynomials factor nicely over the arrangement.…
Given an elliptic curve E/F_q and P∈ E(F_q), characterize maps or isogenies ψ:E→ E' for which ψ(P) can be evaluated in time polynomial in logdegψ and log q, ideally O(logdegψ log^2q).
Let S be a properly bounded strategy, let rm RS denote the random strategy, and let ε_S,RS be the metric distance between their P-functions for parameters n and N. Let rm KS^0 denote the excluded key strategy in which players do not start…
Let G be a graph, and let μ(G) denote its Mycielski graph. A graph is semi-transitive if it admits an acyclic orientation with no shortcut. Hameed's conjecture. For every graph G, the graph μ(G) is semi-transitive if and only if G is a…
Let H be the Hamiltonian of the O(1) loop model acting on the link-pattern basis, and let Ψ be the vector whose components are the numbers A_n(π) of fully packed loop states with link-pattern π. The largest eigenvalue of H is 2n. Perron…
Let G be a simple connected graph with n vertices, and let irr_t(G) denote its total irregularity. A graph is regular if all its vertices have the same degree. Second-minimal total irregularity conjecture. If G is not a regular graph, then…
For integers n,k≥ 1, let E^n denote n-dimensional Euclidean space, and let ℓ_s denote a set of s equally spaced collinear points. Write E^n→(ℓ_s,ℓ_k) if every red-blue coloring of E^n contains either a red copy of ℓ_s or a blue copy of…
Assocoipahedra and the moduli space of Riemann surfaces. The met- ric condition defining short-branched trees is related to an equivalence relation appearing in Bodigheimer’s work on the moduli space of Riemann surfaces [1]; the…
Koizumi and Liu conjectured that for every real hyperplane arrangement A, the coefficients of Mag( A;-t) are eventually nonnegative, equivalently that the coefficients of Mag( A;q) eventually alternate in sign. The conjecture is false.…
Given an absolute constant c and polynomials P_1,…,P_m with a total of N coefficients and no common complex zeros, there is no program to find, in at most N^c step, the coefficients of polynomials A_i satisfying B'ezout's relation…
conjecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Noam Lifshitz (joint with Peter Keevash and Dor Minzer) Product free sets in groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .…
For any graph H is there some c=c(H)>0 such that every graph G on n vertices that does not contain H as an induced subgraph contains either a complete graph or independent set on ≥ n^c vertices?
A graph is critical with tree-depth k if its tree-depth is k and every proper minor has smaller tree-depth. The maximum degree of a graph G is denoted by δ(G). The maximum-degree conjecture. Every critical graph with tree-depth k has…
Let G range over chemical graphs, and let σ_t^f(n) denote the total σ-irregularity with the weight function f(n). The graphs described in Theorem~ are the graphs under consideration. **Chemical antiregular graph conjecture.** The same…
Conjecture 6. 3 2. (Thomass´ e) If G is a loopless digon-free digraph the maximum number of induced directed 2-edge paths is n3/15 + O(n2).Notes: First, note that n3/15 + O(n2) can be obtained by substituting C4's inside C4's. Next, given…
Let G be a simple connected graph, let S be the polynomial ring associated with G, and let mathttv(N_G) denote the v-number of its closed neighborhood ideal N_G. Let reg(S/N_G) denote the Castelnuovo–Mumford regularity of the quotient. The…
Let G be a simple graph, let n_G be its number of vertices, and let S^V(G,β) denote its walk entropy at temperature β>0. Temperature-count conjecture. If G is not walk-regular, then there are at most n_G-1 values β>0 such that S^V(G,β)=log…