Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let cf G be a class of graphs, let CMSO_1xspace denote counting monadic second-order logic with one free set-variable type, let τ be a CMSO_1xspace transduction, and let P_t denote the path on t vertices. Transduction characterization…
Let R_3(n) be the minimal m such that if the edges of the 3-uniform hypergraph on m vertices are 2-coloured then there is a monochromatic copy of the complete 3-uniform hypergraph on n vertices. Is there some constant c>0 such that R_3(n)…
Let triangle be a lattice polygon, let e run over its edges, and let ℓ(e) denote the lattice length of e. For a zero mutable Laurent polynomial f with Newton polygon triangle, let p_e(f)=(s_e,l)_l=1^w be the decreasing partition associated…
Speed up the computation of cryptographic pairings.
Let P=(X,≤) be a finite partially ordered set, so that ≤ is a reflexive, antisymmetric, transitive binary relation on the finite set X. A linear extension of P is a total order preceq on X such that x≤ y implies xpreceq y for all x,y∈ X.…
Let G be a graph on n vertices with minimum degree at least δ, where n and δ satisfy n ≥ 2δ. Let i(G) denote the total number of independent sets in G, and let K_δ,n-δ be the complete bipartite graph with parts of sizes δ and n-δ.…
How does stochasticity contribute in regard to this? • What is the amount of data needed for such a network to achieve a small estimation error with high probability? The report passage is retained verbatim as the relevant context for this…
For an integer k, a graph has girth at least k if its shortest cycle has length at least k. A graph has sufficiently large minimum degree when its minimum degree exceeds a threshold depending on k. Thomassen's conjecture. For every integer…
Conjecture: s_r(3) = Θ(r^2 log r) Remark: This would follow from the extension of the triangle-free process to r colors.
Prove finiteness of the Shafarevich–Tate group of the elliptic-curve lift required by the Huang–Raskind method, in the general cases where it is not known.
For which values of k is the following true: whenever we partition [N] = A_1 ∪ … ∪ A_k, we have |bigcup_i=1^k (A_i hat+ A_i)| ≥ 1/10 N?
Conjecture: (Fox--Grinshpun--Liebenau--Person--Szab'o) s_r(k) = Θ(r · f_k,k+1(r)^2) where f_k,k+1 is the Erd\H{o}s-Rogers function, to be discussed in Dudek's talk.
For every pair of uniform matroids U_r,n and U_s,m, there exists a freest matroid product of U_r,n and U_s,m; equivalently, the relevant class of products has a maximal element in the freeness order.
Let T_M^d be the d-dimensional toroidal grid with all side lengths equal to M, and let R_rm ave(T_M^d) denote its average effective resistance. More generally, let T_M_1,…,M_d be a toroidal grid with side lengths M_1,…,M_d and total size…
Let G be a simple graph, let I be its edge ideal, and let I^[k] denote its kth squarefree power. Let ν_0(G) be the maximum size of a restricted matching in G, with ν_0(G)=1 if no restricted matching exists. Squarefree-power threshold…
Let t_4k+1^e denote the even involution count associated with size 4k+1, let ord_2 be the 2-adic valuation, and let χ_o(k) be the indicator of odd integers. A 2-adic integer is an element of Z_2; write ρ=∑_i≥ 0ρ_i2^i, where 0≤ρ_i≤1. 2-adic…
Let P be the Petersen graph, and let phi_2(P) denote its 2-dimensional flow number. Petersen graph flow-number conjecture. φ_2(P)=1+√7/3. The paper gives the matching upper bound and proposes equality based on computational evidence; no…
Let E=v_1,…,v_n be a spanning subset of a d-dimensional complex vector space V, and let w_i(E) denote the number of i-dimensional subspaces spanned by subsets of E. Rota's unimodal conjecture. There exists an index j such that w_0(E)≤…≤…
Construct improved practical trapdoor pairings.
Let G be a graph of order n, let k≥ 3 be an integer, and let n_1,…,n_k be positive integers satisfying ∑_i=1^kn_i=n. Write σ_2(G) for the minimum degree sum of two nonadjacent vertices. Enomoto and Ota's conjecture. If σ_2(G)≥ n+k-1, then…