Tuza's conjecture

Last updated

Packing and covering triangles in the complete graph
K
5
{\displaystyle K_{5}}
. The maximum number of edge-disjoint triangles in this graph is two (left). If four edges are removed from the graph (red edges, right), the remaining subgraph becomes triangle-free, and more strongly bipartite (as shown by the blue and yellow vertex coloring). According to Tuza's conjecture, in any graph, it is possible to remove twice as many edges as the maximum triangle packing size, and eliminate all triangles.
K
5
{\displaystyle K_{5}}
is an extreme case, for which exactly twice the packing size is needed. K5 triangle packing and covering.svg
Packing and covering triangles in the complete graph . The maximum number of edge-disjoint triangles in this graph is two (left). If four edges are removed from the graph (red edges, right), the remaining subgraph becomes triangle-free, and more strongly bipartite (as shown by the blue and yellow vertex coloring). According to Tuza's conjecture, in any graph, it is possible to remove twice as many edges as the maximum triangle packing size, and eliminate all triangles. is an extreme case, for which exactly twice the packing size is needed.

Tuza's conjecture is an unsolved problem in graph theory, a branch of mathematics, concerning triangles in undirected graphs.

Contents

Statement

In any graph , one can define two quantities and based on the triangles in . The quantity is the "triangle packing number", the largest number of edge-disjoint triangles that it is possible to find in . [1] It can be computed in polynomial time as a special case of the matroid parity problem. [2] The quantity is the size of the smallest "triangle-hitting set", a set of edges that touches at least one edge from each triangle. [1]

Clearly, . For the first inequality, , any triangle-hitting set must include at least one edge from each triangle of the optimal packing, and none of these edges can be shared between two or more of these triangles because the triangles are disjoint. For the second inequality, , one can construct a triangle-hitting set of size by choosing all edges of the triangles of an optimal packing. This must hit all triangles in , even the ones not in the packing, because otherwise the packing could be made larger by adding any unhit triangle. [1]

Tuza's conjecture asserts that the second inequality is not tight, and can be replaced by . That is, according to this unproven conjecture, every undirected graph has a triangle-hitting set whose size is at most twice the number of triangles in an optimal packing. [1]

History and partial results

Zsolt Tuza formulated Tuza's conjecture in 1981. [1] [3] If true, it would be best possible: there are infinitely many graphs for which , including all of the block graphs whose blocks are cliques of 2, 4, or 5 vertices. [1]

The conjecture is known to hold for planar graphs, [1] and more generally for sparse graphs of degeneracy at most six. [4] (Planar graphs have degeneracy at most five.) It is also known to hold for graphs of treewidth at most six, [5] for threshold graphs, [6] for sufficiently dense graphs, and for chordal graphs that contain a large clique. [1] For random graphs in the Erdős–Rényi–Gilbert model, it is true with high probability. [7]

Although Tuza's conjecture remains unproven, the bound can be improved, for all graphs, to . [8]

See also

Related Research Articles

<span class="mw-page-title-main">Convolution</span> Integral expressing the amount of overlap of one function as it is shifted over another

In mathematics, convolution is a mathematical operation on two functions that produces a third function that expresses how the shape of one is modified by the other. The term convolution refers to both the result function and to the process of computing it. It is defined as the integral of the product of the two functions after one is reflected about the y-axis and shifted. The choice of which function is reflected and shifted before the integral does not change the integral result. The integral is evaluated for all values of shift, producing the convolution function.

In graph theory, the girth of an undirected graph is the length of a shortest cycle contained in the graph. If the graph does not contain any cycles, its girth is defined to be infinity. For example, a 4-cycle (square) has girth 4. A grid has girth 4 as well, and a triangular mesh has girth 3. A graph with girth four or more is triangle-free.

<span class="mw-page-title-main">Discrete geometry</span> Branch of geometry that studies combinatorial properties and constructive methods

Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geometric objects, such as points, lines, planes, circles, spheres, polygons, and so forth. The subject focuses on the combinatorial properties of these objects, such as how they intersect one another, or how they may be arranged to cover a larger object.

In mathematics, the Poisson summation formula is an equation that relates the Fourier series coefficients of the periodic summation of a function to values of the function's continuous Fourier transform. Consequently, the periodic summation of a function is completely defined by discrete samples of the original function's Fourier transform. And conversely, the periodic summation of a function's Fourier transform is completely defined by discrete samples of the original function. The Poisson summation formula was discovered by Siméon Denis Poisson and is sometimes called Poisson resummation.

In combinatorics, a greedoid is a type of set system. It arises from the notion of the matroid, which was originally introduced by Whitney in 1935 to study planar graphs and was later used by Edmonds to characterize a class of optimization problems that can be solved by greedy algorithms. Around 1980, Korte and Lovász introduced the greedoid to further generalize this characterization of greedy algorithms; hence the name greedoid. Besides mathematical optimization, greedoids have also been connected to graph theory, language theory, order theory, and other areas of mathematics.

<span class="mw-page-title-main">Perfect graph</span> Graph with tight clique-coloring relation

In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.

<span class="mw-page-title-main">Critical graph</span>

In graph theory, a critical graph is an undirected graph all of whose subgraphs have smaller chromatic number. In such a graph, every vertex or edge is a critical element, in the sense that its deletion would decrease the number of colors needed in a graph coloring of the given graph. The decrease in the number of colors cannot be by more than one.

In combinatorics, a Sperner family, or clutter, is a family F of subsets of a finite set E in which none of the sets contains another. Equivalently, a Sperner family is an antichain in the inclusion lattice over the power set of E. A Sperner family is also sometimes called an independent system or irredundant set.

