Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let G be a graph, and consider the Cartesian square G× G. An ordering of the vertices is optimal for the edge-isoperimetric problem (EIP) when it minimizes the number of boundary edges among vertex sets of each prescribed size. The…
Conjecture 6.17. The following were all presented by Seymour, with no other attributions given: For the following questions, matrices are assumed to be n × n 0-1 matrices such that aij = 1 implies aji 6 = 1, and all diagonal elements equal…
Let A⊂ G, and suppose E(A)≥ |A|^3/K. Then there is a set A'⊂ A so that |A'|≥ frac|A|K^100, |A'+A'|≤ K^100|A'|, E(A')/|A'|^3≥ E(A)/|A|^3 Can we moreover obtain the following? E(A')/|A'|^3≥ E(A)/|A|^3 (|A|/|A'|)^1/100
Find all graphs where all minimal zero forcing sets are also minimum zero forcing sets. (Greedoids?)
Quantify elliptic curves over finite fields whose group order has a large prime divisor.
Let k, r, and n be positive integers with n≥ rk and r≥2. An r-stable k-element subset of 1,…,n is one in which any two elements have cyclic distance at least r. The hypergraph KG^r(k,n)_r-stab is the subhypergraph of the r-uniform Kneser…
Let G be a graph on n vertices with minimum degree at least 2. The game domination number γ_g(G) is the number of moves in the domination game when Dominator starts and both players play optimally. Bujtás–Iršič–Klavžar's additive…
Let bar K_k be the class of all graphs that are not k-colourable. A class of graphs is multiplicative if it is closed under categorical products. Hedetniemi's multiplicativity conjecture. For every positive integer k, the class bar K_k is…
Let G be a connected graph and let e∈ E(G). Write G/e for the graph obtained by contracting e, and let μ denote mean subtree order. Connected-graph contraction conjecture. Contracting any edge should reduce the mean subtree order by at…
Let y=(y_1,y_2,y_3,y_4)∈N^4. A car-length vector is minimally invariant when it has the minimal invariance property defined in the paper. Four-car minimal-invariance conjecture. Then, y is minimally invariant if and only if (y_1 < y_2) ∧…
Consider the question of bounding the diameter of any Cayley graph Γ(G, A) of a finite, simple, non-abelian group G. How can Symn and Altn serve as a model for SLn ? What ideas from the proof may carry over to linear algebraic groups? What…
Let P_m be the path graph on m vertices and C_n the cycle graph on n vertices. Define f_n(t)=∑_m=0^∞ Z(P_m× C_n)t^m, where Z(G)=1-χ(Ind(G)) is the Witten index associated with the independence complex of G. Write each rational function…
For an n-vertex graph G, let X_G,k be the number of edges induced by a uniformly random k-vertex subset of G. Define I(n,k,ℓ)=maxPr(X_G,k=ℓ):|V(G)|=n and ind(k,ℓ)=lim_n→∞I(n,k,ℓ). Alon–Hefetz–Krivelevich–Tyomkyn's superlinear sparsity…
Let G be a connected graph, let e join two distinct vertices of G, and let G+e be the graph obtained by adding that edge. Write μ(G) for the subtree density of G. Density monotonicity conjecture. Then μ(G)<μ(G+e). The paper notes that…
Let G be a finite graph. Let bfA_RW(G) denote the evolution algebra associated with the random walk on G, and let bfA(G) denote the evolution algebra associated with G. Graph evolution-algebra isomorphism conjecture. A_RW(G)≅ A(G) if and…
Let G be a finite simple graph, with n(G) denoting its number of vertices and J_G its binomial edge ideal in S=K[x_i,y_i:i∈ V(G)]. Matsuda–Murai's conjecture. reg(S/J_G)=n(G)-1 if and only if G is a path graph on n(G) vertices. The claim…
What is the exact value of R(5,5), the smallest number n such that any 2-coloring of the edges of K_n contains a monochromatic K_5?
Call a graph G Ramsey size linear if R(G,H)=O(m) for every graph H with m edges and no isolated vertices. Are there infinitely many graphs that are not Ramsey size linear although every proper subgraph is?
What about variations of throttling, like the product of |B| and pt(G,B)? Note that ℓ-round power domination seems like it is similar to throttling.
Linal/Luria: A d-dimensional permutation of order n is an n-by-n-by-...-by-n (d+1)-dimensional array of zeroes and ones, with the property that every row, column, etc., has exactly one 1 in it. (More precisely, if the array entries are…