Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Determine whether (4,C)-SymRelCol has a sudden hardness jump, and determine the order of g(6,n), the least g such that every n-vertex graph of maximum degree 6 has a two-coloring with every monochromatic component of order at most g.
Let n and i be parameters for the interval-vector polytope P_n(I_1,n-i), where I_1,n-i denotes the corresponding family of intervals and vol denotes volume. Volume conjecture. vol(P_n(I_1,n-i))=2^i(n-(i+1)). This formula was observed from…
For integers k≤ n, let U_k(n) be the minimum length of a sequence of independent lazy transpositions whose product maps the elements 1,…,k uniformly to the n(n-1)…(n-k+1) possible ordered k-tuples; such a sequence is called a…
Let h(n) be minimal such that every graph on n vertices where every set of 7 vertices contains a triangle (a copy of K_3) must contain a clique on at least h(n) vertices. Estimate h(n) - in particular, do there exist constants c_1,c_2>0…
Frankl and F"uredi~\cite{frankl+furedi:89} determined π(B_k,2) for k=5,6; in both cases the lower bounds comes by blowing up a small design. The following question is still open (see Frankl and…
For fixed n, determine which pairs of k-cycle networks are distinguishable under the CFN, K2P, and K3P group-based models, and extend the analysis from k-cycle networks to level-1 networks.
Let (ε_n)_n≥ 0 be a sequence of elements in 0,1. Assume that the real number ∑_n≥ 0ε_n 3^-n is irrational, then it is transcendental.
Let C_n be the n-th order standard circulant matrix, and let m_1(C_n) denote its first appearance degree. Let fix be the fixed-point function associated with the identity matrix of order n. Standard-circulant first appearance degree…
Let G be a 2-connected graph with a longest cycle L. For an H-bridge B, let its length λ(B) be the maximum number of edges in a tree within B whose leaves are exactly the attachments of B. Let B_1, B_2, …, B_k be L-bridges that are…
Construct pairing-friendly hyperelliptic curves suitable for cryptography.
Let (ε_n)_n≥ 0 be a sequence of elements in 0,1. Assume that the real number ∑_n≥ 0ε_n 3^-n is irrational, then it is transcendental.
Let ζ_p:Z_p→Q_p be the p-adic zeta function. Is ζ_p(k)≠0 for every even integer k?
Can the function f on SL(2,Z) be extended naturally to C/SL(2,Z)? Can analogous series be constructed for other lattices or tessellations of the plane?
Let J(2k,k-1) be the Johnson graph whose vertices are the (k-1)-subsets of a 2k-element set, and let JK(2k,k-1) be the graph used in the construction above. Order the vertices of J(2k,k-1) lexicographically and apply the greedy algorithm…
For L,C∈ N, let G and H be graphs and let φ be an (L,C)-quasi-isometry from G to H. An edge-weighting function wcolon E(H)→N gives H the weighted-graph metric, denoted (H,w). Nguyen–Scott–Seymour conjecture. For all L,C∈N, there exists…
conjecture for k “ 2 was proved by Allen [1] and k “ 3 by Ilinca and Kahn [6]. Bollobás and Brightwell [2] conjectured that if k “ kpnq is allowed to increase with n, as long as k ď p1{2 ´ cqn for some constant c ą 0, the number of k-SAT…
Let G be a connected graph that is not a cycle. Write O(G)=V(G)∪ E(G), let dim_m(G) denote the minimum cardinality of a mixed metric generator of G, let ℓ(G) be the number of leaves of G, and let c(G)=|E(G)|-|V(G)|+1 be its cyclomatic…
Let G be a graph with bounded degrees, let P be the transition kernel of the underlying random walk, and for each induced connected subgraph F⊂ G with finite boundary let P_F be the corresponding restricted transition kernel. Define…
Let k be a positive integer. Let G_1,G_2,… be graphs that do not contain a Robertson chain of length at least k as a topological minor. Let Q be a set equipped with a well-quasi-ordering ≤_Q, and for each positive integer i, let…
Problem What is the largest connected planar graph of minimum degree 3 which has everywhere positive combinatorial curvature, but is not a prism or antiprism?