More Like this

1. Bipartite-ness under smooth conditions

   https://doi.org/10.1017/S0963548323000019  

   Jiang, Tao; Longbrake, Sean; Ma, Jie (February 2023, Combinatorics, Probability and Computing)

   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
2. On approximability of satisfiable $$\boldsymbol {k}$$-CSPs: II

   https://doi.org/10.1017/S0963548325100114  

   Bhangale, Amey; Khot, Subhash; Minzer, Dor (November 2025, Combinatorics, Probability and Computing)

   Abstract Let$$\Sigma$$be an alphabet and$$\mu$$be a distribution on$$\Sigma ^k$$for some$$k \geqslant 2$$. Let$$\alpha \gt 0$$be the minimum probability of a tuple in the support of$$\mu$$(denoted$$\mathsf{supp}(\mu )$$). We treat the parameters$$\Sigma , k, \mu , \alpha$$as fixed and constant. We say that the distribution$$\mu$$has a linear embedding if there exist an Abelian group$$G$$(with the identity element$$0_G$$) and mappings$$\sigma _i : \Sigma \rightarrow G$$,$$1 \leqslant i \leqslant k$$, such that at least one of the mappings is non-constant and for every$$(a_1, a_2, \ldots , a_k)\in \mathsf{supp}(\mu )$$,$$\sum _{i=1}^k \sigma _i(a_i) = 0_G$$. In [Bhangale-Khot-Minzer, STOC 2022], the authors asked the following analytical question. Let$$f_i: \Sigma ^n\rightarrow [\!-1,1]$$be bounded functions, such that at least one of the functions$$f_i$$essentially has degree at least$$d$$, meaning that the Fourier mass of$$f_i$$on terms of degree less than$$d$$is at most$$\delta$$. If$$\mu$$has no linear embedding (over any Abelian group), then is it necessarily the case that\begin{equation*}\left | \mathop {\mathbb{E}}_{({\textbf {x}}_1, {\textbf {x}}_2, \ldots , {\textbf {x}}_k)\sim \mu ^{\otimes n}}[f_1({\textbf {x}}_1)f_2({\textbf {x}}_2)\cdots f_k({\textbf {x}}_k)] \right | = o_{d, \delta }(1),\end{equation*}where the right hand side$$\to 0$$as the degree$$d \to \infty$$and$$\delta \to 0$$? In this paper, we answer this analytical question fully and in the affirmative for$$k=3$$. We also show the following two applications of the result.1.The first application is related to hardness of approximation. Using the reduction from [5], we show that for every$$3$$-ary predicate$$P:\Sigma ^3 \to \{0,1\}$$such that$$P$$has no linear embedding, anSDP (semi-definite programming) integrality gap instanceof a$$P$$-Constraint Satisfaction Problem (CSP) instance with gap$$(1,s)$$can be translated into a dictatorship test with completeness$$1$$and soundness$$s+o(1)$$, under certain additional conditions on the instance.2.The second application is related to additive combinatorics. We show that if the distribution$$\mu$$on$$\Sigma ^3$$has no linear embedding, marginals of$$\mu$$are uniform on$$\Sigma$$, and$$(a,a,a)\in \texttt{supp}(\mu )$$for every$$a\in \Sigma$$, then every large enough subset of$$\Sigma ^n$$contains a triple$$({\textbf {x}}_1, {\textbf {x}}_2,{\textbf {x}}_3)$$from$$\mu ^{\otimes n}$$(and in fact a significant density of such triples). 

   more » « less
3. Surface layer response to heterogeneous tree canopy distributions: roughness regime regulates secondary flow polarity

   https://doi.org/10.1017/jfm.2022.583  

   Joshi, P.; Anderson, W. (September 2022, Journal of Fluid Mechanics)

   Large-eddy simulation was used to model turbulent atmospheric surface layer (ASL) flow over canopies composed of streamwise-aligned rows of synthetic trees of height,$$h$$, and systematically arranged to quantify the response to variable streamwise spacing,$$\delta _1$$, and spanwise spacing,$$\delta _2$$, between adjacent trees. The response to spanwise and streamwise heterogeneity has, indeed, been the topic of a sustained research effort: the former resulting in formation of Reynolds-averaged counter-rotating secondary cells, the latter associated with the$$k$$- and$$d$$-type response. No study has addressed the confluence of both, and results herein show secondary flow polarity reversal across ‘critical’ values of$$\delta _1$$and$$\delta _2$$. For$$\delta _2/\delta \lesssim 1$$and$$\gtrsim 2$$, where$$\delta$$is the flow depth, the counter-rotating secondary cells are aligned such that upwelling and downwelling, respectively, occurs above the elements. The streamwise spacing$$\delta _1$$regulates this transition, with secondary cell reversal occurring first for the largest$$k$$-type cases, as elevated turbulence production within the canopy necessitates entrainment of fluid from aloft. The results are interpreted through the lens of a benchmark prognostic closure for effective aerodynamic roughness,$$z_{0,{Eff.}} = \alpha \sigma _h$$, where$$\alpha$$is a proportionality constant and$$\sigma _h$$is height root mean square. We report$$\alpha \approx 10^{-1}$$, the value reported over many decades for a broad range of rough surfaces, for$$k$$-type cases at small$$\delta _2$$, whereas the transition to$$d$$-type arrangements necessitates larger$$\delta _2$$. Though preliminary, results highlight the non-trivial response to variation of streamwise and spanwise spacing. 

   more » « less
