Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let H) be a tree, and consider any path between leaf vertices. For a path of odd length 2n-1, suppose that the numbers of subtrees rooted at the successive branches satisfy C^H_1 ≥ D^H_1 ≥ C^H_2 ≥ … ≥ C^H_n ≥ D^H_n. For a path of even…
Let G be a K_4-free graph with chromatic number 4. Must G contain an odd cycle with at least two diagonals? More generally, is there some f(r)→ ∞ such that every graph with chromatic number 4, in which every subgraph on ≤ r vertices has…
Let 0<c<1 be a constant. For a graph G, let MIS(G) denote its family of maximal independent sets, and define the family of large maximal independent sets by MIS_large(G)=I∈MIS(G): |I|≥ cn. A transversal is a set of vertices meeting every…
For integers m≥ 4 and 0≤ i≤ m, define the Boros–Moll numbers by d_i(m)=2^-2m∑_k=i^m2^kbinom2m-2km-kbinomm+kkbinomki, and define u_i(m)=dfracd_i-1(m)d_i+1(m)d_i(m)^2. Chen and Gu conjectured that, for every m, the sequence u_i(m)_2≤ i≤ m-2…
Conjecture 6. 1 0. (Devos) Under the hypotheses of
Let p,q≥ 1 be fixed integers. We define H(n)=H(N;p,q) to be the largest m such that any graph on n vertices where every set of p vertices spans at least q edges must contain a complete graph on m vertices. Is c(p,q)=liminf log H(n)/log n a…
If G, H are graphs, a function f: E(G) → E(H) is called cycle-continuous if the pre-image of every element of the (binary) cycle space of H is a member of the cycle space of G. Problem Does there exist an infinite set of graphs G_1,G_2,……
Can the minimum size for sunflowers be bounded by an exponential (not super-exponential) function of k?
Let n runners with distinct constant speeds run around the unit circle, starting at a common time and place. Identify the unit circle with T=R/Z, and let lVert·rVert_T denote the distance to the nearest integer. Equivalently, let…
Let a graph be critical banned in dimension d when it is banned in dimension d but deleting any vertex lowers the required dimension. Two vertices are isomorphic when deleting either one produces a graph of smaller dimension and the two…
Let E_k(λ) be the Euclid polynomials. A polynomial p(λ)=∑_j=0^na_jλ^j is unimodal when its coefficient vector [a_0,a_1,…,a_n] consists of positive integers that first increases monotonically to a peak, possibly attained at two or more…
Let c_k,ℓ denote the asymptotic covering density parameter for ℓ-rooks in k dimensions, with positive integers k≥ ℓ≥ 2. Covering density conjecture. For positive integers k≥ ℓ≥ 2, c_k,ℓ=fracbinomk2binomℓ2. The conjecture is proposed as an…
Let G be an Eulerian graph, and let an ℓ-step self-avoiding Eulerian tour of G be one in which every segment of length at most ℓ is a path. Here, a segment of length ℓ is a walk e_1e_2… e_ℓ whose consecutive edges occur consecutively in…
For fixed 0 less than p less than 1, does a random graph G in G(n,p) satisfy f_min(G) at least a constant times n/log n with high probability; what is the maximum f_min(G) over n-vertex graphs; and is f_min(G)=o(n) for every G in G(n) or…
Let n be a positive integer, let x be a parameter, and let (α)_p denote the Pochhammer symbol, defined by (α)_p=α(α+1)…(α+p-1) for p≥1 and (α)_0=1. Parametric determinant conjecture. det_0≤ i,j≤…
Let G be a simple graph of order n. Select an orientable embedding of G uniformly at random, and let F denote its number of faces. Linear expected-face conjecture. The expected number of faces satisfies E[F]=O(n). Stahl proved the upper…
Let [n]=1,2,…,n, and call a graph on [n] a minimal kinematics graph when its edge set is inclusion-maximal among the graphs realizing minimal kinematics. Minimal kinematics edge-count conjecture. Every minimal kinematics graph on [n] has…
The anti-Ramsey number AR(n,G) is the maximum possible number of colours in which the edges of K_n can be coloured without creating a rainbow copy of G (i.e. one in which all edges have different colours). Let C_k be the cycle on k…
For a matching π, define G_π=A_π(-|π|); let A_n and A_n^V denote the enumerative quantities used in the source, and let ^n denote the empty matching with n nested arches. Sum-rule conjecture. For every positive integer n,…
Is G cocompactly cubulable? Is G necessarily residually finite? Can one remove the word “uniform” from this statement, i.e., instead just suppose that every point has a neighbourhood in which every triple has a unique median? Problem 10.…