Quasirandom Graphs and the Pantograph Equation

Abstract

The pantograph differential equation and its solution, the deformed exponential function, are remarkable objects that appear in areas as diverse as combinatorics, number theory, statistical mechanics, and electrical engineering. In this article, we describe a new surprising application of these objects in graph theory, by showing that the set of all cliques is not forcing for quasirandomness. This provides a natural example of an infinite family of graphs, which is not forcing, and answers a natural question posed by P. Horn.

Keywords:

• MSC: Primary 05C35
• Secondary 05C80
• 30D20

Acknowledgments

We thank two anonymous referees for their helpful remarks. The first author was supported in part by ISF Grant 1028/16, ERC Consolidator Grant 863438, and NSF-BSF Grant 20196. The second author was supported in part by ERC Synergy grant DYNASNET 810115 and the H2020-MSCA-RISE project CoSP- GA No. 823748.

Additional information

Funding

The first author was supported in part by ISF Grant 1028/16, ERC Consolidator Grant 863438, and NSF-BSF Grant 20196. The second author was supported in part by ERC Synergy grant DYNASNET 810115 and the H2020-MSCA-RISE project CoSP- GA No. 823748.

Notes on contributors

Asaf Shapira

Asaf Shapira received his Ph.D. in computer science from Tel Aviv University in 2006. He is a professor in the School of Mathematical Sciences at Tel Aviv University since 2011, where he researches and teaches discrete mathematics with an emphasis on problems in extremal combinatorics. He was previously a postdoc at Microsoft Research, Redmond (2006–2008) and an assistant professor at Georgia Institute of Technology (2008–2011).

School of Mathematics, Tel Aviv University, Tel Aviv, Israel

[email protected]

Mykhaylo Tyomkyn

Mykhaylo Tyomkyn received his Ph.D. from the University of Cambridge in 2011. He is an assistant professor at Charles University where he works in extremal combinatorics. Previously he had postdoctoral appointments at the University of Birmingham, Tel Aviv University, the University of Oxford, and the California Institute of Technology. He enjoys chess and outdoor activities.

Department of Applied Mathematics, Charles University, Prague, Czech Republic[Mismatch]

[email protected]