Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let G be a graph given by n points in R^2, where any two distinct points are at least distance 1 apart, and we draw an edge between two points if they are distance 1 apart. Let g(n) be maximal such that any such graph always has an…
Given a set of n unit-radius balls in R^3, what is the number of lines that are tangent to four of the balls in the set, and miss all the others? (The balls are not necessarily disjoint.)
Let F(n) be maximal such that every graph on n vertices contains a regular induced subgraph on at least F(n) vertices. Prove that F(n)/log n→ ∞.
Let F(k) be the minimal N such that if we two-colour 1,…,N there is a set A of size k such that all subset sums ∑_a∈ Sa (for ∅ eq S⊆ A) are monochromatic. Estimate F(k).
Must every graph on 2n+1 vertices with n^2+n+1 edges contain two vertices of the same degree joined by a path of length three?
This family of open problems is concerned with low-norm deep networks in clas- sification settings where moreover the model is powerful enough to perfectly label the data. Margin maximization with shallow ReLU networks Matus Telgarsky…
Let A be a hyperplane arrangement in a vector space of dimension ℓ, let L_0 be its intersection lattice with the minimal element removed, and let D denote the lattice sheaf associated with the module of logarithmic vector fields. Lattice…
A planar semi-cover of K_2,2,2,1 is a planar graph G' equipped with the projection structure described in the paper. Suppose G' satisfies the following conditions: if H⊂ G' is the full preimage of the subgraph K_4⊂ K_2,2,2,1 on vertices…
Let X_1,X_2 and X_3 be the partite sets of the complete tripartite graph K_n_1,n_2,n_3, where |X_i|=n_i for i∈ llbracket 3rrbracket. Let F be a spanning forest in K_n_1,n_2,n_3 with k components T_1,T_2,…,T_k. Write n=n_1+n_2+n_3 and…
Let p,q ∈ R_+[x_1,…,x_n] be homogeneous real stable polynomials of total degree d. For a multi-index μ with |μ|=d, write p_μ and q_μ for the corresponding coefficients, let binomdμ denote the multinomial coefficient, and let…
Erdős: How many colors is it necessary to use so that, if you paint every single point of the two-dimensional plane some color, no two points which are a distance one from each other are the same color? (That is, what is the chromatic…
Let n qudits be arranged according to a graph, and let an ε-approximate t-design be formed by a random quantum circuit using two-qudit gates on the graph's edges. The connection count is the number of graph connections required to form the…
If a tree T has bipartition classes of sizes k and 2k, must R(T,T)=4k-1?
The list chromatic number χ_L(G) is defined to be the minimal k such that for any assignment of a list of k colours to each vertex of G (perhaps different lists for different vertices) a colouring of each vertex by a colour on its list can…
A bipartite circle graph is a circle graph whose vertices can be divided into two parts such that edges join only vertices in different parts. A graph H is a pivot-minor of G if it can be obtained from G by pivotings and vertex deletions,…
Conjecture Let G be a planar graph of maximum degree Δ. The chromatic number of its square is at most 7 if Δ =3, at most Δ+5 if 4≤Δ≤ 7, at most ⌊frac32 Δ⌋+1 if Δ≥8.
Does there exist a constant C>1 such that, for every n≥ 2, there exists a sequence z_i∈ C with z_1=1 and lvert z_irvert ≥ 1 for all 1≤ i≤ n with max_2≤ k≤ n+1lvert ∑_1≤ i≤ nz_i^krvert < C^-n?
Let G be an Eulerian oriented planar graph, meaning a connected oriented planar graph in which every vertex has even degree. A vertex set is acyclic when it induces a subdigraph without directed cycles. Eulerian Neumann-Lara conjecture.…
: Suppose we begin with a set of points S in the plane. Let T(S) be the set of points one gets by taking all lines through pairs of points in S, and taking all intersections of those lines. If one iterates T(.), how quickly does the…
How and when can one establish stability of gradient-flow evolution equations on geometric graphs as the number of points n tends to infinity and the connectivity parameter epsilon tends to zero?