Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Given a single-source network with capacities u, costs c, source s, sinks t_i, and demands d_i satisfying the no-bottleneck condition d_{max}\leq u_e, does every splittable flow x satisfying the demands admit an unsplittable flow y…
Let (G_n)_n∈ N be a sequence of connected graphs, with n vertices, edge set E_n, and maximum degree Δ_n. Let t_n be a non-negative sequence of times, let f_n(η_0,ω) denote the consensus opinion of the voter model, and let ω_t_n denote the…
Let G be a connected weakly closed graph, let S=K[x_1,…,x_n,y_1,…,y_n], and let J_G be its binomial edge ideal. Let ℓ denote the length of the longest induced path of G. Regularity conjecture for weakly closed graphs. If the longest…
Let d∈N_>0, let F∈N^d, and let N(F) denote the number of generalized numerical semigroups with Frobenius element F. For d≠ 5, define d_1=lceild+1/3⌉ and a_d=((√3)^frac12^d∑_i=d_1^d-d_1binomdi× (2)^1/2^d∑_i=d-d_1+1^2d_1-1binomdi), while…
Let T be a tree, let B_nT denote the braid group on n strands on T, and let H^*(B_nT) denote its cohomology ring. An exterior face algebra is the exterior face algebra structure on this cohomology ring. Exterior face algebra conjecture.…
A perfect binary sequence is a binary periodic sequence of period n with constant periodic autocorrelation at every nonzero shift; d denotes this constant autocorrelation value. Schmidt's conjecture. There do not exist perfect binary…
Let n,m≥ 2 and let G=B_n,m be the dumbbell graph. The NF-number conjecture. NF(G)= 2, (n,m)=(2,2), n+m+2, otherwise. The preceding results determine the first two iterates of the NF-operator for B_n,m and motivate this conjectural formula…
Conjecture. In any 2-coloring of E^2, every 3-point set X occurs monochromatically (as some congruent copy), except possibly for the three points that form some specific equilateral triangle. (Example coloring: half-open horizontal stripes…
For a digraph D=(V,A), we call a nonempty C⊆ A a dicut if there is some X⊆ V such that no edge enters X and C consists of the outgoing edges of X. The conjecture states that for any D, there exists a system C of pairwise disjoint finite…
We say that a graph is 4-chromatic critical if it has chromatic number 4, and removing any edge decreases the chromatic number to 3. Is there, for arbitrarily large n, a 4-chromatic critical graph on n vertices with minimum degree ≫ n?
Let M=(E,I) be a matroid with rank function r. It is Hamiltonian if some cyclic ordering of E has the property that every segment of r(M) consecutive elements is a basis of M. It is uniformly dense if, for every nonempty subset X⊆ E,…
problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 Michael Krivelevich (joint with Sahar Diskin, Itay Markbreit, Maksim Zhukovskii) A large hole in pseudo-random graphs . . . . . . . . . . . . . .…
Is it true that every smooth polytope has the integer decomposition property?
For integers n>2 and k>1, let F_n,k(x)=Φ_n(1+x+…+x^k)∈Q[x], where Φ_n is the n-th cyclotomic polynomial. Determine, exactly in terms of n and k, whether F_n,k(x) is reducible over Q and, in the reducible cases, determine the number of…
Is there a scale at which the structure of a (real) network ``looks like'' a manifold? (e.g., Krioukov's result)
For a graph G, write f_G(r) for its growth function, and let Gboxtimes H denote the strong product of graphs G and H. Let K_t be the complete graph on t vertices. A graph has polynomial growth with parameters c and d when f_G(r)leqslant…
Let G) be a tree on n vertices, and let F_k(G) denote its k-token graph, whose vertices are the k-subsets of V(G). For a fixed integer k satisfying 1≤ k≤ n-1, the treewidth order conjecture for token graphs of trees. tw(F_k(G)) ∈ Θ(n^k-1).…
Let n be a positive integer, let R_n denote the 2-rigidity matroid on the edge set of the complete graph on [n], and let K_3,3 be the complete bipartite graph with parts of size three. A matroid on this edge set is symmetric if it is…
Caccetta--H"aggkvist conjecture: every n-vertex digraph with minimum outdegree at least r contains a directed cycle of length at most \lceil n/r\rceil.
Let t and r be positive integers, and let δ_t,r(Z^2) denote the minimum density of a (t,r)-broadcasting set in the infinite square grid. Asymptotic sharpness conjecture. For every r≥ 2, there exists an integer t_0 such that for every t≥…