Turán's triangle theorem and binary matroids
A special case of a theorem of Turán is that a graph on v vertices, with no loops, parallel edges, or triangles, has no more than \(\lfloor v/2\rfloor \lceil v/2\rceil\) edges. This bound is achieved by a graph G if and only if \(G\cong K_{\lfloor v/2\rfloor,\lceil v/2\rceil}\). We generalize this result to binary maroids. In particular, we show that if \(M=(E,{\mathcal C})\) is a rank r, binary maroid with no minor isomorphic to the dual of the Fano matroid, and if \(| C| \geq 4\) \(\forall C\in {\mathcal C}\), then \(| E| \leq \lfloor (r+1)/2)\rfloor \lceil (r+1)/2\rceil\), unless \(M\cong R_{10}\). Moreover, if the bound is attained then M is isomorphic to the circuit matroid of \(K_{\lfloor (r+1)/2\rfloor,\lceil (r+1)/2\rceil}\).
- A Tverberg type theorem for matroids
- Menger's theorem for matroids
- An Erdős-Gallai theorem for matroids
- On ternary transversal matroids
- On Vertex-Triads in 3-Connected Binary Matroids
- Tutte Polynomials and Bicycle Dimension of Ternary Matroids
- The critical number of dense triangle-free binary matroids
- The binary matroids whose only odd circuits are triangles
- On the cogirth of binary matroids
- Consequences of the Brylawski-Lucas theorem for binary matroids
This page was built for publication: Turán's triangle theorem and binary matroids
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1117942)
