Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Suppose that F_2^n is partitioned into sets A_1, …, A_K. Does 2A_i contain a coset of codimension O_K(1) for some i?
For a graph G, let χ(G) denote its chromatic number, i.e. the least number of colours in a proper vertex colouring of G. For graphs H and G, say that G is H-free if no induced subgraph of G is isomorphic to H; here an induced subgraph of G…
Problem 3.12 (J. Bourgain). Consider the Szemer´ edi-Trotter theorem in R3 with n2 lines, each containing n points from a given set S. Assume no n lines are coplanar. Find a lower bound for S (e.g. |S| ≥ n3−≤).
Let P_n and C_n denote, respectively, the path and cycle on n vertices, and let ρ_R(G) denote the replication number of a graph G. The cycle–path replication conjecture. For every n≥ 6, ρ_R(C_n)=ρ_R(P_n). The conjecture is motivated by…
: What are the Whitney numbers of the (lattice of contractions of the) n-cube? What if contractions equivalent under symmetries of the cube are identified? How many contractions are there up to isomorphism? See this.
Let T_n be an arbitrary tree on n vertices, let C_m be a cycle on m vertices, and let R(T_n,C_m) denote the Ramsey number of T_n versus C_m. Define f(m) to be the least function such that R(T_n,C_m)=2n-1 for every odd m≥ 3 whenever n≥…
Let G be a finite primitive permutation group on a set Ω, and let b be its base size. Define the generalised Saxl graph Σ_b(G) to have vertex set Ω, with distinct vertices x,y∈Ω adjacent if and only if x,y is contained in a base of G of…
(31) Dustin Cartwright: "What is the (tropical) Picard group (in the sense of [13]) of the product of graphs? I have a guess if one of the graphs is a tree."
Let A=a_1<a_2<…⊂ N be an infinite sum-free set - that is, there are no solutions to a=b_1+…+b_r with b_1<…<b_r<a∈ A. How small can a_n+1-a_n be? Is it possible that a_n+1-a_n<n?
One may also ask: Can one find Chern classes of associated bundles (in this more general setting where V is not of CohFT-type) and determine when the higher Chern classes are tautological? What are sufficient conditions ensuring the Chern…
For every undirected graph G, are the following equivalent: (1) the Colin de Verdière number μ(G) ≤ 5; (2) the even-mapping invariant σ(G) ≤ 5; and (3) the panelling G̃, obtained by attaching a disk to each circuit of G, embeds in R⁴?
Let T_1(k,c) be the triangular grid, with k and c as in the tail asymptotics conjecture. For indices satisfying the displayed ranges, define the edge-label ratios r_2,1(c,r,d)=⟨ r,d,2⟩_c/⟨ r,d,1⟩_c, r_3,1(c,r,d)=⟨ r,d,3⟩_c/⟨ r,d,1⟩_c, and…
Let B be a board for Snort, and let the degree of B denote its maximum vertex degree. The temperature of a Snort position on B measures the incentive to move. The degree bound conjecture for Snort on boards. The temperature of Snort on a…
Let P_n be the path graph on n vertices, and let C_n be the cycle graph on n vertices. The incompatibility robustness of a graph is denoted by η(·). Path-graph robustness conjecture. For all n≥ 1,…
Let T be a tree. For a vertex w and a neighbor x of w, let T^x denote the component containing x after deleting w, let μ(x) denote the number of isomorphism types among the branches rooted at x, and let a(T^x) denote the number of…
Let D be an interaction graph and let F[D,q] denote the finite dynamical systems over an alphabet of size q with interaction graph D. For j∈0,1,2, let d_j denote the proportion of elements of F[D,q] having exactly j fixed points, and let…
Let k≥ 3 and define F_k(n) to be the minimal r such that there is a graph G on n vertices with ⌊ n^2/4⌋+1 many edges such that the edges can be r-coloured so that every subgraph isomorphic to C_2k+1 has no colour repeating on the edges. Is…
For any simple digraph G, we let γ(G) be the number of unordered pairs of nonadjacent vertices (i.e. the number of non-edges), and β(G) be the size of the smallest feedback edge set. Conjecture If G is a simple digraph without directed…
Steinitz conjecture Given vectors v_1,...,v_n∈R^d and a norm X satisfying ∑_i=1^n v_i=0 and ||v_i||_X≤ 1 for all i. Define S_n(X,d)=min_π∈ S^nmax_k=1,...,n|| ∑_i=1^k v_π(i)||_X where S^n is the set of all permutations of [n]. Let…
For every number of variables n and every normalized bounded ratio R on Lorentzian polynomials in n variables, the optimal bounding constant of R is at most 2: opt(R)≤ 2.