Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
A variant of the Erdős–Faber–Lovász conjecture (Tom Kelly) The Erdős–Faber–Lovász conjecture is the following: If G1 , . . . , Gn are complete graphs, S each on at most n vertices, such that every pair shares at most one vertex, n then…
In the biased positional games on the edges of K_n, determine the unresolved threshold questions recorded in the report: close the remaining gap for the Breaker bias at which Maker can build a Hamilton cycle; determine the threshold bias…
Given a crossing negamodular function R:2^V→ Z such that R(X)≠ 1 for every X⊆ V and a hypergraph G_0=(V,E_0), find a hypergraph G=(V,E) of minimum total size such that d_G(X)≥ R(X)-d_G_0(X) holds for every X⊆ V and the rank of G does not…
Let G be an infinite graph with vertex set E, and let deg(x) denote the degree of x. Ulam reconstruction conjecture. If ∀ x∈ E, deg(x)<∞, then G is Ulam-reconstructible. The source gives this as a further sufficient condition for…
Let g_k(n) be the largest number of edges in an n-vertex graph having no cycle with k chords incident to a single vertex of the cycle. Is g_k(n)=(k+1)n-(k+1)^2 for all sufficiently large n?
A graph's metamour period is the least positive integer k for which its iterated metamour graph returns to the original graph, under the metamour operation used in the paper. Let k range over the positive odd integers. Finiteness…
Let G) be an infinite graph with vertex set E. For x∈ E, write G|E∖x for the subgraph induced by deleting x, and write ~ for graph isomorphism. Ulam reconstruction conjecture. If ∀ x ∈ E, G|E∖xnsim G|E, then G is Ulam-reconstructible. This…
Let k_1,k_2,k_3 be odd natural numbers. For each i=1,2,3, let y_i,1,…,y_i,k_i be distinct real numbers, and set y_i,0=y_i,k_i+1=-∞. For two finite pairs of real numbers, call their sums non-crossing when the two sums of one choice and the…
Let G be a directed graph and let E be a subset of its edge set E(G). Write H_0^Q(G) for the degree-zero Khovanov-Rozansky homology over Q and H_0(G) for the corresponding homology over Z. For a module over a ring, write K-dim for its…
It remains an interesting open problem to identify the strongly prime smooth graphs. The report passage is retained verbatim as the relevant context for this extracted problem.
Let r=2^t p_1^α_1… p_k^α_k, where t∈0,1 and the p_i are distinct odd primes. Let overline m,overline m'∈( Z_r)^n be parameter vectors, and let B_(r;overline m) denote the associated matrices. For each i and each t with 1≤ i≤ k and 1≤ t≤…
Does every graph on n vertices with >ex(n;C_4) edges contain ≫ n^1/2 many copies of C_4?
Let a Costas sequence be a sequence whose difference triangle has no repeated entry in any row. A sequence is singly periodical when every circular shift of its terms is also a Costas sequence. A Welch sequence is one obtained from the…
Erdős, Hajnal: Suppose G has n vertices and no induced copy of H. Is there an ľ > 0, depending only on H, so that the homogeneous number of G (i.e., the size of the largest clique or independent set) is at least n^(ľ )? This is open even…
Question: (Fox) Is R_f^(2)(3,n) = n^1 + o(1)?
Let n,r∈ N with r dividing n. Let G be a graph on n vertices with degree sequence d_1≤…≤ d_n. Balogh, Kostochka and Treglown's conjecture. If d_i≥ (r-2)n/r+i for all i<n/r, and d_n/r+1≥ (r-1)n/r, then G contains a perfect K_r-packing. A…
Let J_±(n,4,1) be the Johnson-type graph with parameters n, 4, and 1, and let α[G] denote the independence number of a graph G. Independence number conjecture. Let n>n_0 be an even number. Then α[J_±(n,4,1)]=2n(n-2). This is posed as an…
There exists a positive number C which depends only on L and H with the following property. Let m, x and y be rational integers with m≥ 2 and |y|>1 satisfying y^m=f(x). Then either m≤ C, or else there is a proper subsum in…
Let G be a bridgeless cubic graph. Mazzuoccolo's conjecture. There exist two perfect matchings M_1,M_2 such that the graph obtained by deleting their union, G∖(M_1∪ M_2), is bipartite. The source presents this as a weakening of the…
For a graph Γ and a braid index n≥ 2, let B_nΓ denote its graph braid group. An n-nucleus is a minimal graph whose n-braid group is not a right-angled Artin group, while the n-braid group of every graph contained in it is a right-angled…