Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFinitely forcible graph limits are universal
56
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
The theory of graph limits represents large graphs by analytic objects called graphons. Graph limits determined by finitely many graph densities, which are represented by finitely forcible graphons, arise in various scenarios, particularly within extremal combinatorics. Lovasz and Szegedy conjectured that all such graphons possess a simple structure, e.g., the space of their typical vertices is always finite dimensional; this was disproved by several ad hoc constructions of complex finitely forcible graphons. We prove that any graphon is a subgraphon of a finitely forcible graphon. This dismisses any hope for a result showing that finitely forcible graphons possess a simple structure, and is surprising when contrasted with the fact that finitely forcible graphons form a meager set in the space of all graphons. In addition, since any finitely forcible graphon represents the unique minimizer of some linear combination of densities of subgraphs, our result also shows that such minimization problems, which conceptually are among the simplest kind within extremal graph theory, may in fact have unique optimal solutions with arbitrarily complex structure.
rate research
Read More
Graphons are analytic objects representing limits of convergent sequences of graphs. Lovasz and Szegedy conjectured that every finitely forcible graphon, i.e. any graphon determined by finitely many graph densities, has a simple structure. In particular, one of their conjectures would imply that every finitely forcible graphon has a weak $varepsilon$-regular partition with the number of parts bounded by a polynomial in $varepsilon^{-1}$. We construct a finitely forcible graphon $W$ such that the number of parts in any weak $varepsilon$-regular partition of $W$ is at least exponential in $varepsilon^{-2}/2^{5log^*varepsilon^{-2}}$. This bound almost matches the known upper bound for graphs and, in a certain sense, is the best possible for graphons.
In this note, we show how to obtain a characteristic power series of graphons -- infinite limits of dense graphs -- as the limit of normalized reciprocal characteristic polynomials. This leads to a new characterization of graph quasi-randomness and another perspective on spectral theory for graphons, a complete description of the function in terms of the spectrum of the graphon as a self-adjoint kernel operator. Interestingly, while we apply a standard regularization to classical determinants, it is unclear how necessary this is.
A connected digraph in which the in-degree of any vertex equals its out-degree is Eulerian; this baseline result is used as the basis of existence proofs for universal cycles (also known as ucycles or generalized deBruijn cycles or U-cycles) of several combinatorial objects. The existence of ucycles is often dependent on the specific representation that we use for the combinatorial objects. For example, should we represent the subset ${2,5}$ of ${1,2,3,4,5}$ as 25 in a linear string? Is the representation 52 acceptable? Or it it tactically advantageous (and acceptable) to go with ${0,1,0,0,1}$? In this paper, we represent combinatorial objects as graphs, as in cite{bks}, and exhibit the flexibility and power of this representation to produce {it graph universal cycles}, or {it Gucycles}, for $k$-subsets of an $n$-set; permutations (and classes of permutations) of $[n]={1,2,ldots,n}$, and partitions of an $n$-set, thus revisiting the classes first studied in cite{cdg}. Under this graphical scheme, we will represent ${2,5}$ as the subgraph $A$ of $C_5$ with edge set consisting of ${2,3}$ and ${5,1}$, namely the second and fifth edges in $C_5$. Permutations are represented via their permutation graphs, and set partitions through disjoint unions of complete graphs.
A subbundle of variable dimension inside the tangent bundle of a smooth manifold is called a smooth distribution if it is the pointwise span of a family of smooth vector fields. We prove that all such distributions are finitely generated, meaning that the family may be taken to be a finite collection. Further, we show that the space of smooth sections of such distributions need not be finitely generated as a module over the smooth functions. Our results are valid in greater generality, where the tangent bundle may be replaced by an arbitrary vector bundle.
It is proved that any vertex operator algebra for which the image of the Virasoro element in Zhus algebra is algebraic over complex numbers is finitely generated. In particular, any vertex operator algebra with a finite dimensional Zhus algebra is finitely generated. As a result, any rational vertex operator algebra is finitely generated.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
