Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Is it true that if G is an n-vertex graph with at least 1 Ω(n2− r ) edges then it contains an r-blow-up of a subdivision of Km ? Question 6. Fix m ⩾ 2. What is the smallest c such that for all sufficiently large n the following holds: if G…
Let G=(V,A) be a directed graph with a distinguished source s∈ V, a set of terminals T⊆ V, and a demand d_t≥ 0 for each t∈ T. A flow x=(x_a)_a∈ A with x_a≥ 0 is called feasible (splittable, or fractional) for this instance if it satisfies…
Is the minimum-distance problem for cyclic codes NP-hard?
Can every graph be totally colored with at most Δ + 2 colors, where Δ is the maximum degree?
Let HM_n^m, NHM_n^m, and P_n^m be the corresponding cones of m-hemimetrics, and let the ridge graph of a cone have the facets as vertices, with adjacency when two facets meet in a ridge. Induced-ridge-graph conjecture. The ridge graph of…
Let Σ be a finite subset of C^n and ε a positive number. There exists a positive number r_0(Σ,ε) such that, for any positive integer t and any entire function f in C^n which vanishes on Σ with multiplicity ≥ t, Θ_f(r)≥ ω_t(Σ)-tε for r≥…
Let G be a strongly connected graph, and let B(G) denote the unique ≤_R-maximal right-resolving bunchy factor of G. Write H≤_S G when there is a synchronizing right resolver from G to H. Bunchy factor conjecture. For every strongly…
Are self-supervised models doing kernel PCA? I have introduced this framework and the foundations of the most recent algorith- mic developments, as well as discussed the potential for representation learning in more detail. This talk will…
3APs in sets of small growth Obtain a proof of the following theorem using the polynomial method. Theorem. There is an absolute constant c>0 that the following holds. If A⊂ F_p^n and |A+A|≤ |A|^1+c then A contains a 3AP.
Let G be a graph. A graph is strongly normal if every induced subgraph of G is normal; let overlineG denote the complement of G, and let C_k denote the cycle on k vertices. The strong normal graph characterization conjecture. A graph G is…
Let α(n;k_1,…,k_n) denote the generalized monotone-triangle enumeration, and let n≥1. Even-argument reciprocity conjecture. The identity α(n;2,4,…,2n)=α(2n;2n,2n,2n-2,2n-2,…,2,2) should hold. The paper lists this among identities supported…
Let G be a nice graph, meaning a simple undirected graph with no component isomorphic to K_2. For an integer edge weighting w:E(G)→1,2,…,k, define σ^e(v):=∑_e∋ vw(e). The weighting is neighbor sum distinguishing when adjacent vertices…
conjecture. Conjecture 2. Every proper pivot-minor-closed class of graphs is polynomially χ-bounded. The discussed natural classes closed under pivot-minors are all polynomially χ-bounded. For circle graphs this was proved by Davies and…
Open Problem 1. Open Problem 2. This means that the lower bounds \alpha > \alpha0 (with \alpha0 = 2 and \alpha0 = 25) in the open problems above are not true in general if \alpha0 < 4/3. 3. Critical case: \alpha = 1 In the case \alpha = 1,…
Online Ramsey numbers Jacob Fox The online Ramsey number tilde r(s,n) is defined via a game as follows. Initially there are infinitely many vertices and no edges. Each turn, the builder adds an edge to the graph, and the painter colors the…
For every odd n\ge 7, does every n-vertex graph with minimum degree at least \lceil n/2\rceil contain a spanning copy of the graph obtained from the square of an n-cycle by deleting alternate peripheral edges until exactly three…
Question What is the saturation number of cycles of length 2ℓ in the d-dimensional hypercube?
Given a finite distribution or set of points in the plane or three-dimensional space, what is the maximum number of points that can lie on the graph of a 1-Lipschitz function?
Conjecture 2. (L. Caccetta, R. H¨ aggkvist [5]) Every simple n-vertex digraph with minimum out-degree at least r has a cycle with length at most d n r e. This can be restated in the following way: Let A be an n × n 0-1 matrix such that aij…
Let l≥ 1 be a constant, let f_1,…,f_l be monotone submodular functions on a ground set N, and let S⊆ N have size k with f_i(S)≥ V_i for every i∈[l]. For an integer m satisfying s≥ m≥ l, there should exist a set X⊆ S of size m such that…