\documentclass[12pt]{article}
\usepackage{e-jc}

\title{An Abstraction of Whitney's Broken Circuit Theorem}

\author{Klaus Dohmen \\ 
\small  Department of Mathematics\\[-0.8ex]
\small  Mittweida University of Applied Sciences\\[-0,8ex] 
\small  Mittweida, Germany\\
\small\tt dohmen@hs-mittweida.de\\
\and
Martin Trinks \\
\small Center for Combinatorics\\[-0.8ex]
\small Nankai University\\[-0.8ex]
\small Tianjin, China\\
\small\tt martin.trinks@googlemail.com
}

\date{\dateline{May 8, 2014}{XX} \\
  \small Mathematics Subject Classifications: 05A15, 05C30, 05C31, 06A07,
  11A25, 52A01}

\usepackage[backend=biber,sorting=nyt]{biblatex}

%-------------- contents of the biblatex bbl file ------------------
\makeatletter
\def\blx@bblfile@biber{%
  \blx@secinit
  \begingroup
  \blx@bblstart
\begingroup
\makeatletter
\@ifundefined{ver@biblatex.sty}
  {\@latex@error
     {Missing 'biblatex' package}
     {The bibliography requires the 'biblatex' package.}
      \aftergroup\endinput}
  {}
\endgroup

\refsection{0}
  \sortlist{entry}{nyt}
    \entry{Apostol:1976}{book}{}
      \name{labelname}{1}{}{%
        {{hash=cd5aed910adad57e2e694401e26167ad}{Apostol}{A\bibinitperiod}{T.M.}{T\bibinitperiod}{}{}{}{}}%
      }
      \name{author}{1}{}{%
        {{hash=cd5aed910adad57e2e694401e26167ad}{Apostol}{A\bibinitperiod}{T.M.}{T\bibinitperiod}{}{}{}{}}%
      }
      \list{location}{1}{%
        {New York}%
      }
      \list{publisher}{1}{%
        {Springer-Verlag}%
      }
      \strng{namehash}{cd5aed910adad57e2e694401e26167ad}
      \strng{fullhash}{cd5aed910adad57e2e694401e26167ad}
      \field{sortinit}{A}
      \field{labeltitle}{Introduction to Analytic Number Theory}
      \field{title}{Introduction to Analytic Number Theory}
      \field{year}{1976}
    \endentry
    \entry{Arocha-Llano:2000:MVM}{article}{}
      \name{labelname}{2}{}{%
        {{hash=7f746e5096ad409cf59f095f68eda4d6}{Arocha}{A\bibinitperiod}{J.L.}{J\bibinitperiod}{}{}{}{}}%
        {{hash=115b56c885e7c030ae7864aea6c8b589}{Llano}{L\bibinitperiod}{B.}{B\bibinitperiod}{}{}{}{}}%
      }
      \name{author}{2}{}{%
        {{hash=7f746e5096ad409cf59f095f68eda4d6}{Arocha}{A\bibinitperiod}{J.L.}{J\bibinitperiod}{}{}{}{}}%
        {{hash=115b56c885e7c030ae7864aea6c8b589}{Llano}{L\bibinitperiod}{B.}{B\bibinitperiod}{}{}{}{}}%
      }
      \strng{namehash}{e833fde2b60845fa13bf0b8bb495be01}
      \strng{fullhash}{e833fde2b60845fa13bf0b8bb495be01}
      \field{sortinit}{A}
      \field{labeltitle}{Mean value for the matching and dominating polynomial}
      \field{journaltitle}{Discuss.\ Math.\ Graph Theory}
      \field{title}{Mean value for the matching and dominating polynomial}
      \field{volume}{20}
      \field{year}{2000}
      \field{pages}{57\bibrangedash 69}
    \endentry
    \entry{AMT:2010}{inproceedings}{}
      \name{labelname}{3}{}{%
        {{hash=42c4607dba574be755692ee75aff7e4b}{Averbouch}{A\bibinitperiod}{I.}{I\bibinitperiod}{}{}{}{}}%
        {{hash=5a8d48a4e6693b6ae0cabd6502fe69fd}{Makowsky}{M\bibinitperiod}{J.A.}{J\bibinitperiod}{}{}{}{}}%
        {{hash=3611f1b3058cb6d1d949696d819eac5a}{Tittmann}{T\bibinitperiod}{P.}{P\bibinitperiod}{}{}{}{}}%
      }
      \name{author}{3}{}{%
        {{hash=42c4607dba574be755692ee75aff7e4b}{Averbouch}{A\bibinitperiod}{I.}{I\bibinitperiod}{}{}{}{}}%
        {{hash=5a8d48a4e6693b6ae0cabd6502fe69fd}{Makowsky}{M\bibinitperiod}{J.A.}{J\bibinitperiod}{}{}{}{}}%
        {{hash=3611f1b3058cb6d1d949696d819eac5a}{Tittmann}{T\bibinitperiod}{P.}{P\bibinitperiod}{}{}{}{}}%
      }
      \name{editor}{2}{}{%
        {{hash=c97eff9e59ee4b21fa0dd6b7be8392f9}{Paul}{P\bibinitperiod}{Ch\@.}{C\bibinitperiod}{}{}{}{}}%
        {{hash=300921433eafb114244f0fb37e3f85f1}{Habib}{H\bibinitperiod}{M.}{M\bibinitperiod}{}{}{}{}}%
      }
      \list{location}{1}{%
        {Berlin}%
      }
      \list{publisher}{1}{%
        {Springer-Verlag}%
      }
      \strng{namehash}{bfd03bcf000982c5441d116774569483}
      \strng{fullhash}{bfd03bcf000982c5441d116774569483}
      \field{sortinit}{A}
      \field{labeltitle}{A graph polynomial arising from community structure}
      \field{eventday}{24}
      \field{eventendday}{26}
      \field{eventendmonth}{06}
      \field{eventendyear}{2009}
      \field{eventmonth}{06}
      \field{eventtitle}{35th Intern.\ Workshop on Graph-theoretic Concepts in Computer Science, WG 2009}
      \field{eventyear}{2009}
      \field{number}{5911}
      \field{series}{Lecture Notes in Computer Science}
      \field{title}{A graph polynomial arising from community structure}
      \field{titleaddon}{Extended abstract}
      \field{venue}{Montpellier, France}
      \field{year}{2010}
      \field{pages}{33\bibrangedash 43}
    \endentry
    \entry{Berge:1973:GH}{book}{}
      \name{labelname}{1}{}{%
        {{hash=1b10104fef6c2adfa513250966d62e20}{Berge}{B\bibinitperiod}{C.}{C\bibinitperiod}{}{}{}{}}%
      }
      \name{author}{1}{}{%
        {{hash=1b10104fef6c2adfa513250966d62e20}{Berge}{B\bibinitperiod}{C.}{C\bibinitperiod}{}{}{}{}}%
      }
      \list{location}{1}{%
        {Amsterdam}%
      }
      \list{publisher}{1}{%
        {North-Holland}%
      }
      \strng{namehash}{1b10104fef6c2adfa513250966d62e20}
      \strng{fullhash}{1b10104fef6c2adfa513250966d62e20}
      \field{sortinit}{B}
      \field{labeltitle}{Hypergraphs: The Theory of Finite Sets}
      \field{title}{Hypergraphs: The Theory of Finite Sets}
      \field{year}{1989}
    \endentry
    \entry{Birkhoff:1912:DFN}{article}{}
      \name{labelname}{1}{}{%
        {{hash=88c9cc0867222b49b497deb562a88777}{Birkhoff}{B\bibinitperiod}{G.D.}{G\bibinitperiod}{}{}{}{}}%
      }
      \name{author}{1}{}{%
        {{hash=88c9cc0867222b49b497deb562a88777}{Birkhoff}{B\bibinitperiod}{G.D.}{G\bibinitperiod}{}{}{}{}}%
      }
      \strng{namehash}{88c9cc0867222b49b497deb562a88777}
      \strng{fullhash}{88c9cc0867222b49b497deb562a88777}
      \field{sortinit}{B}
      \field{labeltitle}{A determinant formula for the number of ways of coloring a map}
      \field{journaltitle}{Ann\@. Math\@.}
      \field{title}{A determinant formula for the number of ways of coloring a map}
      \field{volume}{14}
      \field{year}{1912}
      \field{pages}{42\bibrangedash 46}
    \endentry
    \entry{BBFH:2013}{inproceedings}{}
      \name{labelname}{4}{}{%
        {{hash=f419eaab366930bbb33ef8203d873b5a}{Blanchet-Sadri}{B\bibinithyphendelim S\bibinitperiod}{F.}{F\bibinitperiod}{}{}{}{}}%
        {{hash=fd825d3481834be91b129f866a96bc98}{Bodnar}{B\bibinitperiod}{M.}{M\bibinitperiod}{}{}{}{}}%
        {{hash=8bb78af1373e03dfaa602ae86bd12171}{Fox}{F\bibinitperiod}{N.}{N\bibinitperiod}{}{}{}{}}%
        {{hash=2a6fad480cb21322f0cecb436b0fc36c}{Hidakatsu}{H\bibinitperiod}{J.}{J\bibinitperiod}{}{}{}{}}%
      }
      \name{author}{4}{}{%
        {{hash=f419eaab366930bbb33ef8203d873b5a}{Blanchet-Sadri}{B\bibinithyphendelim S\bibinitperiod}{F.}{F\bibinitperiod}{}{}{}{}}%
        {{hash=fd825d3481834be91b129f866a96bc98}{Bodnar}{B\bibinitperiod}{M.}{M\bibinitperiod}{}{}{}{}}%
        {{hash=8bb78af1373e03dfaa602ae86bd12171}{Fox}{F\bibinitperiod}{N.}{N\bibinitperiod}{}{}{}{}}%
        {{hash=2a6fad480cb21322f0cecb436b0fc36c}{Hidakatsu}{H\bibinitperiod}{J.}{J\bibinitperiod}{}{}{}{}}%
      }
      \list{location}{1}{%
        {Heidelberg}%
      }
      \list{publisher}{1}{%
        {Springer-Verlag}%
      }
      \strng{namehash}{29e675f32ffbc13076d565fe72bca8ba}
      \strng{fullhash}{248358eec437f1100413298a5bb30461}
      \field{sortinit}{B}
      \field{labeltitle}{A graph polynomial approach to primitivity}
      \field{eventday}{02}
      \field{eventendday}{05}
      \field{eventendmonth}{04}
      \field{eventendyear}{2013}
      \field{eventmonth}{04}
      \field{eventtitle}{7th International Conference on Languages and Automata Theory and Applications, LATA 2013}
      \field{eventyear}{2013}
      \field{number}{7810}
      \field{series}{Lecture Notes in Computer Science}
      \field{title}{A graph polynomial approach to primitivity}
      \field{venue}{Bilbao, Spain}
      \field{year}{2013}
      \field{pages}{153\bibrangedash 164}
    \endentry
    \entry{BS:1997}{article}{}
      \name{labelname}{2}{}{%
        {{hash=15d88a88bcc165116151910ff0f872e0}{Blass}{B\bibinitperiod}{A.}{A\bibinitperiod}{}{}{}{}}%
        {{hash=2f6b2d750bdd39d74475ea41c579f869}{Sagan}{S\bibinitperiod}{B.E.}{B\bibinitperiod}{}{}{}{}}%
      }
      \name{author}{2}{}{%
        {{hash=15d88a88bcc165116151910ff0f872e0}{Blass}{B\bibinitperiod}{A.}{A\bibinitperiod}{}{}{}{}}%
        {{hash=2f6b2d750bdd39d74475ea41c579f869}{Sagan}{S\bibinitperiod}{B.E.}{B\bibinitperiod}{}{}{}{}}%
      }
      \strng{namehash}{1874765b6782276aafccd59a99937071}
      \strng{fullhash}{1874765b6782276aafccd59a99937071}
      \field{sortinit}{B}
      \field{labeltitle}{Möbius functions of lattices}
      \field{journaltitle}{Adv\@. Math\@.}
      \field{title}{Möbius functions of lattices}
      \field{volume}{127}
      \field{year}{1997}
      \field{pages}{94\bibrangedash 123}
    \endentry
    \entry{Crapo:1967:HIM}{article}{}
      \name{labelname}{1}{}{%
        {{hash=7f0eead000f482fe7d37eebd02c6e5db}{Crapo}{C\bibinitperiod}{H.H.}{H\bibinitperiod}{}{}{}{}}%
      }
      \name{author}{1}{}{%
        {{hash=7f0eead000f482fe7d37eebd02c6e5db}{Crapo}{C\bibinitperiod}{H.H.}{H\bibinitperiod}{}{}{}{}}%
      }
      \strng{namehash}{7f0eead000f482fe7d37eebd02c6e5db}
      \strng{fullhash}{7f0eead000f482fe7d37eebd02c6e5db}
      \field{sortinit}{C}
      \field{labeltitle}{A higher invariant for matroids}
      \field{journaltitle}{J\@. Combin\@. Theory}
      \field{title}{A higher invariant for matroids}
      \field{volume}{2}
      \field{year}{1967}
      \field{pages}{406\bibrangedash 417}
    \endentry
    \entry{Diestel:2010:GT}{book}{}
      \name{labelname}{1}{}{%
        {{hash=23bb78955091db6a0d125b3e9a93afa3}{Diestel}{D\bibinitperiod}{R.}{R\bibinitperiod}{}{}{}{}}%
      }
      \name{author}{1}{}{%
        {{hash=23bb78955091db6a0d125b3e9a93afa3}{Diestel}{D\bibinitperiod}{R.}{R\bibinitperiod}{}{}{}{}}%
      }
      \list{location}{1}{%
        {New York}%
      }
      \list{publisher}{1}{%
        {Springer-Verlag}%
      }
      \strng{namehash}{23bb78955091db6a0d125b3e9a93afa3}
      \strng{fullhash}{23bb78955091db6a0d125b3e9a93afa3}
      \field{sortinit}{D}
      \field{labeltitle}{Graph Theory}
      \field{edition}{4th ed.}
      \field{title}{Graph Theory}
      \field{year}{2010}
    \endentry
    \entry{Dohmen:1995:BCT}{article}{}
      \name{labelname}{1}{}{%
        {{hash=5f1ca347246e6e762e72caf2a7c23a81}{Dohmen}{D\bibinitperiod}{K.}{K\bibinitperiod}{}{}{}{}}%
      }
      \name{author}{1}{}{%
        {{hash=5f1ca347246e6e762e72caf2a7c23a81}{Dohmen}{D\bibinitperiod}{K.}{K\bibinitperiod}{}{}{}{}}%
      }
      \strng{namehash}{5f1ca347246e6e762e72caf2a7c23a81}
      \strng{fullhash}{5f1ca347246e6e762e72caf2a7c23a81}
      \field{sortinit}{D}
      \field{labeltitle}{A Broken-Circuits-Theorem for hypergraphs}
      \field{journaltitle}{Arch\@. Math.}
      \field{number}{2}
      \field{title}{A Broken-Circuits-Theorem for hypergraphs}
      \field{volume}{64}
      \field{year}{1995}
      \field{pages}{159\bibrangedash 162}
    \endentry
    \entry{Dohmen:1999:IIE}{article}{}
      \name{labelname}{1}{}{%
        {{hash=5f1ca347246e6e762e72caf2a7c23a81}{Dohmen}{D\bibinitperiod}{K.}{K\bibinitperiod}{}{}{}{}}%
      }
      \name{author}{1}{}{%
        {{hash=5f1ca347246e6e762e72caf2a7c23a81}{Dohmen}{D\bibinitperiod}{K.}{K\bibinitperiod}{}{}{}{}}%
      }
      \strng{namehash}{5f1ca347246e6e762e72caf2a7c23a81}
      \strng{fullhash}{5f1ca347246e6e762e72caf2a7c23a81}
      \field{sortinit}{D}
      \field{labeltitle}{An improvement of the inclusion-exclusion principle}
      \field{journaltitle}{Arch\@. Math\@.}
      \field{number}{4}
      \field{title}{An improvement of the inclusion-exclusion principle}
      \field{volume}{72}
      \field{year}{1999}
      \field{pages}{298\bibrangedash 303}
    \endentry
    \entry{Dohmen:2003:NTV}{article}{}
      \name{labelname}{3}{}{%
        {{hash=5f1ca347246e6e762e72caf2a7c23a81}{Dohmen}{D\bibinitperiod}{K.}{K\bibinitperiod}{}{}{}{}}%
        {{hash=26ec319cd7bb2ee681059eff5dc60339}{Pönitz}{P\bibinitperiod}{A.}{A\bibinitperiod}{}{}{}{}}%
        {{hash=3611f1b3058cb6d1d949696d819eac5a}{Tittmann}{T\bibinitperiod}{P.}{P\bibinitperiod}{}{}{}{}}%
      }
      \name{author}{3}{}{%
        {{hash=5f1ca347246e6e762e72caf2a7c23a81}{Dohmen}{D\bibinitperiod}{K.}{K\bibinitperiod}{}{}{}{}}%
        {{hash=26ec319cd7bb2ee681059eff5dc60339}{Pönitz}{P\bibinitperiod}{A.}{A\bibinitperiod}{}{}{}{}}%
        {{hash=3611f1b3058cb6d1d949696d819eac5a}{Tittmann}{T\bibinitperiod}{P.}{P\bibinitperiod}{}{}{}{}}%
      }
      \strng{namehash}{d42813caa95e4f20e42c0a39805f9b67}
      \strng{fullhash}{d42813caa95e4f20e42c0a39805f9b67}
      \field{sortinit}{D}
      \field{labeltitle}{A new two-variable generalization of the chromatic polynomial}
      \field{journaltitle}{Discrete Math\@. Theor\@. Comput\@. Sci.}
      \field{number}{1}
      \field{title}{A new two-variable generalization of the chromatic polynomial}
      \field{volume}{6}
      \field{year}{2003}
      \field{pages}{69\bibrangedash 90}
    \endentry
    \entry{DT:2012:DR}{article}{}
      \name{labelname}{2}{}{%
        {{hash=5f1ca347246e6e762e72caf2a7c23a81}{Dohmen}{D\bibinitperiod}{K.}{K\bibinitperiod}{}{}{}{}}%
        {{hash=3611f1b3058cb6d1d949696d819eac5a}{Tittmann}{T\bibinitperiod}{P.}{P\bibinitperiod}{}{}{}{}}%
      }
      \name{author}{2}{}{%
        {{hash=5f1ca347246e6e762e72caf2a7c23a81}{Dohmen}{D\bibinitperiod}{K.}{K\bibinitperiod}{}{}{}{}}%
        {{hash=3611f1b3058cb6d1d949696d819eac5a}{Tittmann}{T\bibinitperiod}{P.}{P\bibinitperiod}{}{}{}{}}%
      }
      \strng{namehash}{2744fd8e1d02b9c95892c6ab1425e7c8}
      \strng{fullhash}{2744fd8e1d02b9c95892c6ab1425e7c8}
      \field{sortinit}{D}
      \field{labeltitle}{Domination Reliability}
      \field{journaltitle}{Electron.\ J. Combin.}
      \field{title}{Domination Reliability}
      \field{volume}{19}
      \field{year}{2012}
      \field{pages}{\#P15}
    \endentry
    \entry{DKT:2005:CPCG}{book}{}
      \name{labelname}{3}{}{%
        {{hash=431eae414e006488990aba19d7276978}{Dong}{D\bibinitperiod}{F.M.}{F\bibinitperiod}{}{}{}{}}%
        {{hash=eaed86d0aca6d3ce4b46761336506b84}{Koh}{K\bibinitperiod}{K.M.}{K\bibinitperiod}{}{}{}{}}%
        {{hash=d9ee7995568fb182196b41665f778adb}{Teo}{T\bibinitperiod}{K.L.}{K\bibinitperiod}{}{}{}{}}%
      }
      \name{author}{3}{}{%
        {{hash=431eae414e006488990aba19d7276978}{Dong}{D\bibinitperiod}{F.M.}{F\bibinitperiod}{}{}{}{}}%
        {{hash=eaed86d0aca6d3ce4b46761336506b84}{Koh}{K\bibinitperiod}{K.M.}{K\bibinitperiod}{}{}{}{}}%
        {{hash=d9ee7995568fb182196b41665f778adb}{Teo}{T\bibinitperiod}{K.L.}{K\bibinitperiod}{}{}{}{}}%
      }
      \list{location}{1}{%
        {Singapore}%
      }
      \list{publisher}{1}{%
        {World Scientific}%
      }
      \strng{namehash}{72d8fc038207a04b41d253b5e5be422b}
      \strng{fullhash}{72d8fc038207a04b41d253b5e5be422b}
      \field{sortinit}{D}
      \field{labeltitle}{Chromatic Polynomials and Chromaticity of Graphs}
      \field{title}{Chromatic Polynomials and Chromaticity of Graphs}
      \field{year}{2005}
    \endentry
    \entry{EJ:1985:TCG}{article}{}
      \name{labelname}{2}{}{%
        {{hash=184c872419d1236de1b7f8e5a4abc78f}{Edelman}{E\bibinitperiod}{P.H.}{P\bibinitperiod}{}{}{}{}}%
        {{hash=735e9f4ef0966d4aecca3caac8daaf84}{Jamison}{J\bibinitperiod}{R.}{R\bibinitperiod}{}{}{}{}}%
      }
      \name{author}{2}{}{%
        {{hash=184c872419d1236de1b7f8e5a4abc78f}{Edelman}{E\bibinitperiod}{P.H.}{P\bibinitperiod}{}{}{}{}}%
        {{hash=735e9f4ef0966d4aecca3caac8daaf84}{Jamison}{J\bibinitperiod}{R.}{R\bibinitperiod}{}{}{}{}}%
      }
      \strng{namehash}{7a78a3e534d26d388f9d76953dcb79b8}
      \strng{fullhash}{7a78a3e534d26d388f9d76953dcb79b8}
      \field{sortinit}{E}
      \field{labeltitle}{The theory of convex geometries}
      \field{journaltitle}{Geom\@. Dedicata}
      \field{title}{The theory of convex geometries}
      \field{volume}{19}
      \field{year}{1985}
      \field{pages}{247\bibrangedash 270}
    \endentry
    \entry{Glebov:2012:EHHC}{article}{}
      \name{labelname}{3}{}{%
        {{hash=c09685d3ab712c95482e6d224806fdc5}{Glebov}{G\bibinitperiod}{R.}{R\bibinitperiod}{}{}{}{}}%
        {{hash=93cc7703b63d2744e1508580fd276e81}{Person}{P\bibinitperiod}{Y.}{Y\bibinitperiod}{}{}{}{}}%
        {{hash=6b68d7a44e8f8f790e772ec8b4e78bcc}{Weps}{W\bibinitperiod}{W.}{W\bibinitperiod}{}{}{}{}}%
      }
      \name{author}{3}{}{%
        {{hash=c09685d3ab712c95482e6d224806fdc5}{Glebov}{G\bibinitperiod}{R.}{R\bibinitperiod}{}{}{}{}}%
        {{hash=93cc7703b63d2744e1508580fd276e81}{Person}{P\bibinitperiod}{Y.}{Y\bibinitperiod}{}{}{}{}}%
        {{hash=6b68d7a44e8f8f790e772ec8b4e78bcc}{Weps}{W\bibinitperiod}{W.}{W\bibinitperiod}{}{}{}{}}%
      }
      \strng{namehash}{02ff5737207b37770c3cea9387735f89}
      \strng{fullhash}{02ff5737207b37770c3cea9387735f89}
      \field{sortinit}{G}
      \field{labeltitle}{On extremal hypergraphs for hamiltonian cycles}
      \field{journaltitle}{Europ.\ J.\ Combin.}
      \field{title}{On extremal hypergraphs for hamiltonian cycles}
      \field{volume}{33}
      \field{year}{2012}
      \field{pages}{544\bibrangedash 555}
    \endentry
    \entry{Graetzer:1998:GLT}{book}{}
      \name{labelname}{1}{}{%
        {{hash=267fcdcde6a6ad82285c7b4acacffdb5}{Graetzer}{G\bibinitperiod}{G.}{G\bibinitperiod}{}{}{}{}}%
      }
      \name{author}{1}{}{%
        {{hash=267fcdcde6a6ad82285c7b4acacffdb5}{Graetzer}{G\bibinitperiod}{G.}{G\bibinitperiod}{}{}{}{}}%
      }
      \list{location}{1}{%
        {Basel}%
      }
      \list{publisher}{1}{%
        {Birkhäuser}%
      }
      \strng{namehash}{267fcdcde6a6ad82285c7b4acacffdb5}
      \strng{fullhash}{267fcdcde6a6ad82285c7b4acacffdb5}
      \field{sortinit}{G}
      \field{labeltitle}{General Lattice Theory}
      \field{edition}{Second edition}
      \field{title}{General Lattice Theory}
      \field{year}{1998}
    \endentry
    \entry{Heron:1972:MP}{incollection}{}
      \name{labelname}{1}{}{%
        {{hash=8f31eace7f0e3d592cd7e90e6170d77c}{Heron}{H\bibinitperiod}{A.P.}{A\bibinitperiod}{}{}{}{}}%
      }
      \name{author}{1}{}{%
        {{hash=8f31eace7f0e3d592cd7e90e6170d77c}{Heron}{H\bibinitperiod}{A.P.}{A\bibinitperiod}{}{}{}{}}%
      }
      \name{editor}{2}{}{%
        {{hash=1e4af97e1e9c7a981cf11e2a51d3c68b}{Welsh}{W\bibinitperiod}{D.J.A}{D\bibinitperiod}{}{}{}{}}%
        {{hash=bc231c52fec19539066de23bb3000ab9}{Woodall}{W\bibinitperiod}{D.R.}{D\bibinitperiod}{}{}{}{}}%
      }
      \list{publisher}{2}{%
        {The Institute of Combinatorics}%
        {Its Applications}%
      }
      \strng{namehash}{8f31eace7f0e3d592cd7e90e6170d77c}
      \strng{fullhash}{8f31eace7f0e3d592cd7e90e6170d77c}
      \field{sortinit}{H}
      \field{labeltitle}{Matroid polynomials}
      \field{booktitle}{Combinatorics}
      \field{title}{Matroid polynomials}
      \field{year}{1972}
    \endentry
    \entry{OEIS:2014}{online}{}
      \name{labelname}{1}{}{%
        {{hash=af8df48ed7fb00fb3f91fd716a798712}{Integer\bibnamedelima Sequences}{I\bibinitperiod\bibinitdelim S\bibinitperiod}{The\bibnamedelimb On-Line\bibnamedelima Encyclopedia}{T\bibinitperiod\bibinitdelim O\bibinithyphendelim L\bibinitperiod\bibinitdelim E\bibinitperiod}{of}{o\bibinitperiod}{}{}}%
      }
      \name{author}{1}{}{%
        {{hash=af8df48ed7fb00fb3f91fd716a798712}{Integer\bibnamedelima Sequences}{I\bibinitperiod\bibinitdelim S\bibinitperiod}{The\bibnamedelimb On-Line\bibnamedelima Encyclopedia}{T\bibinitperiod\bibinitdelim O\bibinithyphendelim L\bibinitperiod\bibinitdelim E\bibinitperiod}{of}{o\bibinitperiod}{}{}}%
      }
      \strng{namehash}{af8df48ed7fb00fb3f91fd716a798712}
      \strng{fullhash}{af8df48ed7fb00fb3f91fd716a798712}
      \field{sortinit}{I}
      \field{titleaddon}{Sequences A00010, A023900, and A034386}
      \field{urlday}{12}
      \field{urlmonth}{10}
      \field{urlyear}{2014}
      \field{url}{http://oeis.org}
    \endentry
    \entry{LH:2013:NSCP}{article}{}
      \name{labelname}{2}{}{%
        {{hash=7314f75f7e19862a1697f97920b19bf5}{Liao}{L\bibinitperiod}{Y.}{Y\bibinitperiod}{}{}{}{}}%
        {{hash=0fabc6d7a2547ec30db8b66096901f50}{Hou}{H\bibinitperiod}{Y.}{Y\bibinitperiod}{}{}{}{}}%
      }
      \name{author}{2}{}{%
        {{hash=7314f75f7e19862a1697f97920b19bf5}{Liao}{L\bibinitperiod}{Y.}{Y\bibinitperiod}{}{}{}{}}%
        {{hash=0fabc6d7a2547ec30db8b66096901f50}{Hou}{H\bibinitperiod}{Y.}{Y\bibinitperiod}{}{}{}{}}%
      }
      \strng{namehash}{32cf3c1c8bbed8a05ae5940cdaa6d8e8}
      \strng{fullhash}{32cf3c1c8bbed8a05ae5940cdaa6d8e8}
      \field{sortinit}{L}
      \field{labeltitle}{Note on the subgraph component polynomial}
      \field{journaltitle}{Electron. J. Combin.}
      \field{title}{Note on the subgraph component polynomial}
      \field{volume}{21}
      \field{year}{2014}
      \field{pages}{\#P3.27}
    \endentry
    \entry{NW:1997:AT}{article}{}
      \name{labelname}{2}{}{%
        {{hash=c444c6e699e0f90fedb6d2da788900c8}{Naiman}{N\bibinitperiod}{D.Q.}{D\bibinitperiod}{}{}{}{}}%
        {{hash=26770910f5eef4a60d1f65ca93fa8243}{Wynn}{W\bibinitperiod}{H.P.}{H\bibinitperiod}{}{}{}{}}%
      }
      \name{author}{2}{}{%
        {{hash=c444c6e699e0f90fedb6d2da788900c8}{Naiman}{N\bibinitperiod}{D.Q.}{D\bibinitperiod}{}{}{}{}}%
        {{hash=26770910f5eef4a60d1f65ca93fa8243}{Wynn}{W\bibinitperiod}{H.P.}{H\bibinitperiod}{}{}{}{}}%
      }
      \strng{namehash}{d81fc825f4bc8c328244cd39b8f2ac76}
      \strng{fullhash}{d81fc825f4bc8c328244cd39b8f2ac76}
      \field{sortinit}{N}
      \field{labeltitle}{Abstract tubes, improved inclusion-exclusion identities and inequalities and importance sampling}
      \field{journaltitle}{Ann.\ Stat.}
      \field{title}{Abstract tubes, improved inclusion-exclusion identities and inequalities and importance sampling}
      \field{volume}{25}
      \field{year}{1997}
      \field{pages}{1954\bibrangedash 1983}
    \endentry
    \entry{Nar:1974}{article}{}
      \name{labelname}{1}{}{%
        {{hash=0dbaeafc8bdb8a3ddab08d656fdfe8a7}{Narushima}{N\bibinitperiod}{H.}{H\bibinitperiod}{}{}{}{}}%
      }
      \name{author}{1}{}{%
        {{hash=0dbaeafc8bdb8a3ddab08d656fdfe8a7}{Narushima}{N\bibinitperiod}{H.}{H\bibinitperiod}{}{}{}{}}%
      }
      \strng{namehash}{0dbaeafc8bdb8a3ddab08d656fdfe8a7}
      \strng{fullhash}{0dbaeafc8bdb8a3ddab08d656fdfe8a7}
      \field{sortinit}{N}
      \field{labeltitle}{Principle of inclusion-exclusion on semilattices}
      \field{journaltitle}{J. Combin\@. Theory Ser\@. A}
      \field{title}{Principle of inclusion-exclusion on semilattices}
      \field{volume}{17}
      \field{year}{1974}
      \field{pages}{196\bibrangedash 203}
    \endentry
    \entry{Ross:2012:FCP}{book}{}
      \name{labelname}{1}{}{%
        {{hash=819d6048b765b9688493961e96ea8ccc}{Ross}{R\bibinitperiod}{S.}{S\bibinitperiod}{}{}{}{}}%
      }
      \name{author}{1}{}{%
        {{hash=819d6048b765b9688493961e96ea8ccc}{Ross}{R\bibinitperiod}{S.}{S\bibinitperiod}{}{}{}{}}%
      }
      \list{publisher}{1}{%
        {Pearson}%
      }
      \strng{namehash}{819d6048b765b9688493961e96ea8ccc}
      \strng{fullhash}{819d6048b765b9688493961e96ea8ccc}
      \field{sortinit}{R}
      \field{labeltitle}{A First Course in Probability}
      \field{edition}{9th edition}
      \field{title}{A First Course in Probability}
      \field{year}{2012}
    \endentry
    \entry{Rota:1964}{article}{}
      \name{labelname}{1}{}{%
        {{hash=5a1c7f2794d7119e68f31600477b5278}{Rota}{R\bibinitperiod}{G.-C.}{G\bibinithyphendelim C\bibinitperiod}{}{}{}{}}%
      }
      \name{author}{1}{}{%
        {{hash=5a1c7f2794d7119e68f31600477b5278}{Rota}{R\bibinitperiod}{G.-C.}{G\bibinithyphendelim C\bibinitperiod}{}{}{}{}}%
      }
      \strng{namehash}{5a1c7f2794d7119e68f31600477b5278}
      \strng{fullhash}{5a1c7f2794d7119e68f31600477b5278}
      \field{sortinit}{R}
      \field{labeltitle}{On the foundations of combinatorial theory I. Theory of Möbius functions}
      \field{journaltitle}{Z. Wahrscheinlichkeitstheorie Verw\@. Gebiete}
      \field{title}{On the foundations of combinatorial theory I. Theory of Möbius functions}
      \field{volume}{2}
      \field{year}{1964}
      \field{pages}{340\bibrangedash 368}
    \endentry
    \entry{Stanley:1972}{article}{}
      \name{labelname}{1}{}{%
        {{hash=6619a48c70c24d85196a00c3d874e441}{Stanley}{S\bibinitperiod}{R.P.}{R\bibinitperiod}{}{}{}{}}%
      }
      \name{author}{1}{}{%
        {{hash=6619a48c70c24d85196a00c3d874e441}{Stanley}{S\bibinitperiod}{R.P.}{R\bibinitperiod}{}{}{}{}}%
      }
      \strng{namehash}{6619a48c70c24d85196a00c3d874e441}
      \strng{fullhash}{6619a48c70c24d85196a00c3d874e441}
      \field{sortinit}{S}
      \field{labeltitle}{Supersolvable lattices}
      \field{journaltitle}{Alg\@. Univ\@.}
      \field{title}{Supersolvable lattices}
      \field{volume}{2}
      \field{year}{1972}
      \field{pages}{197\bibrangedash 217}
    \endentry
    \entry{Steinbach:2014}{incollection}{}
      \name{labelname}{2}{}{%
        {{hash=eccf9f787d27398be1763e944e1f192b}{Steinbach}{S\bibinitperiod}{B.}{B\bibinitperiod}{}{}{}{}}%
        {{hash=f77d9ab35617c2c344ee446abc4164d9}{Posthoff}{P\bibinitperiod}{C.}{C\bibinitperiod}{}{}{}{}}%
      }
      \name{author}{2}{}{%
        {{hash=eccf9f787d27398be1763e944e1f192b}{Steinbach}{S\bibinitperiod}{B.}{B\bibinitperiod}{}{}{}{}}%
        {{hash=f77d9ab35617c2c344ee446abc4164d9}{Posthoff}{P\bibinitperiod}{C.}{C\bibinitperiod}{}{}{}{}}%
      }
      \name{editor}{1}{}{%
        {{hash=eccf9f787d27398be1763e944e1f192b}{Steinbach}{S\bibinitperiod}{B.}{B\bibinitperiod}{}{}{}{}}%
      }
      \list{location}{1}{%
        {Newcastle}%
      }
      \list{publisher}{1}{%
        {Cambridge Scholars Publishing}%
      }
      \strng{namehash}{12159819fb1cf11bd4ad5a4e21e2460a}
      \strng{fullhash}{12159819fb1cf11bd4ad5a4e21e2460a}
      \field{sortinit}{S}
      \field{labeltitle}{Four-Colored Rectangle-free Grids}
      \field{booktitle}{Recent Progress in the Boolean Domain}
      \field{title}{Four-Colored Rectangle-free Grids}
      \field{year}{2014}
    \endentry
    \entry{TAM:2011}{article}{}
      \name{labelname}{3}{}{%
        {{hash=3611f1b3058cb6d1d949696d819eac5a}{Tittmann}{T\bibinitperiod}{P.}{P\bibinitperiod}{}{}{}{}}%
        {{hash=42c4607dba574be755692ee75aff7e4b}{Averbouch}{A\bibinitperiod}{I.}{I\bibinitperiod}{}{}{}{}}%
        {{hash=5a8d48a4e6693b6ae0cabd6502fe69fd}{Makowsky}{M\bibinitperiod}{J.A.}{J\bibinitperiod}{}{}{}{}}%
      }
      \name{author}{3}{}{%
        {{hash=3611f1b3058cb6d1d949696d819eac5a}{Tittmann}{T\bibinitperiod}{P.}{P\bibinitperiod}{}{}{}{}}%
        {{hash=42c4607dba574be755692ee75aff7e4b}{Averbouch}{A\bibinitperiod}{I.}{I\bibinitperiod}{}{}{}{}}%
        {{hash=5a8d48a4e6693b6ae0cabd6502fe69fd}{Makowsky}{M\bibinitperiod}{J.A.}{J\bibinitperiod}{}{}{}{}}%
      }
      \strng{namehash}{22552b220fe64d0650e34c9013a89d55}
      \strng{fullhash}{22552b220fe64d0650e34c9013a89d55}
      \field{sortinit}{T}
      \field{labeltitle}{The enumeration of vertex induced subgraphs with respect to the number of components}
      \field{journaltitle}{Europ\@. J\@. Combin\@.}
      \field{title}{The enumeration of vertex induced subgraphs with respect to the number of components}
      \field{volume}{32}
      \field{year}{2011}
      \field{pages}{954\bibrangedash 974}
    \endentry
    \entry{Trinks:2012:NBCT}{article}{}
      \name{labelname}{1}{}{%
        {{hash=a0df348fdf2c3ba6140f53e0a37c8a5b}{Trinks}{T\bibinitperiod}{M.}{M\bibinitperiod}{}{}{}{}}%
      }
      \name{author}{1}{}{%
        {{hash=a0df348fdf2c3ba6140f53e0a37c8a5b}{Trinks}{T\bibinitperiod}{M.}{M\bibinitperiod}{}{}{}{}}%
      }
      \strng{namehash}{a0df348fdf2c3ba6140f53e0a37c8a5b}
      \strng{fullhash}{a0df348fdf2c3ba6140f53e0a37c8a5b}
      \field{sortinit}{T}
      \field{labeltitle}{{A note on a broken-cycle theorem for hypergraphs}}
      \field{journaltitle}{Discuss\@. Math\@. Graph Theory}
      \field{title}{{A note on a broken-cycle theorem for hypergraphs}}
      \field{volume}{34}
      \field{year}{2014}
      \field{pages}{641\bibrangedash 646}
    \endentry
    \entry{Whitney:1932:LEM}{article}{}
      \name{labelname}{1}{}{%
        {{hash=d4dc8486a571bcae165e45f260d8d662}{Whitney}{W\bibinitperiod}{H.}{H\bibinitperiod}{}{}{}{}}%
      }
      \name{author}{1}{}{%
        {{hash=d4dc8486a571bcae165e45f260d8d662}{Whitney}{W\bibinitperiod}{H.}{H\bibinitperiod}{}{}{}{}}%
      }
      \strng{namehash}{d4dc8486a571bcae165e45f260d8d662}
      \strng{fullhash}{d4dc8486a571bcae165e45f260d8d662}
      \field{sortinit}{W}
      \field{labeltitle}{{A logical expansion in mathematics}}
      \field{journaltitle}{Bull\@. Amer\@. Math\@. Soc\@.}
      \field{title}{{A logical expansion in mathematics}}
      \field{volume}{38}
      \field{year}{1932}
      \field{pages}{572\bibrangedash 579}
    \endentry
  \endsortlist
\endrefsection
  \blx@bblend
  \endgroup
  \csnumgdef{blx@labelnumber@\the\c@refsection}{0}}
\makeatother
%-------------- end of contents of the biblatex bbl file ------------------

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\usepackage{enumerate} 
\usepackage{mathrsfs} 
\usepackage{xcolor}
\usepackage{amsmath,amssymb,amsthm} 
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}
\theoremstyle{remark}
\newtheorem{remark}{Remark}
\DeclareMathOperator{\lcm}{lcm}
\DeclareMathOperator{\re}{Re}
\DeclareMathOperator{\rad}{rad}

\begin{document}

\maketitle

\begin{abstract}
We establish a broad generalization of Whitney's broken circuit theorem on the
chromatic polynomial of a graph to sums of the type $\sum_{A\subseteq S} f(A)$
where $S$ is a finite set and $f$ is a mapping from the power set of $S$ to an
abelian group. We give applications to the domination polynomial and the
subgraph component polynomial of a graph, the chromatic polynomial of a
hypergraph, the characteristic polynomial and Crapo's beta invariant of a
matroid, and the principle of inclusion-exclusion.  Thus, we discover several
known and new results in a concise and unified way.  As further applications
of our main result, we derive a new generalization of the maximums-minimums
identity and of a theorem due to Blass and Sagan on the M\"obius function of a
finite lattice, which generalizes Rota's crosscut theorem.  For the classical
M\"obius function, both Euler's totient function and its Dirichlet inverse,
and the reciprocal of the Riemann zeta function we obtain new expansions
involving the greatest common divisor resp.\ least common multiple.  We
finally establish an even broader generalization of Whitney's broken circuit
theorem in the context of convex geometries (antimatroids).

\bigskip\noindent \textbf{Keywords:} 
graph polynomial; domination polynomial; beta invariant; broken circuit; Möbius function; lattice; max-min identity; totient; Dirichlet inverse; Riemann zeta function; closure system; convex geometry
\end{abstract}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}

Whitney's broken circuit theorem \cite{Whitney:1932:LEM} is one of the most
significant results on the chromatic polynomial of a graph.  We refer to
Diestel \cite{Diestel:2010:GT} for general graph terminology, and to Dong, Koh
and Teo \cite{DKT:2005:CPCG} for a comprehensive treatment of the chromatic
polynomial.  The chromatic polynomial of any finite simple graph $G=(V,E)$ can
be expressed as
\begin{gather}
\label{Birkhoff-Whitney}
P(G,x) = \sum_{A\subseteq E} (-1)^{|A|} x^{c(V,A)}, 
\end{gather}
where $c(V,A)$ denotes the number of connected components of the spanning
subgraph $(V,A)$.  The significance of the chromatic polynomial lies in the
fact that for any $x\in\mathbb{N}$ it evaluates to the number of proper
$x$-colourings of $G$, that is, the number of mappings
$f:V\rightarrow\{1,\dots,x\}$ such that $f(v)\neq f(w)$ for any edge
$\{v,w\}\in E$.  This interpretation matches the original definition due to
Birkhoff \cite{Birkhoff:1912:DFN}, whereas the expansion in
Eq.~(\ref{Birkhoff-Whitney}) goes back to Whitney \cite{Whitney:1932:LEM}.
In this paper, we adopt Eq.~(\ref{Birkhoff-Whitney}) as a definition.

In order to state Whitney's broken circuit theorem, we assume that the edge
set of $G$ is endowed with a linear ordering relation. Given a set $C$
consisting of the edges of a cycle of $G$, we refer to $C\setminus\{\max C\}$
as a \emph{broken circuit} of $G$.  Thus, a broken circuit of $G$ is obtained
from the edge set of a cycle of $G$ by removing its maximum edge.

In his prominent result, Whitney \cite{Whitney:1932:LEM} showed that the sum
in Eq.~(\ref{Birkhoff-Whitney}) can be restricted to those subsets $A$ which
do not include any broken circuit as a subset; that is,
\begin{gather}
P(G,x) = \sum_{\substack{A\subseteq E\\ \forall
  B\in\mathscr{B}:\, B\not\subseteq A}} (-1)^{|A|} x^{c(V,A)} 
\end{gather}
where $\mathscr{B}$ denotes the set of broken circuits of $G$.

As a consequence, since $c(V,A) = |V|-|A|$ whenever $(V,A)$ is cycle-free, the
coefficient of $x^{|V|-k}$ in $P(G,x)$ equals $(-1)^k$ times the number of
$k$-subsets of the edge set of $G$ which do not include any broken circuit of
$G$ as a subset ($k=0,1,2,\dots$).

The significance of Whitney's broken circuit theorem lies in the fact that it
provides a combinatorial interpretation of the coefficients of the chromatic
polynomial. It has been generalized to hypergraphs
\cite{Dohmen:1995:BCT,Trinks:2012:NBCT}, matroids\cite{Heron:1972:MP},
lattices \cite{BS:1997,Rota:1964}, generalized graph colourings
\cite{Dohmen:2003:NTV}, and sophisticated inclusion-exclusion variants
\cite{Dohmen:1999:IIE}.  In this paper, an even broader generalization is
established, from which the aforementioned generalizations derive in a concise
and unified way. Some new results are deduced as well, among them a broken
circuit theorem for the recent subgraph component polynomial
\cite{AMT:2010,TAM:2011}, a generalization of the Blass-Sagan theorem on the
M\"obius function of a finite lattice \cite{BS:1997}, and a generalization of
the well-known maximum-minimums identity \cite{Ross:2012:FCP}.

The paper is organized as follows. Section \ref{sec:main} contains the main
result along with two different proofs.  This main result generalizes
Whitney's broken circuit theorem to sums of the type $\sum_{A\subseteq S}
f(A)$ where $S$ is a finite set and $f$ is a mapping from the power set of $S$
to an abelian group.  In Section \ref{sec:applications} conclusions are
drawn for the chromatic polynomial of a hypergraph, the subgraph component
polynomial and the domination polynomial of a graph, the characteristic
polynomial and beta invariant of a matroid, the maximums-minimums-identity,
the principle of inclusion-exclusion, the M\"obius function of a lattice, the
classical M\"obius function, Euler's totient function and its Dirichlet
inverse, and the reciprocal of the Riemann zeta function.  In Section
\ref{sec:furth-gener} our main result is even further generalized to convex
geometries (a concept equivalent to antimatroids).  Roughly speaking, this
generalization states that, if its requirements are fulfilled, the sum
$\sum_{A\subseteq S} f(S)$ can be restricted to the free sets of a convex
geometry on $S$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Main result}
\label{sec:main}

Our main result, which is stated below, specializes to Whitney's broken
circuit theorem for any finite simple graph $G$ by letting $S$ be the edge set
of $G$, $\mathscr{C}$ the set of all edge sets of cycles of $G$,
$\Gamma=\mathbb{Z}[x]$ with the usual addition of polynomials, $f:2^S
\rightarrow \Gamma$ defined by $f(A) = (-1)^{|A|} x^{c(V,A)}$ for any
$A\subseteq S$, and $\mathscr{B} = \{ C\setminus\{\max C\} \mathrel|
C\in\mathscr{C}\}$.

% Main result
\begin{theorem}
\label{thm:1}
Let $S$ be a finite linearly ordered set, $\mathscr{C}\subseteq
2^S\setminus\{\emptyset\}$, $\Gamma$ an abelian group (additively written),
and $f:2^S\rightarrow \Gamma$ a mapping such that for any $C\in\mathscr{C}$
and $A\supseteq C$,
\begin{gather}
\label{Bedingung}
 f(A) + f(A\setminus \{\max C\}) = 0 \, .
\end{gather}
Then, for any $\mathscr{B}\subseteq \{ C\setminus\{\max C\} \mathrel|
C\in\mathscr{C} \}$,
\begin{gather}
\label{claim}
 \sum_{A \subseteq S} f(A) \,\, = \!\! \sum_{\substack{A\subseteq S \\ \forall
  B\in\mathscr{B}:\, B\not\subseteq A}} f(A) \, .
\end{gather} 
\end{theorem}

Subsequently, we give two proofs of Theorem \ref{thm:1}. The first proof makes
use of the principle of inclusion-exclusion, while the second proof is by
induction on $|\mathscr{B}|$.

% First proof
\begin{proof}[First Proof]
If $\emptyset\in\mathscr{B}$, then 
$C=\{c\}$ for some $C\in\mathscr{C}$ and $c\in S$, and hence,
by the requirement of the theorem,
$f(A) + f(A\setminus\{c\}) = 0$ for any $A\supseteq\{c\}$.
It follows that
\begin{gather*}
 \sum_{A\subseteq S} f(A) 
= \sum_{\substack{A\subseteq S\\ A\ni c}} f(A) + \sum_{\substack{A\subseteq
    S\\ A\not\ni c}} f(A)
= \sum_{\substack{A\subseteq S\\ A\ni c}} \left( f(A) + f(A\setminus\{c\})
\right) = 0 \, ,
\end{gather*}
which implies the validity of Eq.~(\ref{claim}) since no set $A$ satisfies
$\emptyset\not\subseteq A$.
\par
In the sequel, we assume that $\emptyset\notin \mathscr{B}$.  By the principle
of inclusion-exclusion,
\begin{align}
\sum_{\substack{A\subseteq S\\ \forall B\in\mathscr{B}:\,B\not\subseteq A}}\! f(A) 
& = \sum_{\mathscr{A}\subseteq\mathscr{B}} (-1)^{|\mathscr{A}|}
\sum_{\substack{A\subseteq S\\ A\supseteq\bigcup\mathscr{A}}} f(A) \notag \\
& = \sum_{A\subseteq S} f(A) + \bigg[
\sum_{\substack{\mathscr{A}\subseteq\mathscr{B} \\
    \mathscr{A}\neq\emptyset}} (-1)^{|\mathscr{A}|} \sum_{\substack{A\subseteq
S\\ A\supseteq \bigcup\mathscr{A}}} f(A) \bigg] \, . 
\label{bracketed}
\end{align} 
\newcommand{\X}{\bigcup \mathscr{A}} 
It remains to show that the bracketed term in Eq.~(\ref{bracketed}) 
vanishes, which is the case if
\begin{gather}
\label{Behauptung}
\sum_{A\supseteq \X}
f(A)=0 \qquad (\emptyset\neq \mathscr{A}\subseteq\mathscr{B}) .
\end{gather}
In order to establish Eq.~(\ref{Behauptung}), choose
%
(i) $B\in\mathscr{A}$ with $\max B = \max \X$, and 
%
(ii) $b\notin B$ such that $B\cup \{b\} \in \mathscr{C}$ and $b> \max B$.  
%
Then, $b\notin \X$ since otherwise $b\le \max \X = \max B$.  Hence,
\begin{gather}
\label{eq1}
 \sum_{A\supseteq \X} f(A) = \sum_{\substack{A\supseteq \X\\ A\ni b}} f(A) \,+ \sum_{\substack{A\supseteq \X\\
  A\not\ni b}} f(A) = \sum_{\substack{A\supseteq \X\\ A\not\ni b}} \left(
f(A\cup\{b\}) + f(A) \right) .
\end{gather}
For each $A$ in the last sum consider $A'=A\cup\{b\}$.  Since $A\supseteq
\X\supseteq B$ we have $A'\supseteq C$ for $C=B\cup\{b\}$ and hence, by the
requirement of the theorem,
\begin{gather}
\label{eq2}
 f(A\cup\{b\}) + f(A) = f(A') + f(A'\setminus\{ \max C\} ) = 0 \, .
\end{gather}
Now Eqs.~(\ref{eq1}) and (\ref{eq2}) imply Eq.~(\ref{Behauptung}), and hence
the statement of the theorem.
\end{proof}

% Second proof
\begin{proof}[Second Proof]
The statement is obvious if $\mathscr{B}=\emptyset$.  We proceed by induction
on $|\mathscr{B}|$.  If $\mathscr{B}\neq\emptyset$, then for some
$C\in \mathscr{C}$, $C\setminus \{\max C\}\in \mathscr{B}$.  Among those $C$
choose one whose $\max C$ value is maximal.  Let
$\mathscr{B}':=\mathscr{B}\setminus \{C\setminus \{\max C\} \}$.  By the
induction hypothesis,
\begin{gather*}
 \sum_{A \subseteq S} f(A) \,\, = \!\! \sum_{\substack{A\subseteq S \\ \forall
  B\in\mathscr{B}':\, B\not\subseteq A}} f(A) \, ,
\end{gather*} 
which implies
\begin{gather}
\label{afterinduction}
 \sum_{A \subseteq S} f(A) \,\, = \!\! \sum_{\substack{A\subseteq S \\ \forall
  B\in\mathscr{B}:\, B\not\subseteq A}} f(A) \,+
 \sum_{\substack{A\subseteq S \\ \forall
  B\in\mathscr{B}':\, B\not\subseteq A\\ C\setminus\{\max C\}\subseteq A}} f(A).
\end{gather}
We claim that the second sum on the right-hand side 
of Eq.~(\ref{afterinduction}) vanishes.
Let
\begin{gather*}
\mathscr{A} := \left\{ A \mathrel| A\subseteq S; \,\,\forall B\in\mathscr{B}': B\not\subseteq A; \,\,C\setminus\{\max C\} \subseteq A \right\} . %|
\end{gather*}
By Eq.~(\ref{Bedingung}) our claim is proved if $A\in\mathscr{A}$ if and only
if $A\setminus\{\max C\}\in\mathscr{A}$.  The only non-trivial issue is to
show that if $A\setminus\{\max C\}\in\mathscr{A}$, then $B\not\subseteq A$ for
any $B\in\mathscr{B}'$.  Assume that $B\subseteq A$ for some
$B\in\mathscr{B}'$.  By the requirement of the theorem there exists
$C'\in\mathscr{C}$ such that $B=C'\setminus\{\max C'\}$.  If $\max C \in B$,
then $\max C \le \max B < \max C'$, contradicting the maximality of $\max C$.
If $\max C\notin B$, then since $A\supseteq B$ we conclude that $A\setminus
\{\max C\}\supseteq B$, which is in contradiction with $A\setminus\{\max C\}
\in\mathscr{A}$.
\end{proof}

\begin{remark}
\label{thm:remark}
Let $S$ be a finite poset, $\mathscr{C} = \{\{s,t\} \subseteq S\mathrel|
s<t\}$, and $f$  a mapping satisfying the requirement in
Eq.~\eqref{Bedingung} with respect to some linear extension of $S$.  By
Theorem \ref{thm:1},
\begin{gather}
\label{eq:10}
\sum_{A\subseteq S} f(A) = \sum_{A\subseteq S_{\max}} f(A) 
\end{gather}
where $S_{\max}$ denotes the set of maximal elements in $S$.
\end{remark}

\begin{remark}
If $S$ is an upper semilattice, we may choose $\mathscr{C}=\{\{s,t,s\vee
t\}\mathrel| s||t\}$, where $s||t$ signifies that $s$ and $t$ are incomparable
and $s\vee t$ denotes the least upper bound of $s$ and $t$ in $S$. Thus,
for any mapping $f$ satisfying the requirement in Eq.~\eqref{Bedingung}
we have
\begin{gather}
\label{eq:11}
\sum_{A\subseteq S} f(A) = \sum_{\substack{A\subseteq S\\ \text{$A$
      chain}}} f(A) .
\end{gather}
\end{remark}

We will make use of the preceding two identities in Subsection
\ref{sec:arithmetic-functions}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Applications}
\label{sec:applications}

\subsection{Chromatic polynomial of a hypergraph}

A \emph{hypergraph} is a pair $H=(V,\mathscr{E})$ where $V$ is a set (of
\emph{vertices}) and $\mathscr{E}$ is a set of non-empty subsets of $V$
(called \emph{edges}).  $H$ is called \emph{finite} if $V$ is finite, and
\emph{simple} if $|E|\ge 2$ for any $E\in\mathscr{E}$.  Distinct vertices
$v,w\in V$ such that $v,w\in E$ for some $E\in\mathscr{E}$ are called
\emph{adjacent}. The reflexive and transitive closure of the adjacency
relation yields an equivalence relation on $V$, whose equivalence classes are
referred to as \emph{connected components} of $H$, and whose number of
equivalence classes is denoted by $c(H)$.

By applying the principle of inclusion-exclusion it follows that for any finite
simple hypergraph $H$ and any $x\in\mathbb{N}$ the polynomial
\begin{gather*}
P(H,x) = \sum_{A\subseteq \mathscr{E}} (-1)^{|A|} x^{c(V,A)}
\end{gather*}
evaluates to the number of mappings $f:V\rightarrow\{1,\dots,x\}$ such that
$f|_E$ (the restriction of $f$ to $E$) is non-constant for any $E\in
\mathscr{E}$ (see \cite{Dohmen:1995:BCT} for details).  

We consider cycles in hypergraphs in the classical sense of C. Berge
\cite{Berge:1973:GH}.  Accordingly, a \emph{cycle of length $l$} in a
hypergraph $H$ is any finite sequence
$(v_1,E_1,v_2,E_2,\dots,v_l,E_l,v_{l+1})$ consisting of at least two pairwise
distinct vertices $v_1,\dots,v_l\in V$ resp.\ edges $E_1,\dots,E_l\in
\mathscr{E}$ where $v_1 = v_{l+1}$ and $v_i,v_{i+1}\in E_i$ for
$i=1,\dots,l$. The definition of a broken circuit is similar as for graphs:
Given a linear ordering relation on $\mathscr{E}$, for any set $C$ consisting
of the edges of a cycle of $H$ we refer to $C\setminus\{\max C\}$ as a
\emph{broken circuit} of~$H$.

Let $H=(V,\mathscr{E})$ be a finite simple hypergraph whose edge set is
endowed with a linear ordering relation.  In order to apply Theorem
\ref{thm:1} we choose $S=\mathscr{E}$, $\mathscr{C}$ as a set of edge sets of
cycles of $H$, $\Gamma=\mathbb{Z}[x]$ with the usual addition of polynomials,
$f(A) = (-1)^{|A|} x^{c(V,A)}$ for any subsets $A\subseteq S$, and $\mathscr{B}
\subseteq \{C\setminus\{\max C\} \mathrel| C\in\mathscr{C} \} $.  This gives
\begin{gather}
\label{eq:7}
P(H,x) = \sum_{\substack{A\subseteq \mathscr{E}\\ \forall
  B\in\mathscr{B}:\, B\not\subseteq A}} (-1)^{|A|} x^{c(V,A)} 
\end{gather}
provided, of course, that the requirement in Eq.~(\ref{Bedingung}) is
satisfied for any $C\in\mathscr{C}$ and any $A\supseteq C$.  This can be
guaranteed by imposing one of the following requirements on $\mathscr{C}$:
\begin{enumerate}
\item[(a)] All cycles belonging to $\mathscr{C}$ have the property that
each edge of the cycle is included by the union of the other edges of that
cycle. 
\item[(b)] All cycles belonging to $\mathscr{C}$ contain an edge of
cardinality 2, and these edges constitute an upset of the edge
set with respect to the given linear ordering relation.
\end{enumerate}
When applied to (a), Theorem \ref{thm:1} from Section \ref{sec:main} provides
us with a new proof of \cite[Theorem 8]{Trinks:2012:NBCT}.  When applied to
(b), it leads to a new proof of \cite[Theorem 2]{Dohmen:1995:BCT}.

The requirement in (a) is satisfied if $\mathscr{C}$ arises from cycles in $H$
having the property that each edge on the cycle is included by the union of
its two neighbouring edges.  This latter condition holds, e.g., for
\emph{$l$-tight} cycles in $r$-uniform hypergraphs where $l\ge r/2$; these are
cycles ``whose vertices can be cyclically ordered in such a way that the edges
are segments of this ordering and every two consecutive edges intersect in
exactly $l$ vertices'' \cite{Glebov:2012:EHHC}.  Recall that a hypergraph is
referred to as \emph{$r$-uniform} if each edge contains exactly $r$
vertices. An $(r-1)$-tight cycle in an $r$-uniform hypergraph is called
\emph{tight}. Thus, choosing $\mathscr{C}$ from the tight cycles of an
$r$-uniform hypergraph satisfies (a).

As a more concrete example for (a), consider the 4-uniform hypergraph
$H=(V,\mathscr{E})$ on the set of lattice points of a finite rectangular grid
where the edges of $H$ are any four points determining a rectangle. Let
$\mathscr{C}$ be the set of all 3-sets of edges arising from the 2-tight
cycles of length three in $H$.  Since any 2-tight cycle of length three
corresponds to a pair of neighbouring rectangles (that is, rectangles having
two points in common, thus determining another, geometrically larger
rectangle) we can order the edges of $H$ in such a way that edges
corresponding to geometrically larger rectangles occur later in the ordering.
In this way, the sum in Eq.~\eqref{eq:7} can be restricted to those subsets
$A$ of $\mathscr{E}$ that contain no neighbouring rectangles.  Rectangle-free
grid colorings are a topic of active research; see e.g., \cite{Steinbach:2014}
for recent results.

\subsection{Subgraph component polynomial}
\label{sec:subgr-comp-polyn}

Introduced by Averbouch, Makowsky, and Tittmann \cite{AMT:2010,TAM:2011}, the
\emph{subgraph component polynomial} of any finite graph $G=(V,E)$ is defined
by
\begin{gather*} 
Q(G,x,y) = \sum_{A\subseteq V} x^{|A|} y^{c(G[A])}.
\end{gather*}
This polynomial has seen applications in social network analysis
\cite{AMT:2010} and formal language theory \cite{BBFH:2013}.  For some recent
results on $Q(G,x,y)$, the reader is referred to \cite{LH:2013:NSCP}.

In the following, our considerations are restricted to the particular case
where $x=-1$.  We refer to $G$ as \emph{cyclically claw-free} if no centre of
a claw is located on a cycle.  Evidently, any claw-free or cycle-free graph is
cyclically claw-free.

The key observation is that if $G$ is cyclically claw-free, then $c(G[A]) =
c(G[A\setminus \{c\}])$ for any $A\subseteq V$ and any vertex $c$ on a cycle
$C\subseteq A$ (where, in this subsection, we consider cycles as subsets of
the vertex set). This leads to a vertex analogue of the notion of a broken
circuit: Given a linear ordering relation on $V$, for any cycle $C\subseteq V$
we refer to $C\setminus \{\max C\}$ as a \emph{broken circuit} of $G$. Similar
to Eq.~\eqref{eq:7} we obtain by Theorem \ref{thm:1},
\begin{gather}
\label{eq:5}
Q(G,-1,y) = \sum_{\substack{A\subseteq V\\ \forall B\in\mathscr{B}: B\not\subseteq A}}
(-1)^{|A|} y^{c(G[A])}
\end{gather}
for any cyclically claw-free finite graph $G$ and any set
$\mathscr{B}\subseteq 2^V$ of broken circuits of $G$.  Note that if we choose
$\mathscr{B}$ as the set of \emph{all} broken circuits of $G$, then any subset
$A$ of $V$ in the preceding sum is cycle-free, and hence satisfies $c(G[A]) =
|A| - m(G[A])$. Thus, we obtain
\begin{gather}
\label{eq:6}
Q(G,-1,y) = \sum_{A} (-1)^{|A|} y^{|A|-m(G[A])}
\end{gather}
where the sum extends over all subsets $A$ of $V$ not including any broken
circuit. As a consequence, $Q(G,-1,-1)$ is the number of broken-circuit-free
vertex-induced subgraphs having an even number of edges minus those having an
odd number of edges.

We finally remark that Eqs.~\eqref{eq:5} and \eqref{eq:6} hold with $x$ in
place of $-1$ if $Q(G,x,y)$ is considered as a polynomial over some
commutative ring where $(x+1)y=0$.

\subsection{Domination polynomial}

The domination polynomial of any finite simple graph $G=(V,E)$, introduced by
Arocha and Llano \cite{Arocha-Llano:2000:MVM}, is the generating function
\begin{gather*}
D(G,x) := \sum_{k=0}^{|V|} d_k(G) x^k 
\end{gather*}
where $d_k(G)$ is the number of $k$-subsets $A$ of $V$ satisfying
$N_G[A]=V$. Here, $N_G[A]$ denotes the closed neighbourhood of $A$ in $G$,
that is, the union of $A$ and its set of neighbours in $G$.  For convenience,
we write $N_G[v]$ in place of $N_G[\{v\}]$ for any $v\in V$.

Given a linear ordering relation on the vertex set of $G$, for any $v\in
V$ we refer to $N_G[v]\setminus \{v\}$ as a \emph{broken neighbourhood} of $G$
if $ v = \max N_G[v]$.  In \cite{DT:2012:DR} it is shown that
\begin{gather}
\label{bnh}
 D(G,x) = \sum_{A\subseteq V} (-1)^{|A|} (x+1)^{|V|-|N_G[A]|} ,
\end{gather}
and moreover, \emph{if $G$ does not have isolated vertices, then this sum can be
  restricted to those subsets $A$ of $V$ which do not include any broken
  neighbourhoods from an arbitrary set of broken neighbourhoods of $G$.}
\par
This latter statement easily derives from our main result in Section
\ref{sec:main} and Eq.~(\ref{bnh}) by considering the mapping $f(A) =
(-1)^{|A|} (x+1)^{|V|-|N_G[A]|}$ for any $A\subseteq V$ and letting
$\mathscr{C}$ be the set of all closed neighbourhoods $N_G[v]$ where $v=\max
N_G[v]$.  The requirement in Eq.~(\ref{Bedingung}) is satisfied since
$N_G[A\setminus\{v\}] = N_G[A]$ for any $v\in V$ and any $A\supseteq N_G[v]$.

As noted in \cite{DT:2012:DR}, if $G$ does not have isolated vertices or
isolated edges, and its vertex set is linearly ordered such that the vertices
of degree 1 constitute an upset, then each pendant edge $\{v,w\}$ where $v$ is
of degree 1 gives rise to a broken neighbourhood $\{w\}$.  In this case, the
sum in Eq.~(\ref{bnh}) can be restricted to those subsets $A$ of $V$ which do
not contain any vertex from a set of vertices which are adjacent to a vertex
of degree 1.

\subsection{Characteristic polynomial and beta invariant}

Similar conclusions as for graph and hypergraph polynomials can be drawn for
the characteristic polynomial \cite{Heron:1972:MP} and the beta invariant
\cite{Crapo:1967:HIM} of a matroid.

Recall that a \emph{matroid} is a pair $M=(E,r)$ consisting of a finite set
$E$ and a $\mathbb{Z}$-valued function $r$ on $2^E$ such that
for any $A,B\subseteq E$, 
\begin{enumerate}[(i)]
\item $0\le r(A) \le |A|$, 
\item $A\subseteq B \Rightarrow r(A) \le r(B)$, 
\item $r(A\cup B) + r(A\cap B) \le r(A) + r(B)$.  
\end{enumerate}
A \emph{circuit} of $M$ is a non-empty subset $C\subseteq E$ such that
$r(C\setminus\{c\}) = |C|-1=r(C)$ for any $c\in C$.  Given a linear ordering
relation on $E$, for any circuit $C$ of $M$ we refer to $C\setminus\{\max C\}$
as a \emph{broken circuit} of~$M$.

The characteristic polynomial $\chi(M,x)$ and the beta invariant
$\beta(M)$ of a matroid $M=(E,r)$ are defined by
\begin{gather}
\chi(M,x) = \sum_{A\subseteq E} (-1)^{|A|} x^{r(E)-r(A)} \,
, \label{firstsum} \\
\beta(M) = (-1)^{r(E)} \sum_{A\subseteq E} (-1)^{|A|} r(A) \, . \label{secondsum}
\end{gather}
In order to apply Theorem \ref{thm:1}, let $f_1:2^E\rightarrow \mathbb{Z}[x]$
be defined by $f_1(A) = (-1)^{|A|} x^{r(E)-r(A)}$, and $f_2:2^E\rightarrow
\mathbb{Z}$ by $f_2(A) = (-1)^{|A|} r(A)$. Let $\mathscr{C}$ denote the set of
all circuits of $M$.  Then, for any $C\in\mathscr{C}$ and any $A\supseteq C$,
$r(A\setminus \{\max C\}) = r(A)$; hence, both $f_1$ and $f_2$ satisfy the
requirement in Eq.~(\ref{Bedingung}).  Let $\mathscr{B}$ denote the set of
broken circuits of $M$.  Then, by Theorem \ref{thm:1}, the sums in
Eqs.~(\ref{firstsum}) and (\ref{secondsum}) can be restricted to those subsets
$A$ of $E$ not including any $B\in\mathscr{B}$ as a subset.  No such $A$ may
include a circuit, since otherwise it would include the broken circuit derived
from it. Therefore, $r(A)=|A|$ and hence,
\begin{gather}
\chi (M,x) = \sum_{\substack{A\subseteq E\\ \forall
    B\in\mathscr{B}: B\not\subseteq A}} (-1)^{|A|} x^{r(E)-r(A)} 
                 \,=\,\sum_{k=0}^{|E|} (-1)^k b_k(M) x^{r(E)-k} \, , \label{Heron} \\
\beta (M)  = (-1)^{r(E)} \!\! \sum_{\substack{A\subseteq E\\ \forall
    B\in\mathscr{B}: B\not\subseteq A}} \!\! (-1)^{|A|} r(A) \,=\, (-1)^{r(E)} \sum_{k=1}^{|E|} (-1)^k k \, b_k(M) \label{NotHeron}
\end{gather}
where $b_k(M)$ denotes the number of $k$-subsets of $E$ including no broken
circuit.

Eq.~(\ref{NotHeron}) can alternatively be deduced from Eq.~(\ref{Heron}),
which is due to Heron \cite{Heron:1972:MP}, by considering the derivative of
$\chi(M,x)$ at $x=1$.


\subsection{Maximum-minimums identity}

Let $\Gamma$ be an abelian group, endowed with a linear ordering relation,
$(x_s|s\in S)$ a finite family of elements from $\Gamma$, $k\in\mathbb{N}$,
and $f:2^S\rightarrow \Gamma$ defined by
\begin{gather*}
 f(A) = \begin{cases} (-1)^{|A|-k} \min_k (x_a|a\in A) \, , & \text{if $|A|\ge k$},\\
                        0\, ,                 & \text{if $|A|<k$},
          \end{cases} 
\end{gather*}
where $\min_k (x_a|a\in A)$ denotes the $k$-th smallest element in $(x_a|a\in
A)$ for any $A\subseteq S$ satisfying $|A|\ge k$.

In order to define $\mathscr{B}$ and $\mathscr{C}$, choose some linear
ordering relation on $S$ such that $s<t$ implies $x_s\le x_t$ for any $s,t\in
S$.  Now, define $\mathscr{B} = \{ C\setminus \{\max C\} \mathrel|
C\in\mathscr{C} \}$ where $\mathscr{C}$ is the set of all ($k+1$)-subsets of
$S$. Evidently, for any $C\in\mathscr{C}$ and any $A\supseteq C$,
\begin{gather*}
\min\nolimits_k (x_a|a\in A\setminus\{\max C\}) = \min\nolimits_k (x_a|a\in
A) .
\end{gather*}
Hence, the requirements of Theorem \ref{thm:1} are satisfied, which gives
\begin{gather}
\label{eq:8}
 \sum_{\substack{A\subseteq S\\ |A|\ge k}} (-1)^{|A|-k} \min\nolimits_k
 (x_a|a\in A)  
= \! \sum_{\substack{A\subseteq S\\ |A|\ge k \\ \forall B\in\mathscr{B}: \,
    B\not\subseteq A}} \!  (-1)^{|A|-k} \min\nolimits_k (x_a|a\in A)   \, .
\end{gather}
Since $\mathscr{B}$ consists of all $k$-subsets of $S\setminus\{\max S\}$, the
last two conditions under the second sum in Eq.~\eqref{eq:8} are equivalent to
$|A|=k$ and $\max S\in A$.  Since there are $\binom{|S|-1}{k-1}$ many such
$A$, and each of them satisfies $\min_k (x_a|a\in A) = \max (x_s | s\in S)$,
we find that
\begin{gather}
\label{eq:9}
 \sum_{\substack{A\subseteq S\\ |A|\ge k}} (-1)^{|A|-k} \min\nolimits_k
 (x_a|a\in A)
= \binom{|S|-1}{k-1} \max (x_s|s\in S).
\end{gather}
Note that neither side of this identity depends on the ordering of $S$.  For
$k=1$ this identity is known as the \emph{maximum-minimums identity}; see
\cite{Ross:2012:FCP} for a probabilistic proof (in case that the $x_s$'s are
reals) and an application to the coupon collector problem.


\subsection{Principle of inclusion-exclusion}

Let $\{M_s\}_{s\in S}$ be a finite family of finite sets, where $S$ is
linearly ordered, $\mathscr{B}$ a set of non-empty subsets of $S$ such that
for any $B\in\mathscr{B}$, $\bigcap_{b\in B} M_b \subseteq M_c$ for some $c =
c(B) > \max B$.  In \cite{Dohmen:1999:IIE} it is shown that
\begin{gather}
\label{eq:4}
\left| \bigcup_{s\in S} M_s \right| \,=\, \sum_{\substack{\emptyset \neq A
    \subseteq S \\ \forall B\in\mathscr{B}: \,B\not\subseteq A}}
(-1)^{|A|-1} \left| \bigcap_{a\in A} M_a \right|. 
\end{gather}
Under the above assumptions, this identity (which has applications to network
and system reliability) follows from Theorem \ref{thm:1} by defining 
$\mathscr{C} = \{ B\cup c(B) \mathrel| B\in \mathscr{B}\}$
and 
\begin{gather*}
f(A) =
\begin{cases}
(-1)^{|A|-1} \left| \bigcap_{a\in A} M_a\right| , & \text{if
  $A\neq\emptyset$},\\
  0\, , & \text{if $A=\emptyset$},
\end{cases}
\end{gather*}
and applying the principle of inclusion-exclusion to the sets $M_s$,
$s\in S$.

A particular case of Eq.~\eqref{eq:4} is Narushima's principle of
inclusion-exclusion \cite{Nar:1974} where the sum extends over all chains of
a semilattice:
\begin{gather}
\label{eq:22}
\left| \bigcup_{s\in S} M_s \right| \,=\, \sum_{\substack{\emptyset \neq A
    \subseteq S \\ \text{$A$ chain}}}
(-1)^{|A|-1} \left| \bigcap_{a\in A} M_a \right|
\end{gather}
As a prerequisite, $(S,\vee)$ is required to be a finite upper semilattice
satisfying $M_s \cap M_t \subseteq M_{s\vee t}$ for any $s,t\in S$.  This
particular case of Eq.~\eqref{eq:4} may also be deduced from
Eq.~\eqref{eq:11}.

 
\subsection{M\"obius function of a lattice}
\label{sec:mobi-funct-latt}

Our next application concerns the M\"obius function of a finite lattice.  For
notions from the theory of partially ordered sets and lattices, we refer to
the textbook of Graetzer~\cite{Graetzer:1998:GLT}.

Recall that the \emph{M\"obius function} of any finite lattice $L = [\hat{0},
\hat{1}]$ is the unique $\mathbb{Z}$-valued function $\mu_L : L \rightarrow
\mathbb{Z}$ such that for any $x\in L$,
\begin{gather*}
\sum_{y\le x} \mu_L(y) = \delta_{\hat{0}x}
\end{gather*}
 where $\delta$ denotes the
Kronecker delta.  Following Rota \cite{Rota:1964}, we write $\mu(L)$ instead
of $\mu_L(\hat{1})$ and introduce the notion of a \emph{crosscut}, which is
any antichain $C\subseteq L\setminus \{\hat{0}, \hat{1}\}$ having a non-empty
intersection with any maximal chain from $\hat{0}$ to $\hat{1}$ in $L$.  As a
prerequisite, $L$ must be non-trivial, that is, $L\setminus \{\hat{0},
\hat{1}\}\neq\emptyset$.  Rota's crosscut theorem \cite{Rota:1964} states that for any
non-trivial finite lattice $L=[\hat{0},\hat{1}]$ and any crosscut $C$ of $L$,
\begin{gather}
\label{crosscut}
\mu(L) = \sum_{\substack{A\subseteq C\\ \bigwedge\! A=\hat{0}, \bigvee
    \! A=\hat{1}}} (-1)^{|A|}
\end{gather}
where $\bigwedge\emptyset = \hat{1}$ and $\bigvee \emptyset = \hat{0}$.
Due to Blass and Sagan \cite{BS:1997}, for $C=A(L)$, which is the crosscut of
all atoms of $L$, this sum can be written as%
\footnote{For $C=A(L)$ the conditions $\bigwedge A=\hat{0}$ in Eq.~(\ref{nbb})
and $\bigwedge B < c$ in Eq.~(\ref{condb}) can be omitted.}
\begin{gather}
\label{nbb}
\mu(L) = \sum_{\substack{A\subseteq C\\ \bigwedge\! A=\hat{0}, \bigvee
    \! A=\hat{1} \\ \forall B\in\mathscr{B}: \,B\not\subseteq A}} (-1)^{|A|}
\end{gather}
where, according to some fixed partial ordering relation $\trianglelefteq$ on
$C$, $\mathscr{B}$ consists of all non-empty subsets $B$ of $C$ such
that for any $b\in B$ there is some $c=c(B,b)\in C$ satisfying
\begin{gather}
\label{condb}
c \vartriangleleft b 
\quad \text{and}\quad
\bigwedge\! B < c < \bigvee\! B .
\end{gather}
Here and subsequently, $<$, $\wedge$ and $\vee$ are associated with the
lattice ordering $\le$ in $L$, while $\triangleleft$ is associated with the
additional partial ordering relation $\trianglelefteq$ on $C$. 

Blass and Sagan \cite{BS:1997} used their result in computing and
combinatorially explaining the M\"obius function of various lattices and in
generalizing Stanley's well-known theorem \cite{Stanley:1972} that the
characteristic polynomial of a semimodular supersolvable lattice factors over
the integers.  As noted by Blass and Sagan \cite{BS:1997}, for $C=A(L)$
Eq.~(\ref{nbb}) generalizes Eq.~(\ref{crosscut}), which is easily seen by
considering the total incomparability $\trianglelefteq$ order on $C$.
% In fact, Blass and Sagan
% \cite{BS:1997} did not employ Rota's crosscut theorem \cite{Rota:1964} in the
% proof of their result.

We now prove that Eq.~(\ref{nbb}) holds for \emph{any} crosscut $C$ of~$L$ by
applying our main result from Section \ref{sec:main} in dual form to the sum
in Eq.~(\ref{crosscut}).  Thus, we consider $f:2^C \rightarrow \mathbb{Z}$
where
\begin{align*}
f(A) & := \begin{cases} (-1)^{|A|} & \text{if $\bigwedge \! A = \hat{0}$ and
  $\bigvee \! A = \hat{1}$},\\
                        0 & \text{otherwise},
          \end{cases} 
\end{align*}
for any $A\subseteq C$.
According to some arbitrary linear extension of $\trianglelefteq$ on $C$ define
\begin{gather*}
 \mathscr{C} := \Big\{B\cup \big\{\!\min_{b\in B} c(B,b)\big\} \,\Big|\,
B\in\mathscr{B}\Big\}\, , 
\end{gather*}
which implies $\mathscr{B} = \{C^\prime\setminus \{\min C^\prime\}\mathrel|
C^\prime\in\mathscr{C}\}$.
It remains to check that for any
$C^\prime\in\mathscr{C}$ and any $A\supseteq C^\prime$ the requirement in
Eq.~(\ref{Bedingung}) holds.
To this end, we show that 
\begin{align}
\label{requirement}
\bigwedge A \,=\, \bigwedge \big( A\setminus \{\min C^\prime\} \big),
\quad 
\bigvee \! A \,=\, \bigvee \big( A\setminus \{\min C^\prime\} \big).
\end{align}
For the first identity in (\ref{requirement}), choose $B\in\mathscr{B}$ such
that $C^\prime = B \cup \{ \min_{b\in B} c(B,b) \}$. Then,
\begin{align*}
\bigwedge\! A & = \bigwedge (A\setminus C^\prime) \wedge \bigwedge C^\prime
\qquad \text{\textcolor{darkgray}{(since $A\supseteq C^\prime$)}}\\
& = \bigwedge \Big( A \setminus \big( B \cup \big\{ \! \min_{b\in B} c(B,b)
\big\} \big) \Big) \wedge \, \bigwedge \Big( B \cup \big\{ \! \min_{b\in B}
c(B,b) \big\}
\Big) \\
& = \bigwedge \Big( A \setminus \big( B \cup \big\{ \! \min_{b\in B} c(B,b)
\big\} \big) \Big) \wedge \, \bigwedge \! B \qquad \text{\textcolor{darkgray}{(since
  $\min_{b\in B} c(B,b)
  > \bigwedge B$)}} \\
& = \bigwedge \Big( A \setminus \big\{ \! \min_{b\in B} c(B,b) \big\} \Big)
\qquad \text{\textcolor{darkgray}{(since $A\supseteq B$ and $\min_{b\in B} c(B,b)\notin B$)}} \\
& = \bigwedge \Big( A \setminus \big\{ \! \min C^\prime \big\} \Big)
\qquad \text{\textcolor{darkgray}{(since $\min C^\prime = \min_{b\in B} c(B,b)$).}}
\end{align*}
For the second claim in Eq.~(\ref{requirement}), simply exchange $\wedge$
with $\vee$ and $>$ with $<$. Thus, for \emph{any} crosscut $C$ of~$L$, the
identity in Eq.~(\ref{nbb}) follows from our main result in Section
\ref{sec:main}.  Furthermore, the identity remains valid if $\mathscr{B}$ is
replaced by any subset $\mathscr{B}'\subseteq \mathscr{B}$.

\subsection{Arithmetical functions}
\label{sec:arithmetic-functions}

In this subsection, we establish new gcd- and lcm-sum expansions for some
classical arithmetical functions. We refer to the textbook of Apostol
\cite{Apostol:1976} for a comprehensive account of arithmetical functions in
general, and of multiplicative functions in particular.

\subsubsection{The classical M\"obius function}
\label{sec:class-mobi-funct}

For any $n\in\mathbb{N}$ let $L_n$ denote the lattice of positive divisors of
$n$, and $\mu(n)=\mu(L_n)$ the classical M\"obius function of $n$.  It is
well-known that for $n\ge 1$ and $k\ge 0$,
\begin{align}
\label{eq:18}
\mu(n) & = \begin{cases} (-1)^k, & \text{if $n$ is the product of $k$
  distinct primes,} \\  0,       & \text{otherwise}.
           \end{cases}
\end{align}                
We use $\gcd(A)$ and $\lcm(A)$ to denote the greatest common divisor
resp.\ least common multiple of any finite set $A\subseteq \mathbb{N}$.  We
adopt the convention that $\gcd(\emptyset)=0$ and \mbox{$\lcm(\emptyset)=1$}.
With $f(A)=(-1)^{|A|}$ if $\gcd(A)=1$ and $f(A)=0$ if $\gcd(A)>1$ for
$A\subseteq L_n\setminus\{1,n\}$ the first remark after Theorem \ref{thm:1}
implies that for any non-prime $n>1$,
\begin{gather}
\label{eq:12}
\sum_{\substack{A\subseteq L_n\setminus\{1,n\} \\ \gcd(A)=1}} (-1)^{|A|} =
\sum_{\substack{A\subseteq P_n^\ast \\ \gcd(A)=1}} (-1)^{|A|} =
\sum_{\substack{A\subseteq P_n\\ \gcd(A^\ast)=1}} (-1)^{|A|} =
\sum_{\substack{A\subseteq P_n \\ \lcm(A)=n}} (-1)^{|A|} = \mu(n)
\end{gather}
where $P_n$ denotes the set of prime factors of $n$, and $A^\ast =
\left\{\frac{n}{a}\mathrel| a\in A\right\}$ for any $A\subseteq P_n$.  The first
equality in Eq.~\eqref{eq:12} is due to Eq.~\eqref{eq:10}, while the last one
follows from Eq.~\eqref{eq:18} (or Eq.~\eqref{crosscut} with $C=P_n$).
Similarly, by considering the dual order on $L_n$ we obtain
\begin{gather}
\label{eq:19}
\sum_{\substack{A\subseteq L_n\setminus\{1,n\} \\ \lcm(A)=n}} (-1)^{|A|} =
\sum_{\substack{A\subseteq P_n \\ \lcm(A)=n}} (-1)^{|A|} =
\sum_{\substack{A\subseteq P_n\\ \gcd(A^\ast)=1}} (-1)^{|A|} =
\sum_{\substack{A\subseteq P_n^\ast \\ \gcd(A)=1}} (-1)^{|A|} = \mu(n)
\end{gather}
for each non-prime integer $n\ge 1$. For $n>1$, the requirement that $n$ is
non-prime is necessary in order to ensure that $P_n,P_n^\ast\subseteq
L_n\setminus\{1,n\}$ in Eqs.~\eqref{eq:12} and \eqref{eq:19}.  It can be
omitted by considering $L_n\setminus\{n\}$ in Eq.~\eqref{eq:12} and
$L_n\setminus\{1\}$ in Eq.~\eqref{eq:19}, respectively.

If $n$ is not squarefree, then $\mu(n)=0$ and hence, due to Eqs.~\eqref{eq:12}
and \eqref{eq:19}, the abstract simplicial complexes
\begin{align*}
\mathscr{S}_n & = \{A\subseteq L_n\setminus\{1,n\}\mathrel| \gcd(A)>1\}, \\
\mathscr{T}_n & = \{A\subseteq L_n\setminus\{1,n\}\mathrel|
\text{$A\neq\emptyset$ and $\lcm(A)<n$}\}
\end{align*}
have Euler characteristic~1.  Recall that the Euler characteristic
$\chi(\mathscr{A})$ of an abstract simplicial complex $\mathscr{A}$ is defined
as $\chi(\mathscr{A}) = \sum_{A\in\mathscr{A}} (-1)^{|A|-1}$, and that
$\mathscr{A}$ is called \emph{contractible} if its geometric realization as a
simplicial complex is contractible, which means, roughly speaking, that it can
be continuously shrunk to a point.  It is well-known that if $\mathscr{A}$ is
contractible, then $\chi(\mathscr{A})=1$.  In view of this, one might
conjecture that both $\mathscr{S}_n$ and $\mathscr{T}_n$ are contractible if
$n$ is not squarefree. This is indeed the case: Suppose $p^2\mathrel|n$ for
some prime~$p$.  For any $A\in\mathscr{S}_n$, if
$\gcd(A)\mathrel|\frac{n}{p}$, then $\gcd(A\cup\{\frac{n}{p}\}) = \gcd(A) >
1$; if $\gcd(A)\nmid \frac{n}{p}$, then $p^2\mathrel| \gcd(A)$ and hence,
$\gcd(A\cup\{\frac{n}{p}\})\ge p > 1$.  In both cases, $A\cup\{\frac{n}{p}\}
\in\mathscr{S}_n$. Thus, $\frac{n}{p}$ is contained in every maximal face of
$\mathscr{S}_n$. As a consequence, the geometric realization of
$\mathscr{S}_n$ is star-shaped with respect to $\frac{n}{p}$ and hence
contractible.  Similarly, by distinguishing the cases $p\mathrel|\lcm(A)$ and
$p\nmid\lcm(A)$ we may conclude that $\mathscr{T}_n$ is contractible.  In
fact, $\mathscr{S}_n$ and $\mathscr{T}_n$ are isomorphic by virtue of
$A\mapsto A^\ast$.

The preceding contractibility result establishes a link to the theory of
discrete tubes. Due to Corollary~2 of \cite{NW:1997:AT}, for any contractible
abstract simplicial complex $\mathscr{A}$,
\begin{equation}
(-1)^r \sum_{\substack{A\in\mathscr{A} \\ |A|\le r}} (-1)^{|A|-1} \le (-1)^r \quad
(r=1,2,3,\dots).
\label{eq:21}
\end{equation}
Applying this to $\mathscr{A}=\mathscr{S}_n$ resp.\ $\mathscr{T}_n$ gives
Bonferroni-like inequalities on $\gcd$- and $\lcm$-sums, e.g., in
Eqs.~\eqref{eq:12} and \eqref{eq:19}, in the particular case where $n$ is
non-squarefree.

\subsubsection{Euler's totient function}
\label{sec:eulers-toti-funct-1}

Our conclusions on Euler's totient function and its Dirichlet inverse
(cf.~Subsection \ref{sec:dirichl-inverse-eule}) are stated more generally
using the notion of a multiplicative function.  We refer to any function
$h:\mathbb{N}\rightarrow \mathbb{C}$ as \emph{multiplicative} if $h(1)=1$ and
$h(ab) = h(a)h(b)$ for any coprime $a,b\in\mathbb{N}$, and as \emph{completely
  multiplicative} if the latter condition holds for any $a,b\in\mathbb{N}$.

Examples of multiplicative functions are the identity function, the power
functions for any complex exponent, and the Liouville function, which are all
completely multiplicative; further examples include the M\"obius function,
Euler's totient function, and the sum of positive divisors of $n$.  

Let $f(A)=(-1)^{|A|-1}h(\gcd(A))$ for $A\subseteq L_n\setminus\{1,n\}$ where
$h$ is multiplicative and non-vanishing on the set of primes.  Then, $h(n)\neq
0$ for $n\in\mathbb{N}$---provided $n$ is squarefree or $h$ is completely
multiplicative. In both cases, $h(d)\neq 0$ and $h(n/d) = h(n)/h(d)$ for any
positive divisor $d$ of $n$.  In view of this, the first remark following
Theorem \ref{thm:1} implies that for any non-prime integer $n\ge 1$,
\begin{multline}
\sum_{\substack{A\subseteq L_n\setminus\{1,n\}\\ A\neq\emptyset}} (-1)^{|A|-1}
h(\gcd(A)) = \sum_{\substack{A\subseteq P_n^\ast\\ A\neq\emptyset}}
(-1)^{|A|-1} h(\gcd(A)) = \sum_{\substack{A\subseteq P_n \\ A\neq\emptyset}}
(-1)^{|A|-1} h(\gcd(A^\ast))
\\
= \sum_{\substack{A\subseteq P_n \\ A\neq\emptyset}} (-1)^{|A|-1} h\left( n
\prod_{a\in A} \frac{1}{a} \right) = h(n) - h(n) \sum_{A\subseteq P_n}
(-1)^{|A|} \prod_{a\in A} \frac{1}{h(a)}
\label{eq:totient}
\end{multline}
and hence,
\begin{align}
\label{eq:33}
\sum_{\substack{A\subseteq L_n\setminus\{1,n\}\\ A\neq\emptyset}} (-1)^{|A|-1}
h(\gcd(A)) & = h(n) - h(n) \prod_{\substack{p|n \\ \text{$p$ prime}}} \left( 1
- \frac{1}{h(p)} \right)  =: h(n) - \varphi_h(n)
\end{align}
provided $n$ is squarefree or $h$ is completely multiplicative.  For
$h=\text{id}_{\mathbb{N}}$ the function $\varphi_h$ in Eq.~\eqref{eq:33} is
known as Euler's totient function, which for any $n\in\mathbb{N}$ evaluates to
the number of positive integers coprime with $n$ (sequence A00010 in
\cite{OEIS:2014}).

In a similar way to Subsection \ref{sec:class-mobi-funct}, the requirement
that $n$ is non-prime can be dropped by considering $L_n\setminus\{n\}$
instead of $L_n\setminus\{1,n\}$ in Eqs.~\eqref{eq:totient} and \eqref{eq:33}.
Furthermore, if $n$ is not squarefree and $h$ completely multiplicative, then
$\mu(n)=0$ and hence by Eq.~\eqref{eq:12} the sum in Eq.~\eqref{eq:33} (even
with the previous modification) can be restricted to $\gcd(A)>1$.

Since $L_n\setminus\{n\}$ is a lower semilattice for any $n\in\mathbb{N}$, we
obtain by Eqs.~\eqref{eq:11} and \eqref{eq:33},
\begin{align}
\label{eq:13}
h(n)-\varphi_h(n) & = \sum_{\substack{A\subseteq L_n\setminus\{n\}\\ \text{$A$
      chain} \\ A\neq\emptyset}} (-1)^{|A|-1} h(\gcd(A))
= \sum_{d\in L_n\setminus\{n\}} h(d)\! \sum_{\substack{A\subseteq L_n\setminus\{n\}\\ \text{$A$ chain}\\
    \gcd(A)=d}} (-1)^{|A|-1} .
\end{align}
By backward induction on the height of $d$ in $L_n\setminus\{n\}$ it can be
shown that the inner sum in Eq.~\eqref{eq:13} agrees with $-\mu(n/d)$. As a
consequence, 
\begin{align}
\label{eq:14}
\varphi_h(n) & = \sum_{d|n} h(d) \mu\left( \frac{n}{d} \right) = h(n) \sum_{d|n}
\frac{\mu(d)}{h(d)}
\end{align}
provided $n$ is squarefree or $h$ is completely multiplicative. 
Under this requirement, we rediscover the known formula (cf.~Subsection \ref{sec:dirichl-inverse-eule})
\begin{gather}
\label{eq:29}
\prod_{\substack{p|n \\ \text{$p$ prime}}} \left( 1 - \frac{1}{h(p)} \right) =
\sum_{d|n} \frac{\mu(d)}{h(d)} 
\end{gather}
as an immediate consequence of Eq.~\eqref{eq:14}.  Eq.~\eqref{eq:29} also
holds for non-squarefree numbers~$n$ and any multiplicative function $h$ if
$h$ is required to be nowhere zero, or if the sum in Eq.~\eqref{eq:29} is
restricted to $d|n$ where $d$ is squarefree. Both modifications immediately
follow by applying Eq.~\eqref{eq:29} to the squarefree kernel of $n$.

\subsubsection{Dirichlet inverse of Euler's totient function}
\label{sec:dirichl-inverse-eule}

The dual of Eq.~\eqref{eq:10}, applied to $f(A)=(-1)^{|A|}h(\lcm(A))$ for any
$A\subseteq L_n\setminus\{1,n\}$ where $h$ is multiplicative reveals that for
any non-prime integer $n\ge 1$,
\begin{gather}
\label{eq:15}
\sum_{A\subseteq L_n\setminus\{1,n\}} \!(-1)^{|A|} h(\lcm(A))
= \sum_{A\subseteq P_n} (-1)^{|A|} \prod_{a\in A} h(a) 
= \! \prod_{\substack{p|n \\ \text{$p$ prime}}} \! (1-h(p)) .
\end{gather}
For $h=\text{id}_{\mathbb{N}}$ the product on the right-hand side of
Eq.~\eqref{eq:15} is known as the \emph{Dirichlet inverse} of Euler's totient
function (sequence A023900 in \cite{OEIS:2014}).  Similar to our discussion on
the totient function, the requirement that $n$ is non-prime can be removed by
considering $L_n\setminus\{1\}$ instead of $L_n\setminus\{1,n\}$ in
Eq.~\eqref{eq:15}.  Furthermore, if $n$ is not squarefree, then $\mu(n)=0$ and
hence by Eq.~\eqref{eq:19}, the sum in Eq.~\eqref{eq:15} can be restricted to
$\lcm(A)<n$.  Since $L_n\setminus\{1\}$ is an upper semilattice for any
$n\in\mathbb{N}$, we obtain by Eqs.~\eqref{eq:11} and \eqref{eq:15},
\begin{align}
\label{eq:16}
\prod_{\substack{p|n\\ \text{$p$ prime}}} (1-h(p)) = \sum_{\substack{A\subseteq L_n\setminus\{1\} \\
    \text{$A$ chain}}} (-1)^{|A|} h(\lcm(A)) = 1 + \sum_{d\in
  L_n\setminus\{1\}} h(d) \!  \sum_{\substack{A\subseteq L_n\setminus\{1\} \\
    \text{$A$ chain} \\ \lcm(A)=d}} (-1)^{|A|} .
\end{align}
By induction on the height of $d$ in $L_n\setminus\{1\}$ it follows that the
inner sum in Eq.~\eqref{eq:16} agrees with $\mu(d)$. Thus, the following known
formula (cf.~Theorem 2.18 in \cite{Apostol:1976}) is obtained:
\begin{align}
\label{eq:17}
\prod_{\substack{p|n\\ \text{$p$ prime}}} (1-h(p)) = \sum_{d|n} h(d) \mu(d) .
\end{align}
Note that in Eqs.~\eqref{eq:15}--~\eqref{eq:17} we don't impose any further
requirement on $h$.  By applying Eq.~\eqref{eq:17} to $1/h$ where $h$ is
multiplicative and nowhere zero, we rediscover Eq.~\eqref{eq:29}.

\subsubsection{Riemann zeta function}

Closely related to $\varphi_h$ in Eq.~\eqref{eq:33} is the $\zeta$-function,
which can be represented as
\begin{align}
\label{eq:20}
\frac{1}{\zeta(s)} & = \lim_{n\rightarrow\infty} \frac{\varphi_h(n!)}{h(n!)},
\quad \re(s)>1,
\end{align}
where $h(n)=n^s$ for any $n\in\mathbb{N}$.  By
Eq.~\eqref{eq:33},
\begin{align}
\label{eq:35}
\frac{1}{\zeta(s)} & = 1 + \lim_{n\rightarrow \infty} \,\frac{1}{(n!)^s}
\! \sum_{A\subseteq L_{n!}\setminus\{1,n!\}} (-1)^{|A|}
\left( \gcd(A) \right)^s, \quad \re(s)>1.
\end{align}
In particular, for $s=2$,
\begin{align}
\label{eq:36}
\lim_{n\rightarrow \infty} \,\frac{1}{(n!)^2}
\! \sum_{A\subseteq L_{n!}\setminus\{1,n!\}} (-1)^{|A|-1}
\left( \gcd(A) \right)^2 = 1 - \frac{6}{\pi^2} .
\end{align}
Eqs.~\eqref{eq:20}--\eqref{eq:36} also hold if $n!$ is replaced by $n\#$
where $n\#$ denotes the primorial of $n$, that is, the product of all primes
less than or equal to $n$ (sequence A034386 in \cite{OEIS:2014}).

\section{Generalization to convex geometries}
\label{sec:furth-gener}

A \emph{closure system} $(S,h)$ consists of a set $S$ and a hull operator $h$
on $S$, i.e.\ an extensive, increasing, idempotent operator on subsets of~$S$.
A subset $A$ of $S$ is called \emph{$h$-closed} if $h(A)=A$, and
\emph{$h$-free} if all subsets of $A$ are $h$-closed.  An \emph{$h$-basis} of
$A$ is a minimal subset $B$ of $A$ such that $h(B)=A$.  A \emph{convex
  geometry} is a closure system $(S,h)$ where $S$ is finite and any $h$-closed
subset of $S$ has a unique $h$-basis \cite{EJ:1985:TCG}.

\begin{theorem}
\label{FurtherGen}
Let $(S,h)$ be a convex geometry, $\Gamma$ an abelian group (additively
written), and $f:2^S \rightarrow \Gamma$ such that for any $h$-closed, but not
$h$-free subset $A$ of $S$,
\begin{gather}
\label{eq:1}
\sum_{I:\,A_0\subseteq I\subseteq A} f(I) = 0\, ,
\end{gather}
where $A_0$ denotes the unique $h$-basis of $A$.  Then,
\begin{gather}
\label{eq:2}
\sum_{A\subseteq S} f(A) = \sum_{\substack{A\subseteq S\\ \text{$A$ $h$-free}}}
f(A) \, .
\end{gather}
\end{theorem}

\begin{proof}
Since $(S,h)$ is a convex geometry, $h(I)=A$ if and only if $A_0\subseteq
I\subseteq A$. Hence,
\begin{gather*}
 \sum_{A\subseteq S} f(A) = \sum_{\substack{A\subseteq S \\ \text{$A$
      $h$-closed}}} \sum_{I:\,h(I)=A} f(I) = \sum_{\substack{A\subseteq S \\
    \text{$A$
      $h$-closed}}} \sum_{I:\,A_0\subseteq I\subseteq A} f(I)= \sum_{\substack{A\subseteq S \\
    \text{$A$ $h$-free}}} \sum_{I:\,A_0\subseteq I\subseteq A} f(I) \, .
\end{gather*}
Since any $A\subseteq S$ is $h$-free if and only if $A_0=A$,
the result follows.
\end{proof}

\begin{remark}
The requirement in Eq.~(\ref{eq:1}) is satisfied if $f(I) = (-1)^{|I|}
\gamma(h(I))$ for any $I\subseteq S$ where $\gamma : 2^S\rightarrow \Gamma$.
In this case, we obtain
\begin{gather}
\label{eq:3}
\sum_{A\subseteq S} (-1)^{|A|} \gamma(h(A)) = \sum_{\substack{A\subseteq S\\
    \text{$A$ $h$-free}}} (-1)^{|A|} \gamma(A) \, .
\end{gather}
In particular, by defining $\gamma(A) = (-1)^{|A|}$ for any $A\subseteq S$,
the sum $\sum_{A\subseteq S} (-1)^{|h(A)|-|A|}$ on the left-hand side of
Eq.~(\ref{eq:3}) evaluates to the number of $h$-free subsets of $S$, while by
defining $\gamma(A)=1$ for any $A\subseteq S$, Eq.~(\ref{eq:3}) reveals that
the Euler characteristic of the abstract simplicial complex of all non-empty
$h$-free subsets of $S$ is equal to 1, provided $S\neq\emptyset$. This latter result is attributed to Lawrence (unpublished,
cf.~\cite{EJ:1985:TCG}).
\end{remark}

\begin{remark}
The preceding theorem can be generalized even further by requiring that
$(S,h)$ is a closure system and replacing Eq.~(\ref{eq:1}) by
\begin{gather*}
\sum_{\emptyset \neq \mathscr{J} \subseteq \mathscr{A}_0}
(-1)^{|\mathscr{J}|-1} \! \sum_{I:\,\bigcup\!\!\mathscr{J}\subseteq I\subseteq
  A} \! f(I)
=0
\end{gather*}
where $\mathscr{A}_0$ denotes the system of all $h$-bases of $A$. Note that in
this more general setting, $A$ is $h$-free if and only if $\mathscr{A}_0 =
\{A\}$.
\end{remark}

In the following, we derive Theorem \ref{thm:1} from Theorem \ref{FurtherGen}.

\begin{proof}[Proof of Theorem~\ref{thm:1}]
The requirements imply that for any $B\in\mathscr{B}$ there is some $c(B)\in S
\setminus B$ such that $B\cup \{c(B)\} \in \mathscr{C}$ and $c(B)>b$ for any
$b\in B$.  For any $A\subseteq S$ define
\begin{align*}
\mathscr{B}|_A & :=\{B\in\mathscr{B}\mathrel| B\subseteq A\}, \\
h(A) & := A \cup \{ c(B)\mathrel| B\in\mathscr{B}|_A\}, \\
h^\ast(A) & := h(A) \cup h(h(A)) \cup \dots
\end{align*}
Then, $h^\ast$ is a hull operator on $S$, and 
\begin{align*}
A_0 & := A \setminus \{ c(B) \mathrel| B\in\mathscr{B}|_A\} 
\end{align*}
is the unique $h^\ast$-basis of any $h^\ast$-closed subset $A$ of $S$.

In order to verify Eq.~(\ref{eq:1}), let $A\subseteq S$ be $h^\ast$-closed,
but not $h^\ast$-free.  Then, $A_0\neq A$ and hence,
$\mathscr{B}|_A\neq\emptyset$.  Choose $B'\in\mathscr{B}|_A$ such that $c(B')
= \min \{c(B)\mathrel| B\in\mathscr{B}|_A\}$.  Since $B'\subseteq A$ and $A$
is $h^\ast$-closed, $c(B')\in A$ and therefore, $B'\cup \{c(B')\} \subseteq
A$.  We observe that $B'\subseteq A_0$, since otherwise $B' \cap
\{c(B)\mathrel| B\in\mathscr{B}|_A\}\neq \emptyset$, which implies $c(B)\le
\max B' < c(B')$ for some $B\in\mathscr{B}|_A$, contradicting the minimality
of $c(B')$. Now,
\begin{align*}
\sum_{I:A_0\subseteq I\subseteq A} f(I) & = \sum_{\substack{I:A_0\subseteq I
    \subseteq A \\ \max C\in I}} f(I) + \sum_{\substack{I:A_0\subseteq I
    \subseteq A \\ \max C\notin I}} f(I) 
= \sum_{\substack{I:A_0\subseteq I \subseteq A \\ \max C\in I}} (f(I) +
f(I\setminus \{\max C\})) 
\end{align*}
where $C:=B'\cup \{c(B')\}$.  Since any $I$ in the latter sum includes $C$,
Eq.~(\ref{Bedingung}) (with $I$ in place of $A$) reveals $f(I) + f(I\setminus
\{\max C\})=0$; hence, the whole sum vanishes as
required in Eq.~(\ref{eq:1}).  Applying Theorem \ref{FurtherGen} now gives a
sum over all $h^\ast$-free subsets of $S$.  Since any $A\subseteq S$ is
$h^\ast$-free if and only if $B\not\subseteq A$ for any $B\in\mathscr{B}$, the
proof is complete.
\end{proof}


\printbibliography[title={References}, ]

\end{document}