Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let G be a connected graph with sink vertex v_n, let R=k[x_1,…,x_n-1], and let I be the G-parking function ideal generated by the monomials associated to connected cuts of G. Write β_i(R/I) for its coarsely graded Betti numbers, and let…
Let alpha≥2 and n≥4 be integers satisfying 2alpha≤ n≤3alpha-2. For a graph G, let alpha(G) denote its independence number, let |V(G)| denote its order, and write I(G;x)=∑_k s_kx^k for its independence polynomial. Overhauled Roller-Coaster…
Let G be a vertex-transitive partial cube with girth 6. Marc's conjecture. Doubled Odd graphs are the only vertex-transitive partial cubes with girth 6. This conjecture proposes that the known Doubled Odd graphs exhaust the…
Let G be a finite simple graph with n vertices. Suppose that every vertex subset V' satisfying 2|V'|+1≥ n has an induced subgraph G[V'] with more than n^2/50 edges. Must G contain a triangle?
Let G be an elementary polyomino, meaning a polyomino whose associated plane bipartite graph is elementary. The maximum forcing number conjecture. The maximum forcing number of G can be computed in polynomial time. This conjecture extends…
(25) Andrea Sportiello: "What is the higher-dimensional version of the explorer model [16]? Is this model more amenable to generalization the abelian sandpile model?"
Let G be an infinite transitive connected graph, and let G_n_n=1^∞ be a sequence of infinite transitive connected graphs that converges locally to G. For each graph, let μ(G) denote its connective constant, defined as the exponential…
Open growth questions include: for a graph, what lower bounds can be given for the difference between its two largest adjacency eigenvalues; for A in an abelian group, how large is A+A compared with A; and for A in a general group, how…
In every two-coloring of the subsets of an n-element set, how large a monochromatic family must exist that is closed under both unions and intersections? How large if only closure under unions is required? For the latter quantity F(n), is…
For every integer n≥ 1 and every n-vertex graph G with independence number α(G)=2, the graph G contains K_⌈ n/2⌉ as an odd minor.
Let G be either Q_3 or K_3,3 or H_5 (the last formed by adding two vertex-disjoint chords to C_5). Is it true that, if H has m edges and no isolated vertices, then R(G,H)≪ m?
Equi-isoclinic subspaces Given k-dimensional linear subspaces U,V≤ R^d, we say that U,V are equi-isoclinic with angle α if every unit vector in U projects down onto V a vector of length α. Let N_α^k(d) be the maximum number of…
What is the maximum number ex(H, G, n) of H-subgraphs contained in an n-vertex graph in G? Homomorphism counts in robustly sparse graphs Chun-Hung Liu
Let N≥ 1,n≥ 2 be integers, λ a partition with height(λ)≤ n, and L an n× N matrix with nonnegative integer entries. Let F( L,λ) denote the fermionic representation defined in the paper and K( L,λ) the corresponding generalized Kostka…
For 0≤t<⌊n/2⌋, must every n-vertex graph with ⌊n^2/4⌋+t edges contain at least t⌊n/2⌋ triangles?
Let a Goldbach factorization graph be a graph associated with an even integer and let an exceptional autonomous component (EAC) denote the special source strongly connected component studied in the paper. The conjecture on exactly six…
Let K_n be the complete graph on n vertices, and let T_n denote the family of spanning trees on these vertices. In the Maker–Breaker game (E(K_n), T_n), Maker claims edges while Breaker claims the remaining edges; write Δ(T) for the…
Does there exist a group acting geometrically on a coarse Helly graph that is not Helly, and which Artin groups are coarse median?
Problem 1.17 (A. Granville). Given a set in a finite field, how to determine (in rea-sonable time) whether it is a sumset of yet another set?
Let G be a connected subcubic graph with n vertices and m edges. Subcubic bound conjecture. γ(G)≤ 4n-m/6 unless G is isomorphic to the complete graph K_4 or the complete bipartite graph K_3,3. This is proposed as a minor strengthening of…