Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let Z be the zigzag graph, let ∂_MZ and ∂_minZ denote its Martin and minimal entrance boundaries, and let U^(2) be the space of pairs (U_uparrow,U_downarrow) of disjoint open subsets of [0,1] arising in the boundary parametrization. For…
Is the i.i.d. action of the free group F_2 a local-global limit of finite actions of F_2?
Let k≥ 1 and let T_n,T_n-1,…,T_n-k+1 be trees, where T_n-j has n-j vertices. The trees pack into K_n when they can be found as pairwise edge-disjoint subgraphs of the complete graph K_n. Bollobás's conjecture. For every k≥ 1 there is an…
For a bridgeless graph G, let scc(G) denote the length of a shortest cycle cover of G. Shortest Cycle Cover Conjecture. If G is a bridgeless graph, then scc(G)≤ 7/5|E(G)|. This conjecture gives a sharp proposed upper bound for shortest…
Let G be a simple, finite, undirected graph with N vertices that is d-regular, and let i(G) denote its number of independent sets. The graph N/2dK_d,d is the disjoint union of N/2d copies of the complete bipartite graph K_d,d. Alon–Kahn…
Does there exist a finite upper bound on how many times a number (other than 1) can appear in Pascal's triangle?
If A and B are countably infinite groups, does A× B have fixed price 1?
\begin{enumerate} \item[(a)]Consider the Ehrhart polynomial of a lattice polytope P. Below are two well-known representations of i(P;t): i(P;t) = ∑_i=1^d c_it^i = ∑_i=0^d h_i^* binomt+d-id. Fix k∈ mathbbZ_>0 and write i(P;t) in the basis…
Let G be an HZ-graph, meaning a connected Class 2 graph with Δ(G_Δ)≤2, and let P^* be the Petersen graph with one vertex removed. Let O_Δ be the graph class defined in the paper. HZ-graph classification conjecture. If G is an HZ-graph with…
Let f(k,r) be minimal such that if A_1,A_2,… is a family of sets, all of size k, such that for every collection of r of the A_is there is some pair x,y which intersects all of the A_j, then there is some set of size f(k,r) which intersects…
Let X_n be the unitary Cayley graph considered in the paper, and let m(r) denote the maximum length of an induced cycle in X_n when the underlying modulus has r distinct prime factors. Longest induced cycle conjecture. m(r)=2^r+2. The…
Let S be the set of square-free integers in [2, n] and G = PR[S] the graph on S in which two integers are adjacent when they are not coprime. From the cases n ≤ 100 and about twenty further values n ≤ 200, Graffiti conjectured that the…
Conjecture If G is a simple loopless triangulation of an orientable surface, then the dual of G is 3-edge-colorable.
Let k≥ 2, let n≥ k+1, and define t_k(n)=(k-1)(n-k+2)+binomk-22. A graph has minimum degree k if every vertex has at least k neighbors. Erdős's conjecture. For every k≥ 2 there exists an ε_k>0 such that every graph on n≥ k+1 vertices and…
Given a digraph D=(V+s,A) which is k-arc-connected in V, what is the maximum number of (disjoint) pairs of arcs, consisting of entering and leaving arcs at s, whose (simultaneous) splitting off does not destroy the k-arc-connectivity of D…
Use number theory to prove non-malleability properties for real-world RSA key-generation algorithms.
Identify polytopes with extremal h^*-vectors. That is, for a family of polytopes P and index j, find P∈ P that minimize or maximize h_j^*. Potential families of interest include symmetric edge polytopes for a fixed degree sequence and…
Prove an analogous small-polynomial-factor worst-case hardness result for SVP and SIVP on ideal lattices.
Given a permutation σ, what is the maximum number of copies of σ that a permutation on n symbols may contain?
Let Q_r be the r-dimensional hypercube, let α_bal(Q_r) denote the maximum total size of a balanced bipartite biindependent pair in Q_r, and let a(r) be the quantity defined in the preceding construction. Equality conjecture. Equality…