[{"language":[{"iso":"eng"}],"article_type":"original","oa_version":"Published Version","isi":1,"article_processing_charge":"Yes (via OA deal)","date_published":"2026-01-01T00:00:00Z","abstract":[{"text":"We show that if n is odd and p>=Clog n/n, then with high probability Hamilton cycles in G(n,p) span its cycle space. More generally, we show this holds for a class of graphs satisfying certain natural pseudorandom properties. The proof is based on a novel idea of parity-switchers, which can be thought of as analogues of absorbers in the context of cycle spaces. As another application of our method, we show that Hamilton cycles in a near-Dirac graph G, that is, a graph G with odd n vertices and minimum degree n/2+C for sufficiently large constant C, span its cycle space.\r\n","lang":"eng"}],"publication_status":"published","status":"public","has_accepted_license":"1","OA_type":"hybrid","tmp":{"short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png"},"arxiv":1,"intvolume":"       176","month":"01","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2025-10-05T22:01:34Z","_id":"20422","type":"journal_article","day":"01","corr_author":"1","quality_controlled":"1","PlanS_conform":"1","oa":1,"OA_place":"publisher","citation":{"ista":"Christoph M, Nenadov R, Petrova KH. 2026. The Hamilton space of pseudorandom graphs. Journal of Combinatorial Theory Series B. 176, 254–267.","ama":"Christoph M, Nenadov R, Petrova KH. The Hamilton space of pseudorandom graphs. <i>Journal of Combinatorial Theory Series B</i>. 2026;176:254-267. doi:<a href=\"https://doi.org/10.1016/j.jctb.2025.09.002\">10.1016/j.jctb.2025.09.002</a>","chicago":"Christoph, Micha, Rajko Nenadov, and Kalina H Petrova. “The Hamilton Space of Pseudorandom Graphs.” <i>Journal of Combinatorial Theory Series B</i>. Elsevier, 2026. <a href=\"https://doi.org/10.1016/j.jctb.2025.09.002\">https://doi.org/10.1016/j.jctb.2025.09.002</a>.","ieee":"M. Christoph, R. Nenadov, and K. H. Petrova, “The Hamilton space of pseudorandom graphs,” <i>Journal of Combinatorial Theory Series B</i>, vol. 176. Elsevier, pp. 254–267, 2026.","short":"M. Christoph, R. Nenadov, K.H. Petrova, Journal of Combinatorial Theory Series B 176 (2026) 254–267.","apa":"Christoph, M., Nenadov, R., &#38; Petrova, K. H. (2026). The Hamilton space of pseudorandom graphs. <i>Journal of Combinatorial Theory Series B</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.jctb.2025.09.002\">https://doi.org/10.1016/j.jctb.2025.09.002</a>","mla":"Christoph, Micha, et al. “The Hamilton Space of Pseudorandom Graphs.” <i>Journal of Combinatorial Theory Series B</i>, vol. 176, Elsevier, 2026, pp. 254–67, doi:<a href=\"https://doi.org/10.1016/j.jctb.2025.09.002\">10.1016/j.jctb.2025.09.002</a>."},"year":"2026","department":[{"_id":"MaKw"}],"volume":176,"publisher":"Elsevier","external_id":{"arxiv":["2402.01447"],"isi":["001585783400001"]},"date_updated":"2026-01-05T13:29:52Z","doi":"10.1016/j.jctb.2025.09.002","scopus_import":"1","ec_funded":1,"license":"https://creativecommons.org/licenses/by/4.0/","file_date_updated":"2026-01-05T13:29:34Z","acknowledgement":"This project has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 101034413. Image 1 Part of this research was conducted while the author was at Department of Computer Science, ETH Zürich, Switzerland. This author was supported by grant no. CRSII5 173721 of the Swiss National Science Foundation.","ddc":["510"],"publication_identifier":{"eissn":["1096-0902"],"issn":["0095-8956"]},"page":"254-267","title":"The Hamilton space of pseudorandom graphs","project":[{"grant_number":"101034413","name":"IST-BRIDGE: International postdoctoral program","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","call_identifier":"H2020"}],"fulldoi":"https://doi.org/10.1016/j.jctb.2025.09.002","file":[{"success":1,"checksum":"60676af4af4b3243ba187e7d65440d99","creator":"dernst","file_id":"20953","relation":"main_file","date_updated":"2026-01-05T13:29:34Z","content_type":"application/pdf","access_level":"open_access","file_size":688924,"file_name":"2026_JourCombTheoryB_Christoph.pdf","date_created":"2026-01-05T13:29:34Z"}],"author":[{"last_name":"Christoph","first_name":"Micha","full_name":"Christoph, Micha"},{"last_name":"Nenadov","first_name":"Rajko","full_name":"Nenadov, Rajko"},{"first_name":"Kalina H","full_name":"Petrova, Kalina H","id":"554ff4e4-f325-11ee-b0c4-a10dbd523381","last_name":"Petrova"}],"publication":"Journal of Combinatorial Theory Series B"},{"volume":151,"publisher":"Elsevier","department":[{"_id":"HeEd"}],"citation":{"ama":"Pach J, Tomon I. Erdős-Hajnal-type results for monotone paths. <i>Journal of Combinatorial Theory Series B</i>. 2021;151:21-37. doi:<a href=\"https://doi.org/10.1016/j.jctb.2021.05.004\">10.1016/j.jctb.2021.05.004</a>","ista":"Pach J, Tomon I. 2021. Erdős-Hajnal-type results for monotone paths. Journal of Combinatorial Theory. Series B. 151, 21–37.","chicago":"Pach, János, and István Tomon. “Erdős-Hajnal-Type Results for Monotone Paths.” <i>Journal of Combinatorial Theory. Series B</i>. Elsevier, 2021. <a href=\"https://doi.org/10.1016/j.jctb.2021.05.004\">https://doi.org/10.1016/j.jctb.2021.05.004</a>.","ieee":"J. Pach and I. Tomon, “Erdős-Hajnal-type results for monotone paths,” <i>Journal of Combinatorial Theory. Series B</i>, vol. 151. Elsevier, pp. 21–37, 2021.","short":"J. Pach, I. Tomon, Journal of Combinatorial Theory. Series B 151 (2021) 21–37.","apa":"Pach, J., &#38; Tomon, I. (2021). Erdős-Hajnal-type results for monotone paths. <i>Journal of Combinatorial Theory. Series B</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.jctb.2021.05.004\">https://doi.org/10.1016/j.jctb.2021.05.004</a>","mla":"Pach, János, and István Tomon. “Erdős-Hajnal-Type Results for Monotone Paths.” <i>Journal of Combinatorial Theory. Series B</i>, vol. 151, Elsevier, 2021, pp. 21–37, doi:<a href=\"https://doi.org/10.1016/j.jctb.2021.05.004\">10.1016/j.jctb.2021.05.004</a>."},"year":"2021","scopus_import":"1","date_updated":"2025-04-15T07:16:52Z","doi":"10.1016/j.jctb.2021.05.004","external_id":{"isi":["000702280800002"]},"publication_identifier":{"issn":["0095-8956"]},"acknowledgement":"We would like to thank the anonymous referees for their useful comments and suggestions. János Pach is partially supported by Austrian Science Fund (FWF) grant Z 342-N31 and by ERC Advanced grant “GeoScape.” István Tomon is partially supported by Swiss National Science Foundation grant no. 200021_196965, and thanks the support of MIPT Moscow. Both authors are partially supported by The Russian Government in the framework of MegaGrant no. 075-15-2019-1926.","ddc":["510"],"file_date_updated":"2021-06-28T13:33:23Z","author":[{"first_name":"János","full_name":"Pach, János","last_name":"Pach","id":"E62E3130-B088-11EA-B919-BF823C25FEA4"},{"full_name":"Tomon, István","first_name":"István","last_name":"Tomon"}],"publication":"Journal of Combinatorial Theory. Series B","file":[{"file_name":"2021_JournalOfCombinatorialTheory_Pach.pdf","date_created":"2021-06-28T13:33:23Z","file_size":418168,"access_level":"open_access","content_type":"application/pdf","relation":"main_file","creator":"asandaue","date_updated":"2021-06-28T13:33:23Z","file_id":"9612","checksum":"15fbc9064cd9d1c777ac0043b78c8f12","success":1}],"fulldoi":"https://doi.org/10.1016/j.jctb.2021.05.004","project":[{"call_identifier":"FWF","_id":"268116B8-B435-11E9-9278-68D0E5697425","name":"Mathematics, Computer Science","grant_number":"Z00342"}],"title":"Erdős-Hajnal-type results for monotone paths","page":"21-37","language":[{"iso":"eng"}],"article_type":"original","status":"public","has_accepted_license":"1","abstract":[{"lang":"eng","text":"An ordered graph is a graph with a linear ordering on its vertex set. We prove that for every positive integer k, there exists a constant ck > 0 such that any ordered graph G on n vertices with the property that neither G nor its complement contains an induced monotone path of size k, has either a clique or an independent set of size at least n^ck . This strengthens a result of Bousquet, Lagoutte, and Thomassé, who proved the analogous result for unordered graphs.\r\nA key idea of the above paper was to show that any unordered graph on n vertices that does not contain an induced path of size k, and whose maximum degree is at most c(k)n for some small c(k) > 0, contains two disjoint linear size subsets with no edge between them. This approach fails for ordered graphs, because the analogous statement is false for k ≥ 3, by a construction of Fox. We provide some further examples showing that this statement also fails for ordered graphs avoiding other ordered trees."}],"publication_status":"published","date_published":"2021-06-09T00:00:00Z","article_processing_charge":"No","isi":1,"oa_version":"Published Version","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","date_created":"2021-06-27T22:01:47Z","month":"06","intvolume":"       151","tmp":{"short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png"},"oa":1,"corr_author":"1","quality_controlled":"1","type":"journal_article","_id":"9602","day":"09"},{"language":[{"iso":"eng"}],"article_type":"original","oa_version":"Preprint","extern":"1","status":"public","publication_status":"published","abstract":[{"text":"Extending a recent breakthrough of Shitov, we prove that the chromatic number of the tensor product of two graphs can be a constant factor smaller than the minimum chromatic number of the two graphs. More precisely, we prove that there exists an absolute constant δ>0 such that for all c sufficiently large, there exist graphs G and H with chromatic number at least (1+δ)c for which χ(G×H)≤c.","lang":"eng"}],"date_published":"2021-01-01T00:00:00Z","article_processing_charge":"No","arxiv":1,"OA_type":"green","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2026-06-29T10:50:09Z","keyword":["Graph coloring","Hedetniemi's conjecture"],"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.1906.06783","open_access":"1"}],"month":"01","intvolume":"       146","quality_controlled":"1","_id":"22156","type":"journal_article","day":"01","oa":1,"OA_place":"repository","publisher":"Elsevier","volume":146,"citation":{"ieee":"X. He and Y. Wigderson, “Hedetniemi’s conjecture is asymptotically false,” <i>Journal of Combinatorial Theory, Series B</i>, vol. 146. Elsevier, pp. 485–494, 2021.","ama":"He X, Wigderson Y. Hedetniemi’s conjecture is asymptotically false. <i>Journal of Combinatorial Theory, Series B</i>. 2021;146:485-494. doi:<a href=\"https://doi.org/10.1016/j.jctb.2020.03.003\">10.1016/j.jctb.2020.03.003</a>","ista":"He X, Wigderson Y. 2021. Hedetniemi’s conjecture is asymptotically false. Journal of Combinatorial Theory, Series B. 146, 485–494.","chicago":"He, Xiaoyu, and Yuval Wigderson. “Hedetniemi’s Conjecture Is Asymptotically False.” <i>Journal of Combinatorial Theory, Series B</i>. Elsevier, 2021. <a href=\"https://doi.org/10.1016/j.jctb.2020.03.003\">https://doi.org/10.1016/j.jctb.2020.03.003</a>.","short":"X. He, Y. Wigderson, Journal of Combinatorial Theory, Series B 146 (2021) 485–494.","apa":"He, X., &#38; Wigderson, Y. (2021). Hedetniemi’s conjecture is asymptotically false. <i>Journal of Combinatorial Theory, Series B</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.jctb.2020.03.003\">https://doi.org/10.1016/j.jctb.2020.03.003</a>","mla":"He, Xiaoyu, and Yuval Wigderson. “Hedetniemi’s Conjecture Is Asymptotically False.” <i>Journal of Combinatorial Theory, Series B</i>, vol. 146, Elsevier, 2021, pp. 485–94, doi:<a href=\"https://doi.org/10.1016/j.jctb.2020.03.003\">10.1016/j.jctb.2020.03.003</a>."},"year":"2021","scopus_import":"1","doi":"10.1016/j.jctb.2020.03.003","date_updated":"2026-07-08T07:43:57Z","external_id":{"arxiv":["1906.06783"]},"publication_identifier":{"issn":["0095-8956"]},"title":"Hedetniemi's conjecture is asymptotically false","page":"485-494","author":[{"last_name":"He","first_name":"Xiaoyu","full_name":"He, Xiaoyu"},{"first_name":"Yuval","full_name":"Wigderson, Yuval","last_name":"Wigderson","id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5"}],"publication":"Journal of Combinatorial Theory, Series B","fulldoi":"https://doi.org/10.1016/j.jctb.2020.03.003"}]