Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
For graph sequences, can the inequality beta_Q(G) greater than or equal to beta_{F_p}(G) be strict; can the cost bound beta_K(G)+1 less than or equal to c(G) be strict; and for a finitely generated residually finite group with a Farber…
Let R(G;k) denote the minimal m such that if the edges of K_m are k-coloured then there is a monochromatic copy of G. Show that lim_k→ ∞fracR(C_2n+1;k)R(K_3;k)=0 for any n≥ 2.
Let G be a graph with maximum degree Δ. For a subgraph H⊆ G, vertices of degree Δ(H) are vertices attaining the maximum degree of H. Caro–Lauri–Zarb conjecture. For every k≥ 2 there is a constant g(k) such that one can remove at most…
Given a graph G=(V,E), and weight and capacity functions w,u: E → R_+ defined on the edge set, is there a combinatorial, strongly polynomial algorithm to find a vector x maximizing wx subject to the constraints x ∈ P(G) and x ≤ u, where…
For fixed q, is N_q(g)=max_C#C(F_q) increasing as a function of the genus g?
For a point set P in R^d, let f_d(P) be the number of unit-distance point pairs: f_d(P) = | (u,v) | u, v ∈ P, |u-v| = 1 | ; and let f_d(n) be the maximum over all sets of n points: f_d(n) = max_|P| = n f_d(P) . Further, let g_d(P) denote…
For a graph G let τ(G) denote the minimal number of vertices that include at least one from each maximal clique of G on at least two vertices (sometimes called the clique transversal number). Let H(n) be maximal such that every…
A cubic graph is a graph in which every vertex has degree 3, and it is cyclically 4-edge-connected if at least four edges must be removed to disconnect it into components containing at least two cycles. The circumference ratio of a graph…
Let λ, μ, and ν be Young diagrams with |λ|+|μ|=|ν|. Let A be an admissible order on the skew Young diagram ν∖λ, and let A' be an admissible order on μ. Write P(μ,ν∖λ;A,A') for the set of admissible pictures and B(μ)^ν_λ[A'] for the…
Given a permutation σ, what is the maximum number of copies of σ that a permutation on n symbols may contain?
Let H be a graph and x a vertex. Define H_x(k) to be the subgraph induced by all vertices at distance at most k from x; for vertex-transitive H, write this graph as H(k). Say that a graph H dominates a graph H' when t_H(W)^1/e(H)≥…
Given a finite family cal F of graphs and an integer n, the Turán number ex(n,cal F) of cal F is the largest integer m such that there exists a graph on n vertices with m edges which contains no member of cal F as a subgraph. Conjecture…
Let D^a_n denote the graph used in the paper, with parameters a and n. A non-TRVG is a graph that is not a transparent rectangle visibility graph. The conjecture concerns integers satisfying 2a+5≤ n≤ 2a+7 and a≥ 3. The D^a_n non-TRVG…
For a finite simple graph Gamma and odd prime p, determine the ordinary representation theory of the class-two exponent-p group G_Gamma(Fp), in particular how the number of irreducible characters of degree p^i depends on p for each i at…
For a graph with the parameters and family of cuts defined in Lemma~, let C^ind denote the corresponding family of induced cuts. Bounded enumeration conjecture. Lemma~ holds with |C^ind| ≤ 2^O(1/δ). This conjecture proposes that the family…
Let P be a finite poset that is not a chain. Consider two consecutive comparisons, and let t_0=e(P), where e(P) is the number of linearizations of P; let t_1 be the number of linearizations of the poset after the first comparison, and let…
Mubayi and R"odl~\cite{mubayi+rodl:02} have given bounds on π(C_5^3), where C_5^3 is the tight 3-graph 5-cycle: C_5^3=123,234,345,451,512. In particular, the lower bound π(C_5^3)≥ 2√3-3 comes from the following construction: partition the…
Let G be a graph, and let σ(G) denote the minimum number of equivalence relations needed to cover the line graph structure under the paper's definition. For an integer k≥ 3, the NP-completeness conjecture. It is NP-complete to decide…
Let r be fixed and let H(r) be the Hamming ball of radius r in F_2^n. Let f(r) be the smallest constant such that there exist infinitely many n with subspaces V_n ≤ F_2^n satisfying V_n + H(r) = F_2^n and |V_n| = (f(r) + o(1)) 2^n/|H(r)|.…
Let X be the Cartesian product of k directed cycles of lengths m_1,m_2,…,m_k, where k≥ 3 and each m_i≥ 2. For vertices u and v of X, let d_X(u,v) denote the length of a shortest directed path from u to v. Hamiltonian-path distance…