Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Chung/: A de Bruijn covering code of radius R is a binary string so that the set of words appearing as n consecutive symbols (with wrap-around) is a covering code of radius R. What is the smallest de Bruijn covering code with parameters R…
Fix an integer k≥ 3. Let G=(V_1,…,V_k;E) be a balanced k-partite graph on kn vertices, and let hatδ_k(G)=min_1≤ i<j≤ kδ(G[V_i,V_j]) be its minimum bipartite degree. Asymptotic multipartite Hajnal–Szemerédi conjecture. If hatδ_k(G)≥…
Let Γ be a zillion graph with ω odd cycles and μ even cycles, and let |E(Γ)| denote its number of edges. Edge-size conjecture. There exist a quadratic polynomial f∈Z[x] and a linear polynomial g∈Z[x] such that Γ is graceful whenever…
Entropy of sum of random variables. Let G be a torsion free abelian group. Suppose X is a random variable on G and S_n is sum of n many i.i.d copies of X. Let H(·) be the discrete entropy function. We have the following theorem by T. Tao:…
Let G be a non-separable graph of even order, meaning that no subset W of its vertices with 2≤ |W|≤ |V(G)|-2 becomes disconnected from its complement after any switching. A subgraph obtained by removing one vertex is an induced subgraph,…
Let α_1≥α_2≥…≥α_n≥0 be real numbers with ∑_iα_i<s, and write α=(α_1,…,α_n). Define F(α):=F∈2^[n]:∑_i∈ Fα_i≥1. Then ν( F(α))<s. Halfspace meta-conjecture. For any n,s, the maximum defining e(n,s) is attained by F(α) for a suitable α∈ R^n.…
For θ∈(0,π), define V_θ=re^it ; r>0, |t|>θ. Compute L(V_θ) in terms of θ.
A graph is vertex transitive if, for every pair of vertices v,w, there is a graph automorphism mapping v to w. A graph is Hamiltonian if it admits a Hamiltonian circuit, namely a simple circuit containing every vertex of the graph.…
Let T be a tree of order n≥ 3. A set S⊆ V(T) is a dissociation set if every vertex of the induced subgraph T[S] has degree at most 1, and it is maximal if it is inclusion-maximal among dissociation sets. Let Φ(T) denote the number of…
Let G be a bipartite graph and H a non-bipartite graph, both on n vertices. A common card is an unlabeled vertex-deleted subgraph occurring in the decks of both graphs. Bipartiteness conjecture. For n large enough, the number of common…
If A ⊂ Z/pZ is random with |A| = √p, can we almost surely cover Z/pZ with 100√p translates of A?
Does every extendable hereditary graph property P have a VDF tester with the same, or asymptotically comparable, sample complexity as in the standard dense graph model?
Let K and L be finite free Z/2-simplicial complexes, with diagonal action on their Cartesian product, and let ind X denote the least k for which there is a Z/2-equivariant map from X to E_k( Z/2). Wrochna's topological Hedetniemi…
Let G be a full-rank typical graph. A G-partial matrix is a partial symmetric matrix whose specified off-diagonal entries correspond to the edges of G; it is minimally completable to full rank if it has a completion of full rank but no…
How many facets do symmetric edge polytopes have?
For every connected simple finite graph F with |V(F)|≥ 3, there exist infinitely many simple finite graphs G such that, for every pair of distinct vertices u,v∈ V(G), the numbers of copies of F in G containing u and containing v are…
Let m be the number of marked vertices in a graph. A quadratic spanning forest identity of the indicated type has coefficients as free variables, where the left-hand side consists of a spanning tree and a spanning forest with each marked…
(12) Persi Diaconis: "Is there an abelian growth model for non-overlapping discs growing in the plane?" (a) James Propp: "There is such an abelian model in the case of non-nesting discs; firing means if you have a disc that is totally…
Let Q_n be the Queen graph on an n× n chessboard: its vertices are the board squares, and two distinct vertices are adjacent if they lie in a common row, column, or diagonal. A set S⊆ V(Q_n) is odd independent if it is independent and…
The γ–θ conjecture asserts that for every finite graph G, γ(G)=γ^∞(G) Longrightarrow γ(G)=θ(G), where γ is the domination number, γ^∞ is the eternal domination number in the one-guard-moves model, and θ is the vertex clique-cover number.…