<span class="mw-page-title-main">Polytree</span>

In mathematics, and more specifically in graph theory, a polytree is a directed acyclic graph whose underlying undirected graph is a tree. In other words, if we replace its directed edges with undirected edges, we obtain an undirected graph that is both connected and acyclic.

The arboricity of an undirected graph is the minimum number of forests into which its edges can be partitioned. Equivalently it is the minimum number of spanning forests needed to cover all the edges of the graph. The Nash-Williams theorem provides necessary and sufficient conditions for when a graph is k-arboric.

In mathematics, the theory of optimal stopping or early stopping is concerned with the problem of choosing a time to take a particular action, in order to maximise an expected reward or minimise an expected cost. Optimal stopping problems can be found in areas of statistics, economics, and mathematical finance. A key example of an optimal stopping problem is the secretary problem. Optimal stopping problems can often be written in the form of a Bellman equation, and are therefore often solved using dynamic programming.

<span class="mw-page-title-main">Branch-decomposition</span> Hierarchical clustering of graph edges

In graph theory, a branch-decomposition of an undirected graph G is a hierarchical clustering of the edges of G, represented by an unrooted binary tree T with the edges of G as its leaves. Removing any edge from T partitions the edges of G into two subgraphs, and the width of the decomposition is the maximum number of shared vertices of any pair of subgraphs formed in this way. The branchwidth of G is the minimum width of any branch-decomposition of G.

Discrete Morse theory is a combinatorial adaptation of Morse theory developed by Robin Forman. The theory has various practical applications in diverse fields of applied mathematics and computer science, such as configuration spaces, homology computation, denoising, mesh compression, and topological data analysis.

In the mathematics of structural rigidity, a rigidity matroid is a matroid that describes the number of degrees of freedom of an undirected graph with rigid edges of fixed lengths, embedded into Euclidean space. In a rigidity matroid for a graph with n vertices in d-dimensional space, a set of edges that defines a subgraph with k degrees of freedom has matroid rank dn − k. A set of edges is independent if and only if, for every edge in the set, removing the edge would increase the number of degrees of freedom of the remaining subgraph.

In the mathematical theory of matroids, the rank of a matroid is the maximum size of an independent set in the matroid. The rank of a subset S of elements of the matroid is, similarly, the maximum size of an independent subset of S, and the rank function of the matroid maps sets of elements to their ranks.

<span class="mw-page-title-main">Matroid parity problem</span> Largest independent set of paired elements

In combinatorial optimization, the matroid parity problem is a problem of finding the largest independent set of paired elements in a matroid. The problem was formulated by Lawler (1976) as a common generalization of graph matching and matroid intersection. It is also known as polymatroid matching, or the matchoid problem.

In graph theory, a matching in a hypergraph is a set of hyperedges, in which every two hyperedges are disjoint. It is an extension of the notion of matching in a graph.

In graph theory, a vertex cover in a hypergraph is a set of vertices, such that every hyperedge of the hypergraph contains at least one vertex of that set. It is an extension of the notion of vertex cover in a graph.

In the mathematical field of graph theory, Hall-type theorems for hypergraphs are several generalizations of Hall's marriage theorem from graphs to hypergraphs. Such theorems were proved by Ofra Kessler, Ron Aharoni, Penny Haxell, Roy Meshulam, and others.

In graph theory, Ryser's conjecture is a conjecture relating the maximum matching size and the minimum transversal size in hypergraphs.

References

  1. 1 2 3 4 5 6 7 8 Tuza, Zsolt (1990), "A conjecture on triangles of graphs", Graphs and Combinatorics, 6 (4): 373–380, doi:10.1007/BF01787705, MR   1092587
  2. Lawler, Eugene L. (1976), "Chapter 9: The Matroid Parity Problem", Combinatorial Optimization: Networks and Matroids, New York: Holt, Rinehart and Winston, pp. 356–367, MR   0439106
  3. Tuza, Zsolt (1984), "Conjecture", in Hajnal, A.; Lovász, L.; Sós, V. T. (eds.), Finite and Infinite Sets: Proceedings of the sixth Hungarian combinatorial colloquium held in Eger, July 6–11, 1981, Colloquia Mathematica Societatis János Bolyai, vol. 37, p. 888, ISBN   0-444-86763-5, MR   0818224
  4. Puleo, Gregory J. (2015), "Tuza's conjecture for graphs with maximum average degree less than 7", European Journal of Combinatorics, 49: 134–152, arXiv: 1308.2211 , doi:10.1016/j.ejc.2015.03.006, MR   3349530
  5. Botler, Fábio; Fernandes, Cristina G.; Gutiérrez, Juan (2021), "On Tuza's conjecture for triangulations and graphs with small treewidth", Discrete Mathematics , 344 (4), Paper No. 112281, arXiv: 2002.07925 , doi:10.1016/j.disc.2020.112281, MR   4204419
  6. Bonamy, Marthe; Bożyk, Łukasz; Grzesik, Andrzej; Hatzel, Meike; Masařík, Tomáš; Novotná, Jana; Okrasa, Karolina (2022), "Tuza's conjecture for threshold graphs", Discrete Mathematics & Theoretical Computer Science, 24 (1): P24:1–P24:14, arXiv: 2105.09871 , MR   4471222
  7. Kahn, Jeff; Park, Jinyoung (2022), "Tuza's conjecture for random graphs", Random Structures & Algorithms, 61 (2): 235–249, MR   4456027
  8. Haxell, P. E. (1999), "Packing and covering triangles in graphs", Discrete Mathematics , 195 (1–3): 251–254, doi: 10.1016/S0012-365X(98)00183-6 , MR   1663859