Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Local conditions for distinct distances Andrew Suk Question: (Erd\H{o}s 1986) What is the least possible number of distinct distances among n points in the plane if every 5 of them span at least 9 distinct distances? Conjecture: Ω(n^2)…
If an infinite graph is C-roughly transitive for some finite C, must it be roughly isometric to a homogeneous metric space? Equivalently, does there exist an infinite roughly transitive graph that is not roughly isometric to any space with…
Let G be a bridgeless cubic graph, and let a bipartite core mean a core whose underlying graph is bipartite. Bipartite core conjecture. Every bridgeless cubic graph has a bipartite core. The paper proves that this conjecture is equivalent…
: Given two permutations σ and τ, what is the expected number of copies of σ in a permutation chosen uniformly at random from those permutations on n symbols which avoid τ? Newsflash! Miklós Bóna has a nice paper addressing this.
Conjecture: (Burr--Erd\H{o}s) r(G,G) ≤ c(d) n if G is an n-vertex d-degenerate graph. Known: (Kostochka--Sudakov) r(G,G) ≤ n^1+o_d(1). If G is a 3-uniform d-degenerate hypergraph, the statement can be false. There is a 1-degenerate…
Let Γ be a connected non-bipartite graph, let R be the polynomial ring associated to its vertices, and let I be the edge ideal of Γ. Depth-drop conjecture. If depth R/I^t = 1, then depth R/I^t+3 = 0. The preceding theorem proves a related…
Let G∈C be a graph, and let rm dom_t(G) and rm DOM_t(G) denote its lower and upper orientable total domination numbers. For an orientation f of G, write G_f for the resulting oriented graph and γ_t(G_f) for its total domination number.…
For every rational α∈[1,2), there exists a finite bipartite graph G such that ex(n;G)=Θ(n^α). Equivalently, every rational exponent between 1 and 2 occurs as the order of growth of the Turán number of a single bipartite graph.
Let D=(V(D),E(D)) be a vertex-weighted oriented graph, let G be its underlying graph, and let S=K[x_1,…,x_n] be the polynomial ring on the vertices over a field K. Write I(D) for the vertex-weighted edge ideal of D and I(G) for the usual…
Determine whether the lattice dimension in the stated small-root constructions can be reduced.
(33) Lionel Levine: "What is the infinite volume limit of Andrea's prop-agator model [12] with a finite density of propagators?"
For which graphs H does there exist \varepsilon>0 such that every n-vertex \varepsilon-sparse H-free graph G with n>1 contains sets A,B satisfying one of: (a) |A|,|B|\geq\varepsilonn; (b) |A|\geq\varepsilonn and |B|\geqn^{\varepsilon}; or…
Let t:=n(n+1) and define Q_j(n):=∏_q=1^j-1(jn+q). Polynomiality conjecture. For the indicated integers k and j, S_k,j(n) is expressed as a polynomial in Q_j(n)Q[t]. This claim is suggested by the explicit formulas computed in the paper,…
Let N be a natural number greater than 2, let d be a natural number strictly less than N/2-1, and let n≥ N be another natural number. For the simplex S^N(n) considered in the paper, compare l-element subsets whose coordinate values in a…
Let G be a composite graph with skeleton widehat G. A permitted motif is a motif that supports a fixed point of the associated competitive threshold-linear network. Assume that widehat G is a permitted motif. Composite-graph permitted…
Given k disjoint matchings in a bipartite graph, a rainbow matching is a matching that contains one edge from each of them. Is it true that any family of k disjoint matchings of size k+1 has a rainbow matching?
Question Is every proper vertex-minor closed class of graphs chi-bounded?
Let M=(V,E∪ A) be a mixed graph, where A is the set of directed arcs and E the set of undirected edges. For U⊂ V, a pseudo dicut is the edge set δ_E(U) such that no directed arc enters U. An orientation E^+ of E replaces every undirected…
An oriented k-cycle double-cover (or k-OCDC) of a graph is a multiset of k oriented cycles in which every edge occurs in each orientation in exactly one cycle. Archdeacon's conjecture. Every bridgeless graph has a 5-OCDC. The conjecture is…
Conjecture If T is a tournament of order n, then it contains ⌈ n(n-1)/6 - n/3⌉ arc-disjoint transitive subtournaments of order 3.