{"data":{"id":"10.48550/arxiv.2308.02075","type":"dois","attributes":{"doi":"10.48550/arxiv.2308.02075","prefix":"10.48550","suffix":"arxiv.2308.02075","identifiers":[{"identifier":"2308.02075","identifierType":"arXiv"}],"alternateIdentifiers":[{"alternateIdentifierType":"arXiv","alternateIdentifier":"2308.02075"}],"creators":[{"name":"Chang, Evan","nameType":"Personal","givenName":"Evan","familyName":"Chang","affiliation":[],"nameIdentifiers":[]},{"name":"Kolhe, Neel","nameType":"Personal","givenName":"Neel","familyName":"Kolhe","affiliation":[],"nameIdentifiers":[]},{"name":"Sohn, Youngtak","nameType":"Personal","givenName":"Youngtak","familyName":"Sohn","affiliation":[],"nameIdentifiers":[]}],"titles":[{"title":"Upper bounds on the $2$-colorability threshold of random $d$-regular $k$-uniform hypergraphs for $k\\geq 3$"}],"publisher":"arXiv","container":{},"publicationYear":2023,"subjects":[{"lang":"en","subject":"Combinatorics (math.CO)","subjectScheme":"arXiv"},{"lang":"en","subject":"Discrete Mathematics (cs.DM)","subjectScheme":"arXiv"},{"lang":"en","subject":"Mathematical Physics (math-ph)","subjectScheme":"arXiv"},{"lang":"en","subject":"Probability (math.PR)","subjectScheme":"arXiv"},{"subject":"FOS: Mathematics","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Mathematics","schemeUri":"http://www.oecd.org/science/inno/38235147.pdf","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Computer and information sciences","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Computer and information sciences","schemeUri":"http://www.oecd.org/science/inno/38235147.pdf","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Physical sciences","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Physical sciences","schemeUri":"http://www.oecd.org/science/inno/38235147.pdf","subjectScheme":"Fields of Science and Technology (FOS)"}],"contributors":[],"dates":[{"date":"2023-08-03T23:04:55Z","dateType":"Submitted","dateInformation":"v1"},{"date":"2023-08-07T00:05:10Z","dateType":"Updated","dateInformation":"v1"},{"date":"2023-08","dateType":"Available","dateInformation":"v1"},{"date":"2023","dateType":"Issued"}],"language":null,"types":{"ris":"GEN","bibtex":"misc","citeproc":"article","schemaOrg":"CreativeWork","resourceType":"Article","resourceTypeGeneral":"Preprint"},"relatedIdentifiers":[],"relatedItems":[],"sizes":[],"formats":[],"version":"1","rightsList":[{"rights":"Creative Commons Attribution 4.0 International","rightsUri":"https://creativecommons.org/licenses/by/4.0/legalcode","schemeUri":"https://spdx.org/licenses/","rightsIdentifier":"cc-by-4.0","rightsIdentifierScheme":"SPDX"}],"descriptions":[{"description":"For a large class of random constraint satisfaction problems (CSP), deep but non-rigorous theory from statistical physics predict the location of the sharp satisfiability transition. The works of Ding, Sly, Sun (2014, 2016) and Coja-Oghlan, Panagiotou (2014) established the satisfiability threshold for random regular $k$-NAE-SAT, random $k$-SAT, and random regular $k$-SAT for large enough $k\\geq k_0$ where $k_0$ is a large non-explicit constant. Establishing the same for small values of $k\\geq 3$ remains an important open problem in the study of random CSPs. In this work, we study two closely related models of random CSPs, namely the $2$-coloring on random $d$-regular $k$-uniform hypergraphs and the random $d$-regular $k$-NAE-SAT model. For every $k\\geq 3$, we prove that there is an explicit $d_{\\ast}(k)$ which gives a satisfiability upper bound for both of the models. Our upper bound $d_{\\ast}(k)$ for $k\\geq 3$ matches the prediction from statistical physics for the hypergraph $2$-coloring by Dall'Asta, Ramezanpour, Zecchina (2008), thus conjectured to be sharp. Moreover, $d_{\\ast}(k)$ coincides with the satisfiability threshold of random regular $k$-NAE-SAT for large enough $k\\geq k_0$ by Ding, Sly, Sun (2014).","descriptionType":"Abstract"},{"description":"23 pages, 1 table","descriptionType":"Other"}],"geoLocations":[],"fundingReferences":[],"xml":"PD94bWwgdmVyc2lvbj0iMS4wIiBlbmNvZGluZz0idXRmLTgiPz4KPHJlc291cmNlIHhtbG5zPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCIgeG1sbnM6eHNpPSJodHRwOi8vd3d3LnczLm9yZy8yMDAxL1hNTFNjaGVtYS1pbnN0YW5jZSIgeHNpOnNjaGVtYUxvY2F0aW9uPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCBodHRwOi8vc2NoZW1hLmRhdGFjaXRlLm9yZy9tZXRhL2tlcm5lbC00LjMvbWV0YWRhdGEueHNkIj4KICA8aWRlbnRpZmllciBpZGVudGlmaWVyVHlwZT0iRE9JIj4xMC40ODU1MC9BUlhJVi4yMzA4LjAyMDc1PC9pZGVudGlmaWVyPgogIDxhbHRlcm5hdGVJZGVudGlmaWVycz4KICAgIDxhbHRlcm5hdGVJZGVudGlmaWVyIGFsdGVybmF0ZUlkZW50aWZpZXJUeXBlPSJhclhpdiI+MjMwOC4wMjA3NTwvYWx0ZXJuYXRlSWRlbnRpZmllcj4KICA8L2FsdGVybmF0ZUlkZW50aWZpZXJzPgogIDxjcmVhdG9ycz4KICAgIDxjcmVhdG9yPgogICAgICA8Y3JlYXRvck5hbWUgbmFtZVR5cGU9IlBlcnNvbmFsIj5DaGFuZywgRXZhbjwvY3JlYXRvck5hbWU+CiAgICAgIDxnaXZlbk5hbWU+RXZhbjwvZ2l2ZW5OYW1lPgogICAgICA8ZmFtaWx5TmFtZT5DaGFuZzwvZmFtaWx5TmFtZT4KICAgIDwvY3JlYXRvcj4KICAgIDxjcmVhdG9yPgogICAgICA8Y3JlYXRvck5hbWUgbmFtZVR5cGU9IlBlcnNvbmFsIj5Lb2xoZSwgTmVlbDwvY3JlYXRvck5hbWU+CiAgICAgIDxnaXZlbk5hbWU+TmVlbDwvZ2l2ZW5OYW1lPgogICAgICA8ZmFtaWx5TmFtZT5Lb2xoZTwvZmFtaWx5TmFtZT4KICAgIDwvY3JlYXRvcj4KICAgIDxjcmVhdG9yPgogICAgICA8Y3JlYXRvck5hbWUgbmFtZVR5cGU9IlBlcnNvbmFsIj5Tb2huLCBZb3VuZ3RhazwvY3JlYXRvck5hbWU+CiAgICAgIDxnaXZlbk5hbWU+WW91bmd0YWs8L2dpdmVuTmFtZT4KICAgICAgPGZhbWlseU5hbWU+U29objwvZmFtaWx5TmFtZT4KICAgIDwvY3JlYXRvcj4KICA8L2NyZWF0b3JzPgogIDx0aXRsZXM+CiAgICA8dGl0bGU+VXBwZXIgYm91bmRzIG9uIHRoZSAkMiQtY29sb3JhYmlsaXR5IHRocmVzaG9sZCBvZiByYW5kb20gJGQkLXJlZ3VsYXIgJGskLXVuaWZvcm0gaHlwZXJncmFwaHMgZm9yICRrXGdlcSAzJDwvdGl0bGU+CiAgPC90aXRsZXM+CiAgPHB1Ymxpc2hlcj5hclhpdjwvcHVibGlzaGVyPgogIDxwdWJsaWNhdGlvblllYXI+MjAyMzwvcHVibGljYXRpb25ZZWFyPgogIDxzdWJqZWN0cz4KICAgIDxzdWJqZWN0IHhtbDpsYW5nPSJlbiIgc3ViamVjdFNjaGVtZT0iYXJYaXYiPkNvbWJpbmF0b3JpY3MgKG1hdGguQ08pPC9zdWJqZWN0PgogICAgPHN1YmplY3QgeG1sOmxhbmc9ImVuIiBzdWJqZWN0U2NoZW1lPSJhclhpdiI+RGlzY3JldGUgTWF0aGVtYXRpY3MgKGNzLkRNKTwvc3ViamVjdD4KICAgIDxzdWJqZWN0IHhtbDpsYW5nPSJlbiIgc3ViamVjdFNjaGVtZT0iYXJYaXYiPk1hdGhlbWF0aWNhbCBQaHlzaWNzIChtYXRoLXBoKTwvc3ViamVjdD4KICAgIDxzdWJqZWN0IHhtbDpsYW5nPSJlbiIgc3ViamVjdFNjaGVtZT0iYXJYaXYiPlByb2JhYmlsaXR5IChtYXRoLlBSKTwvc3ViamVjdD4KICAgIDxzdWJqZWN0IHN1YmplY3RTY2hlbWU9IkZpZWxkcyBvZiBTY2llbmNlIGFuZCBUZWNobm9sb2d5IChGT1MpIj5GT1M6IE1hdGhlbWF0aWNzPC9zdWJqZWN0PgogICAgPHN1YmplY3Qgc3ViamVjdFNjaGVtZT0iRmllbGRzIG9mIFNjaWVuY2UgYW5kIFRlY2hub2xvZ3kgKEZPUykiPkZPUzogQ29tcHV0ZXIgYW5kIGluZm9ybWF0aW9uIHNjaWVuY2VzPC9zdWJqZWN0PgogICAgPHN1YmplY3Qgc3ViamVjdFNjaGVtZT0iRmllbGRzIG9mIFNjaWVuY2UgYW5kIFRlY2hub2xvZ3kgKEZPUykiPkZPUzogUGh5c2ljYWwgc2NpZW5jZXM8L3N1YmplY3Q+CiAgPC9zdWJqZWN0cz4KICA8ZGF0ZXM+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iU3VibWl0dGVkIiBkYXRlSW5mb3JtYXRpb249InYxIj4yMDIzLTA4LTAzVDIzOjA0OjU1WjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJVcGRhdGVkIiBkYXRlSW5mb3JtYXRpb249InYxIj4yMDIzLTA4LTA3VDAwOjA1OjEwWjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJBdmFpbGFibGUiIGRhdGVJbmZvcm1hdGlvbj0idjEiPjIwMjMtMDg8L2RhdGU+CiAgPC9kYXRlcz4KICA8cmVzb3VyY2VUeXBlIHJlc291cmNlVHlwZUdlbmVyYWw9IlByZXByaW50Ij5BcnRpY2xlPC9yZXNvdXJjZVR5cGU+CiAgPHZlcnNpb24+MTwvdmVyc2lvbj4KICA8cmlnaHRzTGlzdD4KICAgIDxyaWdodHMgcmlnaHRzVVJJPSJodHRwOi8vY3JlYXRpdmVjb21tb25zLm9yZy9saWNlbnNlcy9ieS80LjAvIiByaWdodHNJZGVudGlmaWVyU2NoZW1lPSJTUERYIiByaWdodHNJZGVudGlmaWVyPSJDQy1CWS00LjAiPkNyZWF0aXZlIENvbW1vbnMgQXR0cmlidXRpb24gNC4wIEludGVybmF0aW9uYWw8L3JpZ2h0cz4KICA8L3JpZ2h0c0xpc3Q+CiAgPGRlc2NyaXB0aW9ucz4KICAgIDxkZXNjcmlwdGlvbiBkZXNjcmlwdGlvblR5cGU9IkFic3RyYWN0Ij5Gb3IgYSBsYXJnZSBjbGFzcyBvZiByYW5kb20gY29uc3RyYWludCBzYXRpc2ZhY3Rpb24gcHJvYmxlbXMgKENTUCksIGRlZXAgYnV0IG5vbi1yaWdvcm91cyB0aGVvcnkgZnJvbSBzdGF0aXN0aWNhbCBwaHlzaWNzIHByZWRpY3QgdGhlIGxvY2F0aW9uIG9mIHRoZSBzaGFycCBzYXRpc2ZpYWJpbGl0eSB0cmFuc2l0aW9uLiBUaGUgd29ya3Mgb2YgRGluZywgU2x5LCBTdW4gKDIwMTQsIDIwMTYpIGFuZCBDb2phLU9naGxhbiwgUGFuYWdpb3RvdSAoMjAxNCkgZXN0YWJsaXNoZWQgdGhlIHNhdGlzZmlhYmlsaXR5IHRocmVzaG9sZCBmb3IgcmFuZG9tIHJlZ3VsYXIgJGskLU5BRS1TQVQsIHJhbmRvbSAkayQtU0FULCBhbmQgcmFuZG9tIHJlZ3VsYXIgJGskLVNBVCBmb3IgbGFyZ2UgZW5vdWdoICRrXGdlcSBrXzAkIHdoZXJlICRrXzAkIGlzIGEgbGFyZ2Ugbm9uLWV4cGxpY2l0IGNvbnN0YW50LiBFc3RhYmxpc2hpbmcgdGhlIHNhbWUgZm9yIHNtYWxsIHZhbHVlcyBvZiAka1xnZXEgMyQgcmVtYWlucyBhbiBpbXBvcnRhbnQgb3BlbiBwcm9ibGVtIGluIHRoZSBzdHVkeSBvZiByYW5kb20gQ1NQcy4KICBJbiB0aGlzIHdvcmssIHdlIHN0dWR5IHR3byBjbG9zZWx5IHJlbGF0ZWQgbW9kZWxzIG9mIHJhbmRvbSBDU1BzLCBuYW1lbHkgdGhlICQyJC1jb2xvcmluZyBvbiByYW5kb20gJGQkLXJlZ3VsYXIgJGskLXVuaWZvcm0gaHlwZXJncmFwaHMgYW5kIHRoZSByYW5kb20gJGQkLXJlZ3VsYXIgJGskLU5BRS1TQVQgbW9kZWwuIEZvciBldmVyeSAka1xnZXEgMyQsIHdlIHByb3ZlIHRoYXQgdGhlcmUgaXMgYW4gZXhwbGljaXQgJGRfe1xhc3R9KGspJCB3aGljaCBnaXZlcyBhIHNhdGlzZmlhYmlsaXR5IHVwcGVyIGJvdW5kIGZvciBib3RoIG9mIHRoZSBtb2RlbHMuIE91ciB1cHBlciBib3VuZCAkZF97XGFzdH0oaykkIGZvciAka1xnZXEgMyQgbWF0Y2hlcyB0aGUgcHJlZGljdGlvbiBmcm9tIHN0YXRpc3RpY2FsIHBoeXNpY3MgZm9yIHRoZSBoeXBlcmdyYXBoICQyJC1jb2xvcmluZyBieSBEYWxsJ0FzdGEsIFJhbWV6YW5wb3VyLCBaZWNjaGluYSAoMjAwOCksIHRodXMgY29uamVjdHVyZWQgdG8gYmUgc2hhcnAuIE1vcmVvdmVyLCAkZF97XGFzdH0oaykkIGNvaW5jaWRlcyB3aXRoIHRoZSBzYXRpc2ZpYWJpbGl0eSB0aHJlc2hvbGQgb2YgcmFuZG9tIHJlZ3VsYXIgJGskLU5BRS1TQVQgZm9yIGxhcmdlIGVub3VnaCAka1xnZXEga18wJCBieSBEaW5nLCBTbHksIFN1biAoMjAxNCkuPC9kZXNjcmlwdGlvbj4KICAgIDxkZXNjcmlwdGlvbiBkZXNjcmlwdGlvblR5cGU9Ik90aGVyIj4yMyBwYWdlcywgMSB0YWJsZTwvZGVzY3JpcHRpb24+CiAgPC9kZXNjcmlwdGlvbnM+CjwvcmVzb3VyY2U+","url":"https://arxiv.org/abs/2308.02075","contentUrl":null,"metadataVersion":0,"schemaVersion":"http://datacite.org/schema/kernel-4","source":"mds","isActive":true,"state":"findable","reason":null,"viewCount":0,"viewsOverTime":[],"downloadCount":0,"downloadsOverTime":[],"referenceCount":0,"citationCount":0,"citationsOverTime":[],"partCount":0,"partOfCount":0,"versionCount":0,"versionOfCount":0,"created":"2023-08-07T00:56:59.000Z","registered":"2023-08-07T00:56:59.000Z","published":"2023","updated":"2023-08-07T00:56:59.000Z"},"relationships":{"client":{"data":{"id":"arxiv.content","type":"clients"}},"provider":{"data":{"id":"arxiv","type":"providers"}},"media":{"data":{"id":"10.48550/arxiv.2308.02075","type":"media"}},"references":{"data":[]},"citations":{"data":[]},"parts":{"data":[]},"partOf":{"data":[]},"versions":{"data":[]},"versionOf":{"data":[]}}}}