Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
A hypergraph H=(V,E) has the Kőnig-property if there is a set D⊆ E of pairwise disjoint hyperedges such that there is a vertex cover consisting of one vertex from each hyperedge in D. (Using this terminology, Kőnig's theorem says that…
For the planar wheel graph with n vertices and 2n-2 edges, the stated self-stress \omega and edge function f_{ij} satisfy \sum_{ij\in E(G)}\omega_{ij}f_{ij}=1. Are there other graphs with n vertices and 2n-2 edges admitting such a…
For every constant C>0, do there exist constants α,β>0 such that every n-vertex graph with no clique or independent set larger than Clog_2 n contains an induced subgraph on at least α n vertices in which at least β√ n vertices have…
For any 4× 4 skew-symmetric matrix M with entries in L and rank ≤ 2, either the rows of M are linearly dependent over Q, or the column space of M contains a nonzero element of Q^4.
Let R_n be the tree obtained, for n≥ 4, by subdividing once an edge of the star S_n-1, and let av_1(T) denote the average size of the 1-nearly independent vertex sets of a tree T. Extremal tree conjecture. The tree R_n reaches the maximum…
Let W_ C^d(0_nω) be the indicated local Weyl module for sl_2, and let W_ C^d(0_nω)^n-2i denote its weight space of weight n-2i. Higher Narayana number conjecture. For i=0,…,n, one has dim W_…
Let M be a matroid, and let A and B be two bases of M. A subset X of A and a subset Y of B, both of size k, form a serial symmetric exchange with respect to A and B if there is an ordering x_1,…,x_k of X and an ordering y_1,…,y_k of Y such…
Let k be a positive integer, let cal G_k be the graph class defined in the paper, and for a graph H let ν_k(H) denote the maximum number of pairwise vertex-disjoint k-paths and let τ_k(H) denote the minimum size of a vertex set meeting…
Let Δ be a connected (d-1)-dimensional homology manifold with nonempty orientable boundary, where d≥ 4. For each face F of Δ, let lk_Δ(F) denote its link. A simplicial complex is stacked if it is obtained from a simplex or a simplicial…
For a plane graph G, let g(G) denote the length of the shortest face in G. For a (not necessarily proper) k-coloring of V(G) we say that a face is polychromatic if all k colors appear on its vertices. A k-coloring of V(G) is called…
For an elliptic curve E/Q, let N_p be its number of solutions modulo p plus one and put f(X)=∑_p≤ Xlog(N_p/p). Is f(X) bounded if and only if E(Q) is finite?
Let n be a positive even integer and let σ be a pairing of 1,…,n. Theorem stated in the source says that Z_σ/Z_1|2|…|n is a polynomial of degree n/2 in the quantities L_i,j:1≤ i<j≤ n and L'_i,j:1≤ i<j≤ n-1. Integrality conjecture. Every…
Let T(n,r) be the largest size of a family of subsets of an n-element set in which no two members intersect in exactly r elements. Estimate T(n,r) for r≥2. In particular, for every ε>0, is there δ>0 such that T(n,r)<(2-δ)^n whenever ε…
Let G be a simple graph of order n. A graph is 3_t-critical if its total domination number is 3 and adding an edge between any nonadjacent vertices lowers its total domination number. Suppose in addition that G has diameter 2, and let m…
Let X be a finite connected rack. Its profile is the common cycle type λ=(λ_0^a_0,λ_1^a_1,…,λ_t^a_t), where λ_0<λ_1<…<λ_t are the cycle lengths of the elements of the image of the rack morphism Φcolon X→Aut(X), with multiplicities…
Must every word of length 2^k-1 over an alphabet of k symbols contain two consecutive blocks in which each symbol occurs the same number of times?
Let G and H be undirected graphs. Write γ(G) for the domination number of a graph, and let i(G) denote its independent domination number, the smallest size of an independent dominating set of G. The Cartesian product Gsquare H has vertex…
Let n be an integer, and let a circulant graph mean a graph whose vertices are arranged cyclically with adjacency determined by a fixed set of cyclic differences. The monophonic position number is denoted by a, and the diameter by D.…
In the preceding setup, additionally require every vertex of B to have at least x|A| neighbors in A and every vertex of C at least y|B| neighbors in B, and define \psi(x,y) as the corresponding maximum two-edge-path density. Is…
For graphs H_1 and H_2, let r(H_1,H_2) be the least integer n such that every red-blue edge-coloring of K_n contains a red copy of H_1 or a blue copy of H_2. The arboricity of a graph is the minimum number of forests into which its edge…