An official website of the United States government
Abstract We determine the order of thek-core in a large class of dense graph sequences. Let$$G_n$$be a sequence of undirected,n-vertex graphs with edge weights$$\{a^n_{i,j}\}_{i,j \in [n]}$$that converges to a graphon$$W\colon[0,1]^2 \to [0,+\infty)$$in the cut metric. Keeping an edge (i,j) of$$G_n$$with probability$${a^n_{i,j}}/{n}$$independently, we obtain a sequence of random graphs$$G_n({1}/{n})$$. Using a branching process and the theory of dense graph limits, under mild assumptions we obtain the order of thek-core of random graphs$$G_n({1}/{n})$$. Our result can also be used to obtain the threshold of appearance of ak-core of ordern.
more »
« less
Polypositroids
Abstract We initiate the study of a class of polytopes, which we coinpolypositroids, defined to be those polytopes that are simultaneously generalized permutohedra (or polymatroids) and alcoved polytopes. Whereas positroids are the matroids arising from the totally nonnegative Grassmannian, polypositroids are “positive” polymatroids. We parametrize polypositroids using Coxeter necklaces and balanced graphs, and describe the cone of polypositroids by extremal rays and facet inequalities. We introduce a notion of$$(W,c)$$-polypositroidfor a finite Weyl groupWand a choice of Coxeter elementc. We connect the theory of$$(W,c)$$-polypositroids to cluster algebras of finite type and to generalized associahedra. We discussmembranes, which are certain triangulated 2-dimensional surfaces inside polypositroids. Membranes extend the notion of plabic graphs from positroids to polypositroids.
more »
« less
- PAR ID:
- 10515448
- Publisher / Repository:
- Cambridge University Press
- Date Published:
- Journal Name:
- Forum of Mathematics, Sigma
- Volume:
- 12
- ISSN:
- 2050-5094
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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 Let$$\mathrm {R}$$be a real closed field. Given a closed and bounded semialgebraic set$$A \subset \mathrm {R}^n$$and semialgebraic continuous functions$$f,g:A \rightarrow \mathrm {R}$$such that$$f^{-1}(0) \subset g^{-1}(0)$$, there exist an integer$$N> 0$$and$$c \in \mathrm {R}$$such that the inequality (Łojasiewicz inequality)$$|g(x)|^N \le c \cdot |f(x)|$$holds for all$$x \in A$$. In this paper, we consider the case whenAis defined by a quantifier-free formula with atoms of the form$$P = 0, P>0, P \in \mathcal {P}$$for some finite subset of polynomials$$\mathcal {P} \subset \mathrm {R}[X_1,\ldots ,X_n]_{\leq d}$$, and the graphs of$$f,g$$are also defined by quantifier-free formulas with atoms of the form$$Q = 0, Q>0, Q \in \mathcal {Q}$$, for some finite set$$\mathcal {Q} \subset \mathrm {R}[X_1,\ldots ,X_n,Y]_{\leq d}$$. We prove that the Łojasiewicz exponent in this case is bounded by$$(8 d)^{2(n+7)}$$. Our bound depends ondandnbut is independent of the combinatorial parameters, namely the cardinalities of$$\mathcal {P}$$and$$\mathcal {Q}$$. The previous best-known upper bound in this generality appeared inP. Solernó, Effective Łojasiewicz Inequalities in Semi-Algebraic Geometry, Applicable Algebra in Engineering, Communication and Computing (1991)and depended on the sum of degrees of the polynomials defining$$A,f,g$$and thus implicitly on the cardinalities of$$\mathcal {P}$$and$$\mathcal {Q}$$. As a consequence, we improve the current best error bounds for polynomial systems under some conditions. Finally, we prove a version of Łojasiewicz inequality in polynomially bounded o-minimal structures. We prove the existence of a common upper bound on the Łojasiewicz exponent for certain combinatorially defined infinite (but not necessarily definable) families of pairs of functions. This improves a prior result of Chris Miller (C. Miller, Expansions of the real field with power functions, Ann. Pure Appl. Logic (1994)).more » « less
-
Abstract Our work is motivated by obtaining solutions to the quantum reflection equation (qRE) by categorical methods. To start, given a braided monoidal category$${\mathcal {C}}$$and$${\mathcal {C}}$$-module category$${\mathcal {M}}$$, we introduce a version of the Drinfeld center$${\mathcal {Z}}({\mathcal {C}})$$of$${\mathcal {C}}$$adapted for$${\mathcal {M}}$$; we refer to this category as thereflective center$${\mathcal {E}}_{\mathcal {C}}({\mathcal {M}})$$of$${\mathcal {M}}$$. Just like$${\mathcal {Z}}({\mathcal {C}})$$is a canonical braided monoidal category attached to$${\mathcal {C}}$$, we show that$${\mathcal {E}}_{\mathcal {C}}({\mathcal {M}})$$is a canonical braided module category attached to$${\mathcal {M}}$$; its properties are investigated in detail. Our second goal pertains to when$${\mathcal {C}}$$is the category of modules over a quasitriangular Hopf algebraH, and$${\mathcal {M}}$$is the category of modules over anH-comodule algebraA. We show that the reflective center$${\mathcal {E}}_{\mathcal {C}}({\mathcal {M}})$$here is equivalent to a category of modules over an explicit algebra, denoted by$$R_H(A)$$, which we call thereflective algebraofA. This result is akin to$${\mathcal {Z}}({\mathcal {C}})$$being represented by the Drinfeld double$${\operatorname {Drin}}(H)$$ofH. We also study the properties of reflective algebras. Our third set of results is also in the Hopf setting above. We show that reflective algebras are quasitriangularH-comodule algebras, and we examine their corresponding quantumK-matrices; this yields solutions to the qRE. We also establish that the reflective algebra$$R_H(\mathbb {k})$$is an initial object in the category of quasitriangularH-comodule algebras, where$$\mathbb {k}$$is the ground field. The case whenHis the Drinfeld double of a finite group is illustrated.more » « less
-
Abstract The purpose of this paper is to introduce and study the following graph-theoretic paradigm. Let$$ \begin{align*}T_Kf(x)=\int K(x,y) f(y) d\mu(y),\end{align*} $$where$$f: X \to {\Bbb R}$$,Xa set, finite or infinite, andKand$$\mu $$denote a suitable kernel and a measure, respectively. Given a connected ordered graphGonnvertices, consider the multi-linear form$$ \begin{align*}\Lambda_G(f_1,f_2, \dots, f_n)=\int_{x^1, \dots, x^n \in X} \ \prod_{(i,j) \in {\mathcal E}(G)} K(x^i,x^j) \prod_{l=1}^n f_l(x^l) d\mu(x^l),\end{align*} $$where$${\mathcal E}(G)$$is the edge set ofG. Define$$\Lambda _G(p_1, \ldots , p_n)$$as the smallest constant$$C>0$$such that the inequality(0.1)$$ \begin{align} \Lambda_G(f_1, \dots, f_n) \leq C \prod_{i=1}^n {||f_i||}_{L^{p_i}(X, \mu)} \end{align} $$holds for all nonnegative real-valued functions$$f_i$$,$$1\le i\le n$$, onX. The basic question is, how does the structure ofGand the mapping properties of the operator$$T_K$$influence the sharp exponents in (0.1). In this paper, this question is investigated mainly in the case$$X={\Bbb F}_q^d$$, thed-dimensional vector space over the field withqelements,$$K(x^i,x^j)$$is the indicator function of the sphere evaluated at$$x^i-x^j$$, and connected graphsGwith at most four vertices.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1017/fms.2024.11
