{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T06:50:16Z","timestamp":1765176616113,"version":"3.37.3"},"reference-count":9,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,12,27]],"date-time":"2022-12-27T00:00:00Z","timestamp":1672099200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,12,27]],"date-time":"2022-12-27T00:00:00Z","timestamp":1672099200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100009087","name":"Industrial University of Santander","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100009087","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2023,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study the following reconstruction problem for colorings. Given a countable set <jats:italic>X<\/jats:italic> (finite or infinite), a coloring on <jats:italic>X<\/jats:italic> is a function <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varphi : [X]^{2}\\rightarrow \\{0,1\\}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03c6<\/mml:mi>\n                    <mml:mo>:<\/mml:mo>\n                    <mml:msup>\n                      <mml:mrow>\n                        <mml:mo>[<\/mml:mo>\n                        <mml:mi>X<\/mml:mi>\n                        <mml:mo>]<\/mml:mo>\n                      <\/mml:mrow>\n                      <mml:mn>2<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mo>\u2192<\/mml:mo>\n                    <mml:mrow>\n                      <mml:mo>{<\/mml:mo>\n                      <mml:mn>0<\/mml:mn>\n                      <mml:mo>,<\/mml:mo>\n                      <mml:mn>1<\/mml:mn>\n                      <mml:mo>}<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where <jats:inline-formula><jats:alternatives><jats:tex-math>$$[X]^{2}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mrow>\n                      <mml:mo>[<\/mml:mo>\n                      <mml:mi>X<\/mml:mi>\n                      <mml:mo>]<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mn>2<\/mml:mn>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is the collection of all 2-elements subsets of <jats:italic>X<\/jats:italic>. A set <jats:inline-formula><jats:alternatives><jats:tex-math>$$H\\subseteq X$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>H<\/mml:mi>\n                    <mml:mo>\u2286<\/mml:mo>\n                    <mml:mi>X<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is homogeneous for <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varphi$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03c6<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> when <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varphi$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03c6<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is constant on <jats:inline-formula><jats:alternatives><jats:tex-math>$$[H]^2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mrow>\n                      <mml:mo>[<\/mml:mo>\n                      <mml:mi>H<\/mml:mi>\n                      <mml:mo>]<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mn>2<\/mml:mn>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Let <jats:inline-formula><jats:alternatives><jats:tex-math>$${{\\,\\textrm{hom}\\,}}(\\varphi )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mrow>\n                      <mml:mspace\/>\n                      <mml:mtext>hom<\/mml:mtext>\n                      <mml:mspace\/>\n                    <\/mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>\u03c6<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> be the collection of all homogeneous sets for <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varphi$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03c6<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. The coloring <jats:inline-formula><jats:alternatives><jats:tex-math>$$1-\\varphi$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mi>\u03c6<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is called the complement of <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varphi$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03c6<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We say that <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varphi$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03c6<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is <jats:italic>reconstructible<\/jats:italic> up to complementation from its homogeneous sets, if for any coloring <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\psi$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03c8<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> on <jats:italic>X<\/jats:italic> such that <jats:inline-formula><jats:alternatives><jats:tex-math>$${{\\,\\textrm{hom}\\,}}(\\varphi )={{\\,\\textrm{hom}\\,}}(\\psi )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mrow>\n                      <mml:mspace\/>\n                      <mml:mtext>hom<\/mml:mtext>\n                      <mml:mspace\/>\n                    <\/mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>\u03c6<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mrow>\n                      <mml:mspace\/>\n                      <mml:mtext>hom<\/mml:mtext>\n                      <mml:mspace\/>\n                    <\/mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>\u03c8<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> we have that either <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\psi =\\varphi$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03c8<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mi>\u03c6<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> or <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\psi =1-\\varphi$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03c8<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mi>\u03c6<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We present several conditions for reconstructibility and non reconstructibility. For <jats:italic>X<\/jats:italic> an infinite countable set, we show that there is a Borel way to recovering a coloring from its homogeneous sets.<\/jats:p>","DOI":"10.1007\/s00373-022-02597-6","type":"journal-article","created":{"date-parts":[[2022,12,27]],"date-time":"2022-12-27T04:20:57Z","timestamp":1672114857000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Reconstruction of a Coloring from its Homogeneous Sets"],"prefix":"10.1007","volume":"39","author":[{"given":"C.","family":"Pi\u00f1a","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3452-2312","authenticated-orcid":false,"given":"C.","family":"Uzc\u00e1tegui","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,12,27]]},"reference":[{"key":"2597_CR1","first-page":"221","volume-title":"Surveys in combinatorics, London Mathematical Society Lecture Note Series","author":"JA Bondy","year":"1991","unstructured":"Bondy, J.A.: A graph reconstructor\u2019s manual. In: Surveys in combinatorics, London Mathematical Society Lecture Note Series, pp. 221\u2013252. Cambridge University Press, Cambridge (1991)"},{"key":"2597_CR2","first-page":"333","volume-title":"The mathematics of Paul Erd\u0151s II, volume 14 of Algorithms Combin","author":"PJ Cameron","year":"1997","unstructured":"Cameron, P.J.: The random graph. In: The mathematics of Paul Erd\u0151s II, volume 14 of Algorithms Combin, pp. 333\u2013351. Springer, Berlin (1997)"},{"issue":"1","key":"2597_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1017\/S0963548300000444","volume":"2","author":"PJ Cameron","year":"1993","unstructured":"Cameron, P.J., Martins, C.: A theorem on reconstruction of random graphs. Combin. Probab. Comput. 2(1), 1\u20139 (1993)","journal-title":"Combin. Probab. Comput."},{"issue":"3","key":"2597_CR4","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1515\/apam-2013-0010","volume":"4","author":"J Dammak","year":"2013","unstructured":"Dammak, J., Lopez, G., Pouzet, M., Si Kaddour, H.: Boolean sum of graphs and reconstruction up to complementation. Adv. Pure Appl. Math. 4(3), 315\u2013349 (2013)","journal-title":"Adv. Pure Appl. Math."},{"issue":"2","key":"2597_CR5","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/s00373-018-02005-y","volume":"35","author":"J Dammak","year":"2019","unstructured":"Dammak, J., Si Kaddour, H.: $$(-1)$$-hypomorphic graphs with the same 3-element homogeneous subsets. Graphs Combin. 35(2), 427\u2013436 (2019)","journal-title":"Graphs Combin."},{"issue":"1","key":"2597_CR6","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1017\/jsl.2018.66","volume":"84","author":"J Greb\u00edk","year":"2019","unstructured":"Greb\u00edk, J., Uzc\u00e1tegui, C.: Bases and Borel selectors for tall families. J. Symb. Log. 84(1), 359\u2013375 (2019)","journal-title":"J. Symb. Log."},{"issue":"11","key":"2597_CR7","doi-asserted-by":"publisher","first-page":"2022","DOI":"10.1016\/j.apal.2017.06.001","volume":"168","author":"M Hrus\u00e1k","year":"2017","unstructured":"Hrus\u00e1k, M., Meza-Alc\u00e1ntara, D., Th\u00fcmmel, E., Uzc\u00e1tegui, C.: Ramsey type properties of ideals. Ann. Pure Appl. Log. 168(11), 2022\u20132049 (2017)","journal-title":"Ann. Pure Appl. Log."},{"key":"2597_CR8","volume-title":"Classical descriptive set theory","author":"AS Kechris","year":"1994","unstructured":"Kechris, A.S.: Classical descriptive set theory. Springer-Verlag, Berlin (1994)"},{"issue":"1","key":"2597_CR9","first-page":"86","volume":"6","author":"M Pouzet","year":"2011","unstructured":"Pouzet, M., Si Kaddour, H., Trotignon, N.: Claw-freeness, 3-homogeneous subsets of a graph and a reconstruction problem. Contrib. Discret. Math. 6(1), 86\u201397 (2011)","journal-title":"Contrib. Discret. Math."}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-022-02597-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-022-02597-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-022-02597-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T21:45:56Z","timestamp":1677015956000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-022-02597-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,27]]},"references-count":9,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["2597"],"URL":"https:\/\/doi.org\/10.1007\/s00373-022-02597-6","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"type":"print","value":"0911-0119"},{"type":"electronic","value":"1435-5914"}],"subject":[],"published":{"date-parts":[[2022,12,27]]},"assertion":[{"value":"16 September 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 October 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 November 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 December 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of Interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical Approval"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to Participate"}},{"value":"We give the consent for publication.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for Publication"}}],"article-number":"6"}}