Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTowards a statement of the S-adic conjecture through examples
120
0
0.0
(
0
)
Added by
Fabien Durand
Publication date
2012
fields
Informatics Engineering
and research's language is
English
Authors
Fabien Durand
Ask ChatGPT about the research
No Arabic abstract
The $S$-adic conjecture claims that there exists a condition $C$ such that a sequence has a sub-linear complexity if and only if it is an $S$-adic sequence satisfying Condition $C$ for some finite set $S$ of morphisms. We present an overview of the factor complexity of $S$-adic sequences and we give some examples that either illustrate some interesting properties or that are counter-examples to what could be believed to be a good Condition $C$.
rate research
Read More
The total influence of a function is a central notion in analysis of Boolean functions, and characterizing functions that have small total influence is one of the most fundamental questions associated with it. The KKL theorem and the Friedgut junta theorem give a strong characterization of such functions whenever the bound on the total influence is $o(log n)$. However, both results become useless when the total influence of the function is $omega(log n)$. The only case in which this logarithmic barrier has been broken for an interesting class of functions was proved by Bourgain and Kalai, who focused on functions that are symmetric under large enough subgroups of $S_n$. In this paper, we build and improve on the techniques of the Bourgain-Kalai paper and establish new concentration results on the Fourier spectrum of Boolean functions with small total influence. Our results include: 1. A quantitative improvement of the Bourgain--Kalai result regarding the total influence of functions that are transitively symmetric. 2. A slightly weaker version of the Fourier--Entropy Conjecture of Friedgut and Kalai. This weaker version implies in particular that the Fourier spectrum of a constant variance, Boolean function $f$ is concentrated on $2^{O(I[f]log I[f])}$ characters, improving an earlier result of Friedgut. Removing the $log I[f]$ factor would essentially resolve the Fourier--Entropy Conjecture, as well as settle a conjecture of Mansour regarding the Fourier spectrum of polynomial size DNF formulas. Our concentration result has new implications in learning theory: it implies that the class of functions whose total influence is at most $K$ is agnostically learnable in time $2^{O(Klog K)}$, using membership queries.
This is the first in a series of six articles devoted to showing that a typical covering map of large degree to a fixed, regular graph has its new adjacency eigenvalues within the bound conjectured by Alon for random regular graphs. Many of the techniques we develop hold whether or not the base graph is regular. Our first main theorem in this series of articles is that if the base graph is $d$-regular, then for any $epsilon>0$, as the degree, $n$, of the covering map tends to infinity, some new adjacency eigenvalue of the map is larger in absolute value that $2(d-1)^{1/2}+epsilon$ with probability at most order $1/n$. Our second main theorem is that if, in addition, the base graph is Ramanujan, then this probability is bounded above and below by $1/n$ to the power of a positive integer that we call the {em tangle power} of the model, i.e., of the probability spaces of random covering maps of degree $n$. The tangle power is fairly easy to bound from below, and at times to compute exactly; it measures the probability that certain {em tangles} appear in the random covering graph, where a {em tangle} is a local event that forces the covering graph to have a new eigenvalue strictly larger than $2(d-1)^{1/2}$. Our main theorems are relativizations of Alons conjecture on the second eigenvalue of random regular graphs of large degree. In this first article of the series, we introduce all the terminology needed in this series, motivate this terminology, precisely state all the results in the remaining articles, and make some remarks about their proofs. As such, this article provides an overview of the entire series of articles; furthermore, the rest of the articles in this series may be read independently of one another.
In this paper, we study asymmetric Ramsey properties of the random graph $G_{n,p}$. Let $r in mathbb{N}$ and $H_1, ldots, H_r$ be graphs. We write $G_{n,p} to (H_1, ldots, H_r)$ to denote the property that whenever we colour the edges of $G_{n,p}$ with colours from the set $[r] := {1, ldots, r}$ there exists $i in [r]$ and a copy of $H_i$ in $G_{n,p}$ monochromatic in colour $i$. There has been much interest in determining the asymptotic threshold function for this property. R{o}dl and Ruci{n}ski determined the threshold function for the general symmetric case; that is, when $H_1 = cdots = H_r$. A conjecture of Kohayakawa and Kreuter, if true, would fully resolve the asymmetric problem. Recently, the 1-statement of this conjecture was confirmed by Mousset, Nenadov and Samotij. Building on work of Marciniszyn, Skokan, Sp{o}hel and Steger, we reduce the 0-statement of Kohayakawa and Kreuters conjecture to a certain deterministic subproblem. To demonstrate the potential of this approach, we show this subproblem can be resolved for almost all pairs of regular graphs. This therefore resolves the 0-statement for all such pairs of graphs.
This is the fifth in a series of articles devoted to showing that a typical covering map of large degree to a fixed, regular graph has its new adjacency eigenvalues within the bound conjectured by Alon for random regular graphs. In this article we use the results of Articles~III and IV in this series to prove that if the base graph is regular, then as the degree, $n$, of the covering map tends to infinity, some new adjacency eigenvalue has absolute value outside the Alon bound with probability bounded by $O(1/n)$. In addition, we give upper and lower bounds on this probability that are tight to within a multiplicative constant times the degree of the covering map. These bounds depend on two positive integers, the emph{algebraic power} (which can also be $+infty$) and the emph{tangle power} of the model of random covering map. We conjecture that the algebraic power of the models we study is always $+infty$, and in Article~VI we prove this when the base graph is regular and emph{Ramanujan}. When the algebraic power of the model is $+infty$, then the results in this article imply stronger results, such as (1) the upper and lower bounds mentioned above are matching to within a multiplicative constant, and (2) with probability smaller than any negative power of the degree, the some new eigenvalue fails to be within the Alon bound only if the covering map contains one of finitely many tangles as a subgraph (and this event has low probability).
In this note we apply a substantial improvement of a result of S. Ferenczi on $S$-adic subshifts to give Bratteli-Vershik representations of these subshifts.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
