Reiman's theorem

The set of Reiman is a theorem from the mathematical sub-area of combinatorics which the Hungarian mathematician István Reiman back (1927-2012). The theorem formulates a necessary condition for a finite simple graph not to contain any circles of length 4 as subgraphs .

Formulation of the sentence

The set of Reiman can be formulated as follows:

A finite simple graph with nodes and edges is given.   ${\displaystyle {\mathcal {G}}=(V,E)}$ ${\displaystyle |V|=n}$ ${\displaystyle |E|=m}$ ${\displaystyle (n,m\in \mathbb {N} )}$

It is also assumed:

(B) There are no circles of four as subgraphs. ${\displaystyle {\mathcal {G}}}$

Then the inequality holds :

(U)   . ${\displaystyle m\leq \lfloor {{\frac {n}{4}}(1+{\sqrt {4n-3}})}\rfloor }$

In other words:

If there is an edge number that genuinely exceeds the real number , at least one circle of four must be included as a subgraph. ${\displaystyle {\mathcal {G}}}$ ${\displaystyle m}$ ${\displaystyle {\frac {n}{4}}(1+{\sqrt {4n-3}})}$ ${\displaystyle {\mathcal {G}}}$

Evidence sketch

The proof is based on an application of the double counting method , the handshake lemma, and the Cauchy-Schwarz inequality .

This is where you start from the amount

${\displaystyle S=\{(v_{0},\{v,w\})\mid {\bigl (}v_{0},v,w\in V{\bigr )}\land {\bigl (}v\neq w{\bigr )}\land {\bigl (}\{v_{0},v\},\{v_{0},w\}\in E{\bigr )}\}}$.

${\displaystyle S}$consists of exactly all those pairs in the graph for which the node with the two other nodes and is adjacent . ${\displaystyle (v_{0},\{v,w\})}$ ${\displaystyle {\mathcal {G}}}$ ${\displaystyle v_{0}}$ ${\displaystyle v}$ ${\displaystyle w}$

Because of (B) in connection with the degrees, the individual nodes are obtained for this one after the other

${\displaystyle \sum _{v\in V}{\binom {d_{\mathcal {G}}(v)}{2}}=|S|\leq {\binom {n}{2}}}$

and thus

${\displaystyle n\cdot \sum _{v\in V}{{d_{\mathcal {G}}(v)}^{2}}\leq n^{2}(n-1)+n\cdot \sum _{v\in V}{d_{\mathcal {G}}(v)}}$

and then

${\displaystyle \left(\sum _{v\in V}{d_{\mathcal {G}}(v)}\right)^{2}\leq n^{2}(n-1)+n\cdot \sum _{v\in V}{d_{\mathcal {G}}(v)}}$

and finally

${\displaystyle 4m^{2}\leq n^{2}(n-1)+2nm}$  .

From the last inequality, however, one arrives directly at inequality (U) by means of quadratic completion .

annotation

The inequality given by the theorem is sharp in the sense that for a graph with five nodes and six edges there exists where the inequality becomes an equation. It is a windmill graph ( English Windmill graph ) composed of two triangular graph is formed (as part of graph), which exactly one node as a point of intersection have. ${\displaystyle n=5}$ ${\displaystyle {\mathcal {G}}}$

literature

• Martin Aigner , Günter M. Ziegler : Proofs from THE BOOK . 2nd Edition. Springer Verlag, Berlin ( inter alia ) 1999, ISBN 3-540-63698-6 ( MR1723092 ).
• Martin Aigner , Günter M. Ziegler : The BOOK of evidence . 4th edition. Springer Spectrum, Berlin (among others) 2014, ISBN 978-3-662-44456-6 .
• Stasys Jukna: Extremal Combinatorics (=  Texts in Theoretical Computer Science ). 2nd Edition. Springer Verlag, Heidelberg / Dordrecht / London / New York 2011, ISBN 978-3-642-17363-9 ( MR2865719 ).
• I. Reiman : On a problem by K. Zarankiewicz . In: Acta Math. Acad. Sci. Hungar . tape 9 , 1958, pp. 269-273 . MR0101250 MR3184547
• Jonathan Gross, Jay Yellen (Eds.): Handbook of Graph Theory (=  Discrete Mathematics and its Applications ). CRC Press, Boca Raton (et al.) 2004, ISBN 1-58488-090-2 .

References and comments

1. ↑ In graph theory , a circle of length 4 is a graph that is isomorphic to the circle graph . Such is also referred to as a circle of four for short . See Martin Aigner , Günter M. Ziegler : The BOOK of evidence . 4th edition. Springer Spectrum, Berlin (among others) 2014, ISBN 978-3-662-44456-6 , p. ${\displaystyle C_{4}}$  210 .
2. ↑ Aigner-Ziegler: The BOOK of evidence . S. 210-211 .
3. ↑ Martin Aigner , Günter M. Ziegler : Proofs from THE BOOK . 2nd Edition. Springer Verlag, Berlin (inter alia) 1999, ISBN 3-540-63698-6 , pp. 128-129 ( MR1723092 ).
4. ↑ Stasys Jukna: Extremal Combinatorics (=  Texts in Theoretical Computer Science ). 2nd Edition. Springer Verlag, Heidelberg / Dordrecht / London / New York 2011, ISBN 978-3-642-17363-9 , pp. 24-26 ( MR2865719 ).
5. ↑   is the Gaussian bracket function . ${\displaystyle x\mapsto \lfloor x\rfloor }$
6. ↑ Martin Aigner , Günter M. Ziegler : The BOOK of evidence . 4th edition. Springer Spectrum, Berlin (among others) 2014, ISBN 978-3-662-44456-6 , p. 210-211 .