4. Extensional rheology of dilute suspensions of spheres in polymeric liquids

   https://doi.org/10.1017/jfm.2025.10530  

   Sharma, Arjun; Koch, Donald L (September 2025, Journal of Fluid Mechanics)

   The extensional rheology of dilute suspensions of spheres in viscoelastic/polymeric liquids is studied computationally. At low polymer concentration$$c$$and Deborah number$$\textit{De}$$(imposed extension rate times polymer relaxation time), a wake of highly stretched polymers forms downstream of the particles due to larger local velocity gradients than the imposed flow, indicated by$$\Delta \textit{De}_{\textit{local}}\gt 0$$. This increases the suspension’s extensional viscosity with time and$$\textit{De}$$for$$De \lt 0.5$$. When$$\textit{De}$$exceeds 0.5, the coil-stretch transition value, the fully stretched polymers from the far-field collapse in regions with$$\Delta \textit{De}_{\textit{local}} \lt 0$$(lower velocity gradient) around the particle’s stagnation points, reducing suspension viscosity relative to the particle-free liquid. The interaction between local flow and polymers intensifies with increasing$$c$$. Highly stretched polymers impede local flow, reducing$$\Delta \textit{De}_{\textit{local}}$$, while$$\Delta \textit{De}_{\textit{local}}$$increases in regions with collapsed polymers. Initially, increasing$$c$$aligns$$\Delta \textit{De}_{\textit{local}}$$and local polymer stretch with far-field values, diminishing particle–polymer interaction effects. However, beyond a certain$$c$$, a new mechanism emerges. At low$$c$$, fluid three particle radii upstream exhibits$$\Delta \textit{De}_{\textit{local}} \gt 0$$, stretching polymers beyond their undisturbed state. As$$c$$increases, however,$$\Delta \textit{De}_{\textit{local}}$$in this region becomes negative, collapsing polymers and resulting in increasingly negative stress from particle–polymer interactions at large$$\textit{De}$$and time. At high$$c$$, this negative interaction stress scales as$$c^2$$, surpassing the linear increase of particle-free polymer stress, making dilute sphere concentrations more effective at reducing the viscosity of viscoelastic liquids at larger$$\textit{De}$$and$$c$$. 

   more » « less
5. Resistance and mobility functions for the near-contact motion of permeable particles

   https://doi.org/10.1017/jfm.2022.171  

   Reboucas, Rodrigo B; Loewenberg, Michael (May 2022, Journal of Fluid Mechanics)

   A lubrication analysis is presented for the resistances between permeable spherical particles in near contact,$$h_0/a\ll 1$$, where$$h_0$$is the minimum separation between the particles, and$$a=a_1 a_2/(a_1+a_2)$$is the reduced radius. Darcy's law is used to describe the flow inside the permeable particles and no-slip boundary conditions are applied at the particle surfaces. The weak permeability regime$$K=k/a^{2} \ll 1$$is considered, where$$k=\frac {1}{2}(k_1+k_2)$$is the mean permeability. Particle permeability enters the lubrication resistances through two functions of$$q=K^{-2/5}h_0/a$$, one describing axisymmetric motions, the other transverse. These functions are obtained by solving an integral equation for the pressure in the near-contact region. The set of resistance functions thus obtained provide the complete set of near-contact resistance functions for permeable spheres and match asymptotically to the standard hard-sphere resistances that describe pairwise hydrodynamic interactions away from the near-contact region. The results show that permeability removes the contact singularity for non-shearing particle motions, allowing rolling without slip and finite separation velocities between touching particles. Axisymmetric and transverse mobility functions are presented that describe relative particle motion under the action of prescribed forces and in linear flows. At contact, the axisymmetric mobility under the action of oppositely directed forces is$$U/U_0=d_0K^{2/5}$$, where$$U$$is the relative velocity,$$U_0$$is the velocity in the absence of hydrodynamic interactions and$$d_0=1.332$$. Under the action of a constant tangential force, a particle in contact with a permeable half-space rolls without slipping with velocity$$U/U_0=d_1(d_2+\log K^{-1})^{-1}$$, where$$d_1=3.125$$and$$d_2=6.666$$; in shear flow, the same expression holds with$$d_1=7.280$$. 

   more » « less