Degenerate extremal problems for random discrete structures

• Grant number: 13/11353-1
• Support Opportunities: Scholarships abroad - Research Internship - Post-doctor
• Start date: October 01, 2013
• End date: September 30, 2014
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Computational Mathematics
• Principal Investigator: Yoshiharu Kohayakawa
• Grantee: Hiep Han
• Supervisor: Vojtech Rodl
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
• Institution abroad: Emory University, United States
• Associated to the scholarship: 10/16526-3 - Quasi-random hypergraphs and spanning subhypergraph containment, BP.PD

Abstract

The problem of extending classical results in extremal Combinatorics to the random setting has attracted the attention of many researchers in the last two decades. Recent breakthroughs by Schacht and by Conlon and Gowers resolved many long standing open questions in this area. However, for the class of degenerate extremal problems basic questions remain open. We introduce some of these open problems and propose to attack them by extending the method of counting independent sets in locally dense uniform hypergraphs. For non-degenerate extremal problems this approach has been successfully applied by Balogh, Morris and Samotij and, independently, by Saxton and Thomason to obtain results similar to those of Schacht and of Conlon and Gowers. However, their implications for degenerate extremal problems are rather weak. For graphs, i.e. 2-uniform hypergraphs, this approach has been carried out successfully by Prof. Kohahyakawa, the author and their colleagues to obtain sharp results for the degenerate case. An extension of these results to hypergraphs would have many applications. (AU)

Scientific publications

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

HAN, HIEP; RETTER, TROY; ROEDL, VOJTECH; SCHACHT, MATHIAS. amsey-type numbers involving graphs and hypergraphs with large girt. COMBINATORICS PROBABILITY & COMPUTING, v. 30, n. 5, p. 722-740, SEP 2021. (10/16526-3, 13/11353-1)

GAUY, MARCELO M.; HAN, HIEP; OLIVEIRA, IGOR C.. Erdos-Ko-Rado for Random Hypergraphs: Asymptotics and Stability. COMBINATORICS PROBABILITY & COMPUTING, v. 26, n. 3, p. 406-422, MAY 2017. (13/11353-1, 10/16526-3)

AIGNER-HOREV, ELAD; HAN, HIEP. Polynomial configurations in subsets of random and pseudo-random sets. JOURNAL OF NUMBER THEORY, v. 165, p. 363-381, AUG 2016. (13/11353-1, 10/16526-3)