Skip to content

Erdős problem 621

Let GG be a graph on nn vertices, α1(G)\alpha_1(G) be the maximum number of edges that contain at most one edge from every triangle, and τ1(G)\tau_1(G) be the minimum number of edges that contain at least one edge from every triangle.

Sources

Browse retained paths and inspect the exact material available for this Problem.

1 retained statement2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

621.lean

Retained formal statement1 of 1

Let GG be a graph on nn vertices, α1(G)\alpha_1(G) be the maximum number of edges that contain at most one edge from every triangle, and τ1(G)\tau_1(G) be the minimum number of edges that contain at least one edge from every triangle.

Is it true thatα1(G)+τ1(G)n24?\alpha_1(G)+\tau_1(G) \leq \frac{n^2}{4}?

A problem of Erdős, Gallai, and Tuza [EGT96], who observe that this is probably quite difficult since there are different examples where equality hold: the complete graph, the complete bipartite graph, and the graph obtained from Km,mK_{m,m} by adding one vertex joined to every other.

This is true, and was proved by Norin and Sun [NoSu16], who in fact proved thatα1(G)+τB(G)n24,\alpha_1(G)+\tau_B(G) \leq \frac{n^2}{4},where τB(G)\tau_B(G) is the minimum number of edges that need to be removed to make the graph bipartite.

Here α1(G)\alpha_1(G) and τ1(G)\tau_1(G) are taken over subsets of the edge set of GG, and the inequality is stated multiplied through by 44 so that it lives in the natural numbers.

The linked file states τ1\tau_1 as the least number of edges whose deletion leaves GG triangle-free, which is the same as meeting every triangle of GG, and quantifies over an arbitrary Fintype V rather than Fin n.

FormalConjectures/ErdosProblems/621.leanErdos621.erdos_62115 linesExact file
True  ∀ (n : ℕ) (G : SimpleGraph (Fin n)) (a t : ℕ),    IsGreatest        {k |AG.edgeFinset,            A.card = k              ∀ (x y z : Fin n), G.Adj x yG.Adj y zG.Adj x z → ({s(x, y), s(y, z), s(x, z)} ∩ A).card ≤ 1}        a      IsLeast          {k |TG.edgeFinset,              T.card = k                ∀ (x y z : Fin n), G.Adj x yG.Adj y zG.Adj x z → (T ∩ {s(x, y), s(y, z), s(x, z)}).Nonempty}          t        4 * (a + t) ≤ n ^ 2
SolvedProof has a holelean4external proof

The proof uses `sorry`: part of the argument is written but not proved. Lean accepts the file; it does not accept the theorem.

Search problems.science

Find a Problem, Result, source, or page