Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
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≥…
A graphical degree sequence is a finite sequence of nonnegative integers realised as the degree sequence of a finite simple graph. A graph is triangular if every edge belongs to a 3-cycle. Triangular realisation conjecture. Any graphical…
Let (Δ_n)_n≥ 1 be an Inc-invariant chain of simplicial complexes, where each Δ_n is a simplicial complex on [n]:=1,…,n. Here Inc is the monoid of increasing maps, and Inc-invariance means Inc(N(Δ_n))⊆N(Δ_n+1) for all n≥ 1, with N(Δ_n)…
For an integer e>1, let g(e) be the largest integer such that every triangle-free graph with e edges contains a bipartite subgraph with at least g(e) edges. Determine the order of g(e)-e/2.
Throughout, graphs are finite, simple, and undirected. Let k be a positive integer, and let T be a tree with bipartition (X,Y). A graph is k-connected when its connectivity satisfies κ(G)≥ k; δ(G) denotes minimum degree, and G-V(T') is the…
Does there exist \varepsilon>0 such that every edge-ordered graph G has an increasing path of length \Omega((e(G)/|G|)^{1/2+\varepsilon})?
Let C>0. There exists ε>0 such that if n is sufficiently large the following holds. For any x_1,…,x_n∈ [-1,1] there exist y_1,…,y_n∈ [-1,1] such that, if P is a polynomial of degree m<(1+ε)n with P(x_i)=y_i for at least (1-ε)n many 1≤ i≤…
For a positive integer m, let [m]=1,…,m, and let σ and τ be set partitions of [m], with τ≥σ meaning that every block of σ is contained in some block of τ. Write ℓ(σ) for the number of blocks of σ, let (λ(τ)-1)! denote the product of the…
Open questions To conclude, by our results it follows that there is a constant c ⩽ 60 such that any n-vertex properly edge-coloured graph G with at least n(log n)c edges contains a rainbow subdivision of Km . We pose the following…
For every admissible parameter triple (n,d,s) and every relevant witness family F, the uniform witness conjecture asserts that lvertFrvert≤binomn-1d; equivalently, the extremal quantity for such witness families is at most binomn-1d.
For a cardinal κ, the shift graph Sh_n(κ) has as vertices the increasing n-tuples of ordinals less than κ, with adjacency defined by the shift condition. A graph G contains all finite subgraphs of another graph when every finite subgraph…
For k≥ 2, let G_n,k be the graph obtained from K_k,n-k by adding all edges among the k vertices in the first part; equivalently, it is the k-fold cone over n-k isolated vertices. Let P_G be the symmetric edge polytope of a graph G on n…
Let B=b_1,b_2,… ,b_k⊂0,1,… ,n-1, and let B_i=b_1+i, b_2+i,…, b_k+i where addition is modulo n. That is, B=B_1,B_2,… B_N is the collection of cyclic translates of B. Prove that there exists a binary matroid M such that every B_i is a basis…
Let G be a graph on 2n vertices that is the union of three disjoint perfect matchings. An (a_1,a_2,a_3)-matching is a matching containing exactly a_i edges from the ith perfect matching. Suppose that G has a component that is not…
For integers r≥ 2, let f(r,3) denote the limiting maximum proportion of vertices that can be guaranteed in each of two disjoint subsets separated by a cut vector for any three trees with a common vertex set labeled by [n] and maximum…
Does every infinite Cayley graph, or every infinite vertex-transitive graph, have a spanning tree without leaves?
Let G be a connected graph with n nodes. Write P_n for the path graph on n nodes, K_n for the complete graph on n nodes, and let the average communicability angle be the average of the communicability angles over pairs of nodes. Extremal…
For a graph G, its k-deck is the multiset of induced subgraphs with k vertices, and G is ℓ-reconstructible when it is determined by the deck obtained by deleting ℓ vertices. Manvel's Kelly conjecture. For each natural number ℓ, there is a…
For every finite graph G and every integer k≥ 1, if P(G,k)=P_ℓ(G,k)>0, then P(G,k+1)=P_ℓ(G,k+1), where P(G,k) is the number of proper k-colorings of G and P_ℓ(G,k)=min_L|proper L-colorings of G| is the minimum, over all assignments L of…
Find reasonable bounds for instances of the multidimensional Szemerédi theorem.