Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let B_n be the type-B_n case, and consider the equation referred to in the source as Equation. Starting from the simple graphs and applying the construction described immediately before the conjecture, one obtains π(n) graphs, where π(n)…
Let f_k(n) be minimal such that if n points in R^2 have no k+1 points on a line then there must be at most f_k(n) many lines containing at least k points. Is it true that f_k(n)=o(n^2) for k≥ 4?
Is the minimum-distance problem for cyclic codes NP-hard?
For n≥1, let p(n) be the number of partitions of n, meaning unordered sums of positive integers. Partition-number conjecture. The sequence (p(n))_n=1^∞=(1,2,3,5,7,11,15,…) of partition numbers is not almost realizable. This conjecture…
Let k≥ 2 and let G be a k-partite graph with parts V_1,…,V_k of the same size n. Define the partite minimum degree of G to be the largest integer d such that every vertex has at least d neighbors in each part other than its own. A perfect…
(10) Lionel Levine: "This question is inspired by Criel Merino's work [25] relating the Tutte polynomial to chip-firing. The Tutte polynomial is the most general invariant of a graph that has a deletion-contraction recurrence. Is there a…
Reduce computational problems on arbitrary lattices to corresponding problems on cyclic or ideal lattices.
Given a visibility graph G and a Hamiltonian circuit C, determine in polynomial time whether there is a simple polygon whose vertex visibility graph is G, and whose boundary corresponds to C.
Let n,d≥ 3 be integers, and let G be a connected n-vertex d-regular graph. Write T_unlabeled(G) for the set of isomorphism classes of spanning trees of G. Exponential spanning-tree conjecture. There exists a universal constant c>0…
Let G be a graph of diameter 2 and order n, and let c(G) denote its cop number. Square-root bound conjecture. One should have c(G)≤ √n. The paper proves the weaker bound c(G)≤ √2n and notes that Moore graphs have cop number √n-1, so this…
/Spencer: Consider p(v, t), the probability that a walk beginning from the origin ends at the point v on the d-dimensional integer lattice in time t. Conjecture : Ignoring the obvious "parity issue", this function is unimodal in t >= 0.
Let G=(V,E) be a finite connected D-regular graph with diameter L. The normalized Bakry–Émery curvature at infinity at a vertex x is denoted by K^rm n_G,x(∞). Bakry–Émery curvature Bonnet–Myers conjecture. One has inf_x ∈ V K^rm n_G,x(∞) ≤…
In any graph G, can we always find an edge e such that cr(G - e) ≥ cr(G) - o(cr(G)).
What is the maximum number of edges in a bipartite graph on (m,n) vertices with no complete bipartite subgraph K_s,t?
Let g(n,k,α,m) denote the minimum number of group-testing queries in the model considered, and let a be the query-size parameter. Assume that 1/α is an integer and k+log k+1≤ ⌈ n/a⌉. Optimality conjecture. Under these assumptions, the…
Problem 2: Find a class C2 of 4-uniform hypergraphs such that • the P4-structure of every graph with an M-join belongs to C2, • no odd ring belongs to C2, • C2 belongs to NP.
Let us end with an open problem. simpler than the earlier proofs. However, the proof that I will present today is a new proof using the mixture bound that is due to Maya Sankar. Using the idea in the proof, we can generalize the rainbow…
Given an integer n, determine whether there are rational numbers x,y,z satisfying x^2+y^2=z^2 and xy=2n; equivalently, determine whether n is the area of a right triangle with rational sides.
Let G be an undirected, connected multigraph of genus g≥ 1, and let an R-divisor be a divisor on G with real coefficients. For real numbers r≥ 0 and 0≤ d≤ 2g-2, define ρ(g,r,d)=g-(r+1)(g-d+r). Equal-degree Brill–Noether existence…
For which rational numbers q do there exist infinitely many rational D(q)-quintuples?