6 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 conjectu…
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…
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…
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…
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…
Extremal number of cliques of given orders in graphs with a forbidden clique minor
Ruilin Shi, Fan Wei
Alon and Shikhelman initiated the systematic study of a generalization of the extremal function. Motivated by algorithmic applications, the study of the extremal function $\text{ex…