An official website of the United States government
Abstract Counting independent sets in graphs and hypergraphs under a variety of restrictions is a classical question with a long history. It is the subject of the celebrated container method which found numerous spectacular applications over the years. We consider the question of how many independent sets we can have in a graph under structural restrictions. We show that any$$n$$-vertex graph with independence number$$\alpha$$without$$bK_a$$as an induced subgraph has at most$$n^{O(1)} \cdot \alpha ^{O(\alpha )}$$independent sets. This substantially improves the trivial upper bound of$$n^{\alpha },$$whenever$$\alpha \le n^{o(1)}$$and gives a characterisation of graphs forbidding which allows for such an improvement. It is also in general tight up to a constant in the exponent since there exist triangle-free graphs with$$\alpha ^{\Omega (\alpha )}$$independent sets. We also prove that if one in addition assumes the ground graph is chi-bounded one can improve the bound to$$n^{O(1)} \cdot 2^{O(\alpha )}$$which is tight up to a constant factor in the exponent.
more »
« less
Self-similarity and the direct (enstrophy) cascade in forced two-dimensional fluid turbulence
In the absence of large-scale coherent structures, a widely used statistical theory of two-dimensional turbulence developed by Kraichnan, Leith, and Batchelor (KLB) predicts a power-law scaling for the energy,$$E(k)\propto k^\alpha$$with an integral exponent$$\alpha ={-3}$$, in the inertial range associated with the direct cascade. A power-law scaling is also observed in the presence of coherent structures, but the scaling exponent becomes fractal and often differs substantially from the value predicted by the KLB theory. Here we present a dynamical theory that sheds new light on the relationship between the spatial and temporal structure of the large-scale flow and the scaling of small-scale structures representing filamentary vorticity. Specifically, we find hyperbolic regions of the large-scale flow to play a key role in the flux of enstrophy between scales. Small-scale vorticity in these regions can be described by dynamically self-similar solutions of the Euler equation, which explains the power-law scaling. Furthermore, we find that correlations between different hyperbolic regions are responsible for the emergence of fractal scaling exponents.
more »
« less
- Award ID(s):
- 2032657
- PAR ID:
- 10559022
- Publisher / Repository:
- Cambridge University Press
- Date Published:
- Journal Name:
- Journal of Fluid Mechanics
- Volume:
- 995
- ISSN:
- 0022-1120
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract In this paper, we consider random dynamical systems formed by concatenating maps acting on the unit interval$$[0,1]$$in an independent and identically distributed (i.i.d.) fashion. Considered as a stationary Markov process, the random dynamical system possesses a unique stationary measure$$\nu $$. We consider a class of non-square-integrable observables$$\phi $$, mostly of form$$\phi (x)=d(x,x_0)^{-{1}/{\alpha }}$$, where$$x_0$$is a non-recurrent point (in particular a non-periodic point) satisfying some other genericity conditions and, more generally, regularly varying observables with index$$\alpha \in (0,2)$$. The two types of maps we concatenate are a class of piecewise$$C^2$$expanding maps and a class of intermittent maps possessing an indifferent fixed point at the origin. Under conditions on the dynamics and$$\alpha $$, we establish Poisson limit laws, convergence of scaled Birkhoff sums to a stable limit law, and functional stable limit laws in both the annealed and quenched case. The scaling constants for the limit laws for almost every quenched realization are the same as those of the annealed case and determined by$$\nu $$. This is in contrast to the scalings in quenched central limit theorems where the centering constants depend in a critical way upon the realization and are not the same for almost every realization.more » « less
-
Abstract What proportion of integers$$n \leq N$$may be expressed as$$x^2 + dy^2$$for some$$d \leq \Delta $$, with$$x,y$$integers? Writing$$\Delta = (\log N)^{\log 2} 2^{\alpha \sqrt {\log \log N}}$$for some$$\alpha \in (-\infty , \infty )$$, we show that the answer is$$\Phi (\alpha ) + o(1)$$, where$$\Phi $$is the Gaussian distribution function$$\Phi (\alpha ) = \frac {1}{\sqrt {2\pi }} \int ^{\alpha }_{-\infty } e^{-x^2/2} dx$$. A consequence of this is a phase transition: Almost none of the integers$$n \leq N$$can be represented by$$x^2 + dy^2$$with$$d \leq (\log N)^{\log 2 - \varepsilon }$$, but almost all of them can be represented by$$x^2 + dy^2$$with$$d \leq (\log N)^{\log 2 + \varepsilon}\kern-1.5pt$$.more » « less
-
Abstract Given a family$$\mathcal{F}$$of bipartite graphs, theZarankiewicz number$$z(m,n,\mathcal{F})$$is the maximum number of edges in an$$m$$by$$n$$bipartite graph$$G$$that does not contain any member of$$\mathcal{F}$$as a subgraph (such$$G$$is called$$\mathcal{F}$$-free). For$$1\leq \beta \lt \alpha \lt 2$$, a family$$\mathcal{F}$$of bipartite graphs is$$(\alpha,\beta )$$-smoothif for some$$\rho \gt 0$$and every$$m\leq n$$,$$z(m,n,\mathcal{F})=\rho m n^{\alpha -1}+O(n^\beta )$$. Motivated by their work on a conjecture of Erdős and Simonovits on compactness and a classic result of Andrásfai, Erdős and Sós, Allen, Keevash, Sudakov and Verstraëte proved that for any$$(\alpha,\beta )$$-smooth family$$\mathcal{F}$$, there exists$$k_0$$such that for all odd$$k\geq k_0$$and sufficiently large$$n$$, any$$n$$-vertex$$\mathcal{F}\cup \{C_k\}$$-free graph with minimum degree at least$$\rho (\frac{2n}{5}+o(n))^{\alpha -1}$$is bipartite. In this paper, we strengthen their result by showing that for every real$$\delta \gt 0$$, there exists$$k_0$$such that for all odd$$k\geq k_0$$and sufficiently large$$n$$, any$$n$$-vertex$$\mathcal{F}\cup \{C_k\}$$-free graph with minimum degree at least$$\delta n^{\alpha -1}$$is bipartite. Furthermore, our result holds under a more relaxed notion of smoothness, which include the families$$\mathcal{F}$$consisting of the single graph$$K_{s,t}$$when$$t\gg s$$. We also prove an analogous result for$$C_{2\ell }$$-free graphs for every$$\ell \geq 2$$, which complements a result of Keevash, Sudakov and Verstraëte.more » « less
-
Abstract Every Thurston map$$f\colon S^2\rightarrow S^2$$on a$$2$$-sphere$$S^2$$induces a pull-back operation on Jordan curves$$\alpha \subset S^2\smallsetminus {P_f}$$, where$${P_f}$$is the postcritical set off. Here the isotopy class$$[f^{-1}(\alpha )]$$(relative to$${P_f}$$) only depends on the isotopy class$$[\alpha ]$$. We study this operation for Thurston maps with four postcritical points. In this case, a Thurston obstruction for the mapfcan be seen as a fixed point of the pull-back operation. We show that if a Thurston mapfwith a hyperbolic orbifold and four postcritical points has a Thurston obstruction, then one can ‘blow up’ suitable arcs in the underlying$$2$$-sphere and construct a new Thurston map$$\widehat f$$for which this obstruction is eliminated. We prove that no other obstruction arises and so$$\widehat f$$is realized by a rational map. In particular, this allows for the combinatorial construction of a large class of rational Thurston maps with four postcritical points. We also study the dynamics of the pull-back operation under iteration. We exhibit a subclass of our rational Thurston maps with four postcritical points for which we can give positive answer to the global curve attractor problem.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1017/jfm.2024.653
