7 papers · 1 filter
On the growth rate of the Stanley-Wilf limit of blockable permutations
Saksham Sethi, Fan Wei
Given a permutation , let be the number of permutations of length that avoid as a subpermutation. The celebrated resolution of the Stanley-Wilf conje…
New Sidorenko-type inequalities in tournaments
Xiaoyu He, Nitya Mani, Jiaxi Nie +2
As a directed analog of Sidorenko's conjecture in extremal graph theory, Fox, Himwich, Zhou, and the second author defined an oriented graph to be tournament Sidorenko (anti-Si…
Social Networks: Enumerating Maximal Community Patterns in -Closed Graphs
Gabriela Bourla, Kaixin Wang, Fan Wei +1
Jacob Fox, C. Seshadhri, Tim Roughgarden, Fan Wei, and Nicole Wein introduced the model of -closed graphs--a distribution-free model motivated by triadic closure, one of the mos…
On Domination Exponents for Pairs of Graphs
Grigoriy Blekherman, Annie Raymond, Alexander Razborov +1
Understanding graph density profiles is notoriously challenging. Even for pairs of graphs, complete characterizations are known only in very limited cases, such as edges versus cli…
Undecidability of polynomial inequalities in tournaments
Hao Chen, Yupeng Lin, Jie Ma +1
Many fundamental problems in extremal combinatorics are equivalent to proving certain polynomial inequalities in graph homomorphism densities. In 2011, a breakthrough result by Hat…
The binomial random graph is a bad inducer
Vishesh Jain, Marcus Michelen, Fan Wei
For a finite graph and a value , let denote the largest for which there is a sequence of graphs of edge density approaching so that the induced $F…