<?xml version="1.0" encoding="utf-8"?>
<TEI xmlns="http://www.tei-c.org/ns/1.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:hal="http://hal.archives-ouvertes.fr/" xmlns:gml="http://www.opengis.net/gml/3.3/" xmlns:gmlce="http://www.opengis.net/gml/3.3/ce" version="1.1" xsi:schemaLocation="http://www.tei-c.org/ns/1.0 http://api.archives-ouvertes.fr/documents/aofr-sword.xsd">
  <teiHeader>
    <fileDesc>
      <titleStmt>
        <title>HAL TEI export of lirmm-00395073</title>
      </titleStmt>
      <publicationStmt>
        <distributor>CCSD</distributor>
        <availability status="restricted">
          <licence target="https://creativecommons.org/publicdomain/zero/1.0/">CC0 1.0 - Universal</licence>
        </availability>
        <date when="2026-05-06T10:59:53+02:00"/>
      </publicationStmt>
      <sourceDesc>
        <p part="N">HAL API Platform</p>
      </sourceDesc>
    </fileDesc>
  </teiHeader>
  <text>
    <body>
      <listBibl>
        <biblFull>
          <titleStmt>
            <title xml:lang="en">The Active Bijection in Graphs, Hyperplane Arrangements, and Oriented Matroids - 1 - The fully Optimal Basis of a Bounded Region</title>
            <author role="aut">
              <persName>
                <forename type="first">Emeric</forename>
                <surname>Gioan</surname>
              </persName>
              <email type="md5">aa32d1c967f4089e573a57177ea1b5e1</email>
              <email type="domain">lirmm.fr</email>
              <idno type="idhal" notation="string">emeric-gioan</idno>
              <idno type="idhal" notation="numeric">740668</idno>
              <idno type="halauthorid" notation="string">28733-740668</idno>
              <idno type="ORCID">https://orcid.org/0009-0007-3370-5460</idno>
              <affiliation ref="#struct-388229"/>
            </author>
            <author role="aut">
              <persName>
                <forename type="first">Michel</forename>
                <surname>Las Vergnas</surname>
              </persName>
              <idno type="halauthorid">211579-0</idno>
              <affiliation ref="#struct-541850"/>
            </author>
            <editor role="depositor">
              <persName>
                <forename>Emeric</forename>
                <surname>Gioan</surname>
              </persName>
              <email type="md5">aa32d1c967f4089e573a57177ea1b5e1</email>
              <email type="domain">lirmm.fr</email>
            </editor>
          </titleStmt>
          <editionStmt>
            <edition n="v1" type="current">
              <date type="whenSubmitted">2009-06-14 17:02:39</date>
              <date type="whenModified">2025-08-13 03:08:01</date>
              <date type="whenReleased">2009-06-15 15:57:45</date>
              <date type="whenProduced">2009</date>
              <ref type="externalLink" target="https://doi.org/10.1016/j.ejc.2008.12.013"/>
            </edition>
            <respStmt>
              <resp>contributor</resp>
              <name key="119041">
                <persName>
                  <forename>Emeric</forename>
                  <surname>Gioan</surname>
                </persName>
                <email type="md5">aa32d1c967f4089e573a57177ea1b5e1</email>
                <email type="domain">lirmm.fr</email>
              </name>
            </respStmt>
          </editionStmt>
          <publicationStmt>
            <distributor>CCSD</distributor>
            <idno type="halId">lirmm-00395073</idno>
            <idno type="halUri">https://hal-lirmm.ccsd.cnrs.fr/lirmm-00395073</idno>
            <idno type="halBibtex">gioan:lirmm-00395073</idno>
            <idno type="halRefHtml">&lt;i&gt;European Journal of Combinatorics&lt;/i&gt;, 2009, 30 (8 (special issue: Combinatorial Geometries and Applications: Oriented Matroids and Matroids)), pp.1868-1886. &lt;a target="_blank" href="https://dx.doi.org/10.1016/j.ejc.2008.12.013"&gt;&amp;#x27E8;10.1016/j.ejc.2008.12.013&amp;#x27E9;&lt;/a&gt;</idno>
            <idno type="halRef">European Journal of Combinatorics, 2009, 30 (8 (special issue: Combinatorial Geometries and Applications: Oriented Matroids and Matroids)), pp.1868-1886. &amp;#x27E8;10.1016/j.ejc.2008.12.013&amp;#x27E9;</idno>
            <availability status="restricted"/>
          </publicationStmt>
          <seriesStmt>
            <idno type="stamp" n="UNIV-PARIS7" corresp="UNIV-PARIS">Université Denis Diderot - Paris VII</idno>
            <idno type="stamp" n="UPMC" corresp="SORBONNE-UNIVERSITE">Université Pierre et Marie Curie</idno>
            <idno type="stamp" n="CNRS">CNRS - Centre national de la recherche scientifique</idno>
            <idno type="stamp" n="IMJ" corresp="SORBONNE-UNIVERSITE">Institut de Mathématiques de Jussieu</idno>
            <idno type="stamp" n="ALGCO" corresp="LIRMM">Algorithmes, Graphes et Combinatoire</idno>
            <idno type="stamp" n="LIRMM">Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier</idno>
            <idno type="stamp" n="TDS-MACS">Réseau de recherche en Théorie des Systèmes Distribués, Modélisation, Analyse et Contrôle des Systèmes</idno>
            <idno type="stamp" n="UPMC_POLE_1" corresp="UPMC">UPMC Pôle 1</idno>
            <idno type="stamp" n="MIPS">Mathématiques, Informatique, Physique et Systèmes</idno>
            <idno type="stamp" n="UNIV-MONTPELLIER">Université de Montpellier</idno>
            <idno type="stamp" n="SORBONNE-UNIVERSITE">Sorbonne Université</idno>
            <idno type="stamp" n="SU-SCIENCES" corresp="SORBONNE-UNIVERSITE">Faculté des Sciences de Sorbonne Université</idno>
            <idno type="stamp" n="UNIV-PARIS">Université Paris Cité</idno>
            <idno type="stamp" n="UP-SCIENCES">Université Paris Cité - Faculté des Sciences</idno>
            <idno type="stamp" n="SU-TI">Sorbonne Université - Texte Intégral</idno>
            <idno type="stamp" n="ALLIANCE-SU"> Alliance Sorbonne Université</idno>
            <idno type="stamp" n="UM-2015-2021" corresp="UNIV-MONTPELLIER">Université de Montpellier (2015-2021)</idno>
          </seriesStmt>
          <notesStmt>
            <note type="audience" n="2">International</note>
            <note type="popular" n="0">No</note>
            <note type="peer" n="1">Yes</note>
          </notesStmt>
          <sourceDesc>
            <biblStruct>
              <analytic>
                <title xml:lang="en">The Active Bijection in Graphs, Hyperplane Arrangements, and Oriented Matroids - 1 - The fully Optimal Basis of a Bounded Region</title>
                <author role="aut">
                  <persName>
                    <forename type="first">Emeric</forename>
                    <surname>Gioan</surname>
                  </persName>
                  <email type="md5">aa32d1c967f4089e573a57177ea1b5e1</email>
                  <email type="domain">lirmm.fr</email>
                  <idno type="idhal" notation="string">emeric-gioan</idno>
                  <idno type="idhal" notation="numeric">740668</idno>
                  <idno type="halauthorid" notation="string">28733-740668</idno>
                  <idno type="ORCID">https://orcid.org/0009-0007-3370-5460</idno>
                  <affiliation ref="#struct-388229"/>
                </author>
                <author role="aut">
                  <persName>
                    <forename type="first">Michel</forename>
                    <surname>Las Vergnas</surname>
                  </persName>
                  <idno type="halauthorid">211579-0</idno>
                  <affiliation ref="#struct-541850"/>
                </author>
              </analytic>
              <monogr>
                <idno type="halJournalId" status="VALID">13025</idno>
                <idno type="issn">0195-6698</idno>
                <idno type="eissn">1095-9971</idno>
                <title level="j">European Journal of Combinatorics</title>
                <imprint>
                  <publisher>Elsevier</publisher>
                  <biblScope unit="volume">30</biblScope>
                  <biblScope unit="issue">8 (special issue: Combinatorial Geometries and Applications: Oriented Matroids and Matroids)</biblScope>
                  <biblScope unit="pp">1868-1886</biblScope>
                  <date type="datePub">2009</date>
                </imprint>
              </monogr>
              <idno type="doi">10.1016/j.ejc.2008.12.013</idno>
            </biblStruct>
          </sourceDesc>
          <profileDesc>
            <langUsage>
              <language ident="en">English</language>
            </langUsage>
            <textClass>
              <keywords scheme="author">
                <term xml:lang="en">basis</term>
                <term xml:lang="en">optimal basis</term>
                <term xml:lang="en">linear programming</term>
                <term xml:lang="en">bijection</term>
                <term xml:lang="en">bounded region</term>
                <term xml:lang="en">bipolar orientation</term>
                <term xml:lang="en">acyclic orientation</term>
                <term xml:lang="en">activity</term>
                <term xml:lang="en">orientation</term>
                <term xml:lang="en">Tutte polynomial</term>
                <term xml:lang="en">oriented matroid</term>
                <term xml:lang="en">matroid</term>
                <term xml:lang="en">hyperplane arrangement</term>
                <term xml:lang="en">AMS Classification: Primary: 52C40. Secondary: 05A99 05B35 05C20 52C35 90C05 Keywords: directed graph</term>
              </keywords>
              <classCode scheme="halDomain" n="info.info-dm">Computer Science [cs]/Discrete Mathematics [cs.DM]</classCode>
              <classCode scheme="halTypology" n="ART">Journal articles</classCode>
              <classCode scheme="halOldTypology" n="ART">Journal articles</classCode>
              <classCode scheme="halTreeTypology" n="ART">Journal articles</classCode>
            </textClass>
            <abstract xml:lang="en">
              <p>The present paper is the first in a series of four introducing a mapping from orientations to spanning trees in graphs, from regions to simplices in real hyperplane arrangements, from reorientations to bases in oriented matroids (in order of increasing generality). We call it the active orientation-to-basis mapping, in reference to an extensive use of activities, a notion depending on a linear ordering, first introduced by W.T. Tutte for spanning trees in graphs. The active mapping, which preserves activities, can be considered as a bijective generalization of a polynomial identity relating two expressions - one in terms of activities of reorientations, and the other in terms of activities of bases - of the Tutte polynomial of a graph, a hyperplane arrangement or an oriented matroid. Specializations include bijective versions of well-known enumerative results related to the counting of acyclic orientations in graphs or of regions in hyperplane arrangements. Other interesting features of the active mapping are links established between linear programming and the Tutte polynomial. We consider here the bounded case of the active mapping, where bounded corresponds to bipolar orientations in the case of graphs, and refers to bounded regions in the case of real hyperplane arrangements, or of oriented matroids. In terms of activities, this is the uniactive internal case. We introduce fully optimal bases, simply defined in terms of signs, strengthening optimal bases of linear programming. An optimal basis is associated with one flat with a maximality property, whereas a fully optimal basis is equivalent to a complete flag of flats, each with a maximality property. The main results of the paper are that a bounded region has a unique fully optimal basis, and that, up to negating all signs, fully optimal bases provide a bijection between bounded regions and uniactive internal bases. In the bounded case, up to negating all signs, the active mapping is a bijection.</p>
            </abstract>
          </profileDesc>
        </biblFull>
      </listBibl>
    </body>
    <back>
      <listOrg type="structures">
        <org type="researchteam" xml:id="struct-388229" status="OLD">
          <orgName>Algorithmes, Graphes et Combinatoire</orgName>
          <orgName type="acronym">ALGCO</orgName>
          <date type="end">2021-12-31</date>
          <desc>
            <address>
              <addrLine>LIRMM, 161 rue Ada, 34000 Montpellier</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">https://www.lirmm.fr/equipes/ALGCO/</ref>
          </desc>
          <listRelation>
            <relation active="#struct-181" type="direct"/>
            <relation name="UMR5506" active="#struct-410122" type="indirect"/>
            <relation name="UMR5506" active="#struct-441569" type="indirect"/>
          </listRelation>
        </org>
        <org type="researchteam" xml:id="struct-541850" status="OLD">
          <orgName>Equipe combinatoire et optimisation</orgName>
          <orgName type="acronym">C&amp;O</orgName>
          <date type="end">2019-12-31</date>
          <desc>
            <address>
              <country key="FR"/>
            </address>
          </desc>
          <listRelation>
            <relation active="#struct-250709" type="direct"/>
            <relation active="#struct-93591" type="indirect"/>
            <relation name="UMR_7586" active="#struct-300301" type="indirect"/>
            <relation name="UMR7586" active="#struct-441569" type="indirect"/>
          </listRelation>
        </org>
        <org type="laboratory" xml:id="struct-181" status="OLD">
          <idno type="IdRef">139590827</idno>
          <idno type="ISNI">0000000405990488</idno>
          <idno type="RNSR">199111950H</idno>
          <idno type="ROR">https://ror.org/013yean28</idno>
          <orgName>Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier</orgName>
          <orgName type="acronym">LIRMM</orgName>
          <date type="start">1995-01-01</date>
          <date type="end">2021-12-31</date>
          <desc>
            <address>
              <addrLine>161 rue Ada - 34095 Montpellier</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">https://www.lirmm.fr</ref>
          </desc>
          <listRelation>
            <relation name="UMR5506" active="#struct-410122" type="direct"/>
            <relation name="UMR5506" active="#struct-441569" type="direct"/>
          </listRelation>
        </org>
        <org type="institution" xml:id="struct-410122" status="OLD">
          <idno type="ISNI">0000000120970141</idno>
          <idno type="ROR">https://ror.org/051escj72</idno>
          <orgName>Université de Montpellier</orgName>
          <orgName type="acronym">UM</orgName>
          <date type="end">2021-12-31</date>
          <desc>
            <address>
              <addrLine>163 rue Auguste Broussonnet - 34090 Montpellier</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">http://www.umontpellier.fr/</ref>
          </desc>
        </org>
        <org type="regroupinstitution" xml:id="struct-441569" status="VALID">
          <idno type="IdRef">02636817X</idno>
          <idno type="ISNI">0000000122597504</idno>
          <idno type="ROR">https://ror.org/02feahw73</idno>
          <orgName>Centre National de la Recherche Scientifique</orgName>
          <orgName type="acronym">CNRS</orgName>
          <date type="start">1939-10-19</date>
          <desc>
            <address>
              <country key="FR"/>
            </address>
            <ref type="url">https://www.cnrs.fr/</ref>
          </desc>
        </org>
        <org type="laboratory" xml:id="struct-250709" status="OLD">
          <idno type="IdRef">084976330</idno>
          <idno type="RNSR">199712632Y</idno>
          <orgName>Institut de Mathématiques de Jussieu - Paris Rive Gauche</orgName>
          <orgName type="acronym">IMJ-PRG (UMR_7586)</orgName>
          <date type="start">2000-01-01</date>
          <date type="end">2019-12-31</date>
          <desc>
            <address>
              <addrLine>UPMC - 4 place Jussieu, Case 247 - 75252 Paris Cedex 5UP7D - Campus des Grands Moulins - Bâtiment Sophie Germain, Case 7012- 75205 PARIS Cedex 13</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">http://www.institut.math.jussieu.fr/</ref>
          </desc>
          <listRelation>
            <relation active="#struct-93591" type="direct"/>
            <relation name="UMR_7586" active="#struct-300301" type="direct"/>
            <relation name="UMR7586" active="#struct-441569" type="direct"/>
          </listRelation>
        </org>
        <org type="institution" xml:id="struct-93591" status="OLD">
          <idno type="ROR">https://ror.org/02en5vm52</idno>
          <orgName>Université Pierre et Marie Curie - Paris 6</orgName>
          <orgName type="acronym">UPMC</orgName>
          <date type="end">2017-12-31</date>
          <desc>
            <address>
              <addrLine>4 place Jussieu - 75005 Paris</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">http://www.upmc.fr/</ref>
          </desc>
        </org>
        <org type="institution" xml:id="struct-300301" status="OLD">
          <idno type="IdRef">027542084</idno>
          <idno type="ISNI">0000000121514068</idno>
          <idno type="ROR">https://ror.org/02n7qrg46</idno>
          <orgName>Université Paris Diderot - Paris 7</orgName>
          <orgName type="acronym">UPD7</orgName>
          <date type="end">2019-12-31</date>
          <desc>
            <address>
              <addrLine>5 rue Thomas-Mann - 75205 Paris cedex 13</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">http://www.univ-paris-diderot.fr</ref>
          </desc>
        </org>
      </listOrg>
    </back>
  </text>
</TEI>