Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Consider the convex hull of parking functions. Does this admit a unimodular triangulation? Furthermore, can the Ehrhart polynomial be obtained from this?
Let C_3 and C_4 denote cycle graphs of lengths three and four, respectively. Form a graph by gluing any number of copies of C_3 along single edges to a single copy of C_4, and assume that no pair of triangles is glued to opposite faces of…
Let G be a graph. Write 4H_d^normalfont Cube(G)4 for its discrete singular cubical homology group in dimension d. Eventual vanishing conjecture. For every graph G, there exists an integer N such that H_d^normalfont Cube(G)=(0) for all d≥…
Let G be a locally finite tree. A graph G is reconstructible if every graph hypomorphic to G is isomorphic to G, where hypomorphism means that there is a bijection between the vertex sets whose corresponding vertex-deleted induced…
Let B=0,1^n, and let μ be the uniform measure on B^t. An intersecting family is a set W⊆0,1^n such that for every x,y∈ W there is a coordinate i with x_i=y_i=1. Let p_intersecting(t,n) be the maximum of μ(W) over t-tuples of intersecting…
In a graph G=(V,E) with a root node r, two spanning trees T_1 and T_2 are called r-independent if for any node x in V-r, the unique paths between r and x in T_1 and T_2 are internally node disjoint. Is it true that if G is k-connected then…
For which classes of digraphs can we explicitly give a linear description of the convex hull of kernels?
Define f:N→N by f(n)=n+rev(n), where rev reverses the decimal digits. Are there infinitely many n for which no iterate f^k(n), k>0, is a palindrome? Is the least such n equal to 196?
Let G be a connected graph, and let P_t denote the path on t vertices. A graph is P_t-free if it has no induced subgraph isomorphic to P_t, and c(G) denotes its cop number. Sivaraman–Testa conjecture. For t≥ 5, if G is P_t-free, then c(G)≤…
For a lattice polytope P, let P^n denote the Cartesian product of P with itself n times (n∈ mathbbN). Investigate what happens to the h^*-polynomial of P^n. Does it eventually become real-rooted?
Let h(n) be maximal such that if A⊆ Z with lvert Arvert=n then there is B⊆ A with lvert Brvert ≥ h(n) such that if a_1+…+a_r=b_1+…+b_s with a_i,b_i∈ B then r=s. Estimate h(n).
Conjecture 6.5. 3. Form a digraph from the matrices A1,..., A t by putting t + 1 copies of the vertex set V in a row, connecting copy k of v to copy k + 1 of v with a horizontal edge for all vertices v and all k, and then from copy k to…
Can the classification of irreducible complex reflection groups give some ideas towards a possible classification of nontrivial geproci sets? It also seems natural to ask to what extent the combinatorics (specifically, the underlying matroid)…
Let h_t(Δ) be the smallest integer such that every graph with h_t(Δ) edges and maximum degree at most Δ contains two edges whose distance is at least t; equivalently, h_t(Δ)-1 is the largest number of edges in a graph of maximum degree at…
A graph is twin-free if every two distinct vertices have distinct open and closed neighborhoods. For a graph G, a set D of vertices locates a vertex v∉ D if the neighborhood of v within D is unique among all vertices in V(G)∖ D; a…
A cycle double cover of a graph is a list of cycles such that every edge belongs to exactly two of them. A graph is simple if it has no loops or parallel edges, and 2-edge-connected if deleting any one edge leaves it connected. Bondy's…
Let genfrac0ptnk denote the Stirling subset number, and define the reversed Stirling subset triangle by genfrac0ptnk^rm rev=genfrac0ptnn-k. Write S^rm rev=(genfrac0ptnk^rm rev)_n,k≥ 0. Total-positivity conjecture. The reversed Stirling…
If G is a graph on n vertices without a K_4 then how large a triangle-free induced subgraph must G contain?
Question Is the binary affine cube AG(3,2) the only 3-connected matroid for which equality holds in the bound E(M) ≤ c(M) c(M^*) / 2wherec(M)is the circumference (i.e. largest circuit size) ofM?
For every fixed k-graph F, does there exist a constant c_{F} depending only on F such that every F-free k-uniform hypergraph with maximum degree \Delta has chromatic number at most c_{F}(\Delta/\log\Delta)^{1/(k-1)}?