Given a family
For a subgraph
In this paper, we prove the conjecture of Häggkvist asymptotically. We also pose a conjecture which generalises this result by allowing the minimum degree conditions in each bipartite subgraph induced by pairs of parts of
- Award ID(s):
- 1800761
- NSF-PAR ID:
- 10475779
- Publisher / Repository:
- Combinatorics, Probability, & Computing
- Date Published:
- Journal Name:
- Combinatorics, Probability and Computing
- Volume:
- 31
- Issue:
- 6
- ISSN:
- 0963-5483
- Page Range / eLocation ID:
- 1031 to 1047
- Subject(s) / Keyword(s):
- extremal graph theory cycles
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
Abstract of bipartite graphs, the$\mathcal{F}$ Zarankiewicz number is the maximum number of edges in an$z(m,n,\mathcal{F})$ by$m$ bipartite graph$n$ that does not contain any member of$G$ as a subgraph (such$\mathcal{F}$ is called$G$ $\mathcal{F}$ -free ). For , a family$1\leq \beta \lt \alpha \lt 2$ of bipartite graphs is$\mathcal{F}$ -$(\alpha,\beta )$ smooth if for some and every$\rho \gt 0$ ,$m\leq n$ . 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$z(m,n,\mathcal{F})=\rho m n^{\alpha -1}+O(n^\beta )$ -smooth family$(\alpha,\beta )$ , there exists$\mathcal{F}$ such that for all odd$k_0$ and sufficiently large$k\geq k_0$ , any$n$ -vertex$n$ -free graph with minimum degree at least$\mathcal{F}\cup \{C_k\}$ is bipartite. In this paper, we strengthen their result by showing that for every real$\rho (\frac{2n}{5}+o(n))^{\alpha -1}$ , there exists$\delta \gt 0$ such that for all odd$k_0$ and sufficiently large$k\geq k_0$ , any$n$ -vertex$n$ -free graph with minimum degree at least$\mathcal{F}\cup \{C_k\}$ is bipartite. Furthermore, our result holds under a more relaxed notion of smoothness, which include the families$\delta n^{\alpha -1}$ consisting of the single graph$\mathcal{F}$ when$K_{s,t}$ . We also prove an analogous result for$t\gg s$ -free graphs for every$C_{2\ell }$ , which complements a result of Keevash, Sudakov and Verstraëte.$\ell \geq 2$ -
Abstract This paper will study almost everywhere behaviors of functions on partition spaces of cardinals possessing suitable partition properties. Almost everywhere continuity and monotonicity properties for functions on partition spaces will be established. These results will be applied to distinguish the cardinality of certain subsets of the power set of partition cardinals.
The following summarizes the main results proved under suitable partition hypotheses.
If
is a cardinal,$\kappa $ ,$\epsilon < \kappa $ ,${\mathrm {cof}}(\epsilon ) = \omega $ and$\kappa \rightarrow _* (\kappa )^{\epsilon \cdot \epsilon }_2$ , then$\Phi : [\kappa ]^\epsilon _* \rightarrow \mathrm {ON}$ satisfies the almost everywhere short length continuity property: There is a club$\Phi $ and a$C \subseteq \kappa $ so that for all$\delta < \epsilon $ , if$f,g \in [C]^\epsilon _*$ and$f \upharpoonright \delta = g \upharpoonright \delta $ , then$\sup (f) = \sup (g)$ .$\Phi (f) = \Phi (g)$ If
is a cardinal,$\kappa $ is countable,$\epsilon $ holds and$\kappa \rightarrow _* (\kappa )^{\epsilon \cdot \epsilon }_2$ , then$\Phi : [\kappa ]^\epsilon _* \rightarrow \mathrm {ON}$ satisfies the strong almost everywhere short length continuity property: There is a club$\Phi $ and finitely many ordinals$C \subseteq \kappa $ so that for all$\delta _0, ..., \delta _k \leq \epsilon $ , if for all$f,g \in [C]^\epsilon _*$ ,$0 \leq i \leq k$ , then$\sup (f \upharpoonright \delta _i) = \sup (g \upharpoonright \delta _i)$ .$\Phi (f) = \Phi (g)$ If
satisfies$\kappa $ ,$\kappa \rightarrow _* (\kappa )^\kappa _2$ and$\epsilon \leq \kappa $ , then$\Phi : [\kappa ]^\epsilon _* \rightarrow \mathrm {ON}$ satisfies the almost everywhere monotonicity property: There is a club$\Phi $ so that for all$C \subseteq \kappa $ , if for all$f,g \in [C]^\epsilon _*$ ,$\alpha < \epsilon $ , then$f(\alpha ) \leq g(\alpha )$ .$\Phi (f) \leq \Phi (g)$ Suppose dependent choice (
),$\mathsf {DC}$ and the almost everywhere short length club uniformization principle for${\omega _1} \rightarrow _* ({\omega _1})^{\omega _1}_2$ hold. Then every function${\omega _1}$ satisfies a finite continuity property with respect to closure points: Let$\Phi : [{\omega _1}]^{\omega _1}_* \rightarrow {\omega _1}$ be the club of$\mathfrak {C}_f$ so that$\alpha < {\omega _1}$ . There is a club$\sup (f \upharpoonright \alpha ) = \alpha $ and finitely many functions$C \subseteq {\omega _1}$ so that for all$\Upsilon _0, ..., \Upsilon _{n - 1} : [C]^{\omega _1}_* \rightarrow {\omega _1}$ , for all$f \in [C]^{\omega _1}_*$ , if$g \in [C]^{\omega _1}_*$ and for all$\mathfrak {C}_g = \mathfrak {C}_f$ ,$i < n$ , then$\sup (g \upharpoonright \Upsilon _i(f)) = \sup (f \upharpoonright \Upsilon _i(f))$ .$\Phi (g) = \Phi (f)$ Suppose
satisfies$\kappa $ for all$\kappa \rightarrow _* (\kappa )^\epsilon _2$ . For all$\epsilon < \kappa $ ,$\chi < \kappa $ does not inject into$[\kappa ]^{<\kappa }$ , the class of${}^\chi \mathrm {ON}$ -length sequences of ordinals, and therefore,$\chi $ . As a consequence, under the axiom of determinacy$|[\kappa ]^\chi | < |[\kappa ]^{<\kappa }|$ , these two cardinality results hold when$(\mathsf {AD})$ is one of the following weak or strong partition cardinals of determinacy:$\kappa $ ,${\omega _1}$ ,$\omega _2$ (for all$\boldsymbol {\delta }_n^1$ ) and$1 \leq n < \omega $ (assuming in addition$\boldsymbol {\delta }^2_1$ ).$\mathsf {DC}_{\mathbb {R}}$ -
Abstract We study the locations of complex zeroes of independence polynomials of bounded-degree hypergraphs. For graphs, this is a long-studied subject with applications to statistical physics, algorithms, and combinatorics. Results on zero-free regions for bounded-degree graphs include Shearer’s result on the optimal zero-free disc, along with several recent results on other zero-free regions. Much less is known for hypergraphs. We make some steps towards an understanding of zero-free regions for bounded-degree hypergaphs by proving that all hypergraphs of maximum degree
have a zero-free disc almost as large as the optimal disc for graphs of maximum degree$\Delta$ established by Shearer (of radius$\Delta$ ). Up to logarithmic factors in$\sim 1/(e \Delta )$ this is optimal, even for hypergraphs with all edge sizes strictly greater than$\Delta$ . We conjecture that for$2$ ,$k\ge 3$ -uniform$k$ linear hypergraphs have a much larger zero-free disc of radius . We establish this in the case of linear hypertrees.$\Omega (\Delta ^{- \frac{1}{k-1}} )$ -
Abstract For
and$g\ge 2$ , let$n\ge 0$ denote the complex moduli stack of$\mathcal {H}_{g,n}\subset \mathcal {M}_{g,n}$ n -marked smooth hyperelliptic curves of genusg . A normal crossings compactification of this space is provided by the theory of pointed admissible -covers. We explicitly determine the resulting dual complex, and we use this to define a graph complex which computes the weight zero compactly supported cohomology of$\mathbb {Z}/2\mathbb {Z}$ . Using this graph complex, we give a sum-over-graphs formula for the$\mathcal {H}_{g, n}$ -equivariant weight zero compactly supported Euler characteristic of$S_n$ . This formula allows for the computer-aided calculation, for each$\mathcal {H}_{g, n}$ , of the generating function$g\le 7$ for these equivariant Euler characteristics for all$\mathsf {h}_g$ n . More generally, we determine the dual complex of the boundary in any moduli space of pointed admissibleG -covers of genus zero curves, whenG is abelian, as a symmetric -complex. We use these complexes to generalize our formula for$\Delta $ to moduli spaces of$\mathsf {h}_g$ n -pointed smooth abelian covers of genus zero curves. -
Abstract We study higher uniformity properties of the Möbius function
, the von Mangoldt function$\mu $ , and the divisor functions$\Lambda $ on short intervals$d_k$ with$(X,X+H]$ for a fixed constant$X^{\theta +\varepsilon } \leq H \leq X^{1-\varepsilon }$ and any$0 \leq \theta < 1$ .$\varepsilon>0$ More precisely, letting
and$\Lambda ^\sharp $ be suitable approximants of$d_k^\sharp $ and$\Lambda $ and$d_k$ , we show for instance that, for any nilsequence$\mu ^\sharp = 0$ , we have$F(g(n)\Gamma )$ $$\begin{align*}\sum_{X < n \leq X+H} (f(n)-f^\sharp(n)) F(g(n) \Gamma) \ll H \log^{-A} X \end{align*}$$ when
and$\theta = 5/8$ or$f \in \{\Lambda , \mu , d_k\}$ and$\theta = 1/3$ .$f = d_2$ As a consequence, we show that the short interval Gowers norms
are also asymptotically small for any fixed$\|f-f^\sharp \|_{U^s(X,X+H]}$ s for these choices of . As applications, we prove an asymptotic formula for the number of solutions to linear equations in primes in short intervals and show that multiple ergodic averages along primes in short intervals converge in$f,\theta $ .$L^2$ Our innovations include the use of multiparameter nilsequence equidistribution theorems to control type
sums and an elementary decomposition of the neighborhood of a hyperbola into arithmetic progressions to control type$II$ sums.$I_2$