Lesson plan

Tardos function

In graph theory and circuit complexity, the Tardos function is a graph invariant introduced by Éva Tardos in 1988 that has the following properties: *Like the Lovász number of the complement of a graph, the Tardos function is sandwiched between the clique number and the chromatic number of the graph. These two numbers are both NP-hard to compute. *The Tardos function is monotone, in the sense that adding edges to a graph can only cause its Tardos function to increase or stay the same, but never decrease. *The Tardos function can be computed in polynomial time. *Any monotone circuit for computing the Tardos function requires exponential size. To define her function, Tardos uses a polynomial-time approximation scheme for the Lovász number, based on the ellipsoid method and provided by . Approximating the Lovász number of the complement and then rounding the approximation to an integer would not necessarily produce a monotone function, however. To make the result monotone, Tardos approximates the Lovász number of the complement to within an additive error of 1/n^2 , adds m/n^2 to the approximation, and then rounds the result to the nearest integer. Here m denotes the number of edges in the given graph, and n denotes the number of vertices.…

Back to article

Article summary

In graph theory and circuit complexity, the Tardos function is a graph invariant introduced by Éva Tardos in 1988 that has the following properties: *Like the Lovász number of the complement of a graph, the Tardos function is sandwiched between the clique number and the chromatic number of the graph. These two numbers are both NP-hard to compute. *The Tardos function is monotone, in the sense that adding edges to a graph can only cause its Tardos function to increase or stay the same, but never decrease. *The Tardos function can be computed in polynomial time. *Any monotone circuit for computing the Tardos function requires exponential size. To define her function, Tardos uses a polynomial-time approximation scheme for the Lovász number, based on the ellipsoid method and provided by . Approximating the Lovász number of the complement and then rounding the approximation to an integer would not necessarily produce a monotone function, however. To make the result monotone, Tardos approximates the Lovász number of the complement to within an additive error of 1/n^2 , adds m/n^2 to the approximation, and then rounds the result to the nearest integer. Here m denotes the number of edges in the given graph, and n denotes the number of vertices.…

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.