Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
What is the complexity of the union of ``fat'' objects in R^3?
Conjecture. Namely, we will take X The report passage is retained verbatim as the relevant context for this extracted problem.
Let P ⊆ G be additive and hereditary. A graph G is vertex-γ_P-critical if its vertex domination number with respect to P has the criticality property used in the paper, and let b_P^+(G) denote its upper bondage number and Δ(G) its maximum…
Let G be a graph of order n with diameter at least three and having a vertex cut of size one. For graphs H_1,…,H_n, let G[H_1,…,H_n] be the corresponding blow-up of G. Vertex-cut obstruction. There are no graphs H_1,…,H_n such that…
A proposed definition of Ramanujan for non-regular graphs is that the non-backtracking matrix B has spectrum satisfying Sp(B) ⊆ ρ e^i θ, θ ∈ [0,2π] ∪ B(0,√ρ). For this definition, prove the result analagous to Alon-Boppana. Namely, for ρ…
A de Bruijn sequence of order n is a cyclic binary sequence in which every binary word of length n occurs exactly once; the Pref-opposite algorithm is the construction specified in the source. The discrepancy of a binary sequence is the…
Given a set S, what is the smallest zero forcing set that contains S (restrained zero forcing). Similarly, given a set S what is the smallest zero forcing set that is contained in S?
At least three of the four numbers π, Γ(1/5), Γ(2/5), e^π√ 5 are algebraically independent over Q.
A quasi-kernel of a digraph D is an independent vertex set K sucht that every vertex is reachable from K in D by a path of length at most two. A quasi-sink of D is a quasi-kernel of the digraph that we obtain by changing the direction of…
Let n≥ 4, and let G_1,…,G_k be a collection of n-edged graphs for some k≥ 1. Write coprod_i=1^kED(G_i) for the disjoint union of their edge decks. Generalized edge reconstruction conjecture. For every k≥ 1, the collection G_1,…,G_k is…
Let G be a graph, let V(G) be its vertex set, let deg_G(v) denote the degree of a vertex v, and let x∈F_2^V(G) be a configuration. Let ML_G(x) and ML^*_G(x) denote the minimum light numbers of x for the sigma-game and lit-only sigma-game…
Conjectures: every Latin square of order n has a partial transversal of size n-1 and, if n is odd, a transversal; and every properly n-edge-colored bipartite multigraph with at least n+1 edges of each color has a rainbow matching using…
Determine the exact proper hat-guessing number of the complete graph on seven vertices with one edge removed. The general bounds leave HG_P(K_7-e)∈11,12.
Let G=(V,E) be a graph, let S⊆binomV2, and let widehatG be obtained from G by replacing an edge by a connected graph. A facet-replacement conjecture asserts that any facet-defining inequality of textscMultC(widehatG,S) is either an edge…
Every simple graph G on n vertices with more than n^2/4 edges contains an edge that lies in at least n/6 triangles.
Let G be a graph, and let χ(G) denote its chromatic number. For n∈N, write Sh_n(ω) for the corresponding shift graph on ω. Taylor's conjecture. If χ(G)>ℵ_0, then there exists an n∈N such that G contains all finite subgraphs of Sh_n(ω). The…
Graham: Suppose that G is a tree. Denote by L(G) the line graph of G. Is the sequence |G|, |L(G)|, |L(L(G))|, |L(L(L(G)))| ... unique to G? That is, can a tree be reconstructed from the sequence of sizes of its iterated line graphs? See…
For k≥ 1, let the odd graph K(2k+1,k) be the Kneser graph whose vertices are the k-element subsets of [2k+1], with edges between disjoint sets. Odd graph Hamiltonicity conjecture. For any k≥ 1, except for k=2, the odd graph K(2k+1,k) has a…
Let n be an odd positive integer, and let ξ(n) denote the toroidal covering parameter. Multiplicative reduction conjecture. ξ(n)=minn/mξ(m): m divides n. This conjecture proposes an exact reduction of the odd case to divisors of n,…
Let M(n) denote the number of distinct multinomial coefficients arising from partitions of n. Asymptotic-growth conjecture. There exists a positive constant C such that lim_n→∞log M(n)/√ n=C. This conjecture concerns the order of magnitude…