More Like this

1. Robust Recovery of Robinson Property in $L^p$-Graphons: A Cut-Norm Approach

   https://doi.org/10.37236/12435  

   Ghandehari, Mahya; Mishura, Teddy (October 2024, The Electronic Journal of Combinatorics)

   This paper investigates the Robinson graphon completion/recovery problem within the class of $L^p$-graphons, focusing on the range $$5 5$, any $L^p$-graphon $$w$$ can be approximated by a Robinson graphon, with error of the approximation bounded in terms of $$\Lambda(w)$$. When viewing $$w$$ as a noisy version of a Robinson graphon, our method provides a concrete recipe for recovering a cut-norm approximation of a noiseless $$w$$. Given that any symmetric matrix is a special type of graphon, our results can be applicable to symmetric matrices of any size. Our work extends and improves previous results, where a similar question for the special case of $$L^\infty$$-graphons was answered. 

   more » « less
2. The Implicit Graph Conjecture is False

   https://doi.org/10.1109/FOCS54457.2022.00109  

   Hatami, Hamed; Hatami, Pooya (October 2022, Annual Symposium on Foundations of Computer Science)

   An efficient implicit representation of an n-vertex graph G in a family F of graphs assigns to each vertex of G a binary code of length O(log n) so that the adjacency between every pair of vertices can be determined only as a function of their codes. This function can depend on the family but not on the individual graph. Every family of graphs admitting such a representation contains at most 2^O(n log(n)) graphs on n vertices, and thus has at most factorial speed of growth. The Implicit Graph Conjecture states that, conversely, every hereditary graph family with at most factorial speed of growth admits an efficient implicit representation. We refute this conjecture by establishing the existence of hereditary graph families with factorial speed of growth that require codes of length n^Ω(1). 

   more » « less
3. Domination inequalities and dominating graphs

   https://doi.org/10.1017/S0305004124000185  

   CONLON, DAVID; LEE, JOONKYUNG (July 2024, Mathematical Proceedings of the Cambridge Philosophical Society)

   Abstract We say that a graphHdominates another graphH^′if the number of homomorphisms fromH^′to any graphGis dominated, in an appropriate sense, by the number of homomorphisms fromHtoG. We study the family of dominating graphs, those graphs with the property that they dominate all of their subgraphs. It has long been known that even-length paths are dominating in this sense and a result of Hatami implies that all weakly norming graphs are dominating. In a previous paper, we showed that every finite reflection group gives rise to a family of weakly norming, and hence dominating, graphs. Here we revisit this connection to show that there is a much broader class of dominating graphs. 

   more » « less
4. On the edit distance function of the random graph

   https://doi.org/10.1017/S0963548321000353  

   Martin, Ryan R.; Riasanovsky, Alex W. (March 2022, Combinatorics, Probability and Computing)

   Abstract Given a hereditary property of graphs $$\mathcal{H}$$ and a $$p\in [0,1]$$ , the edit distance function $$\textrm{ed}_{\mathcal{H}}(p)$$ is asymptotically the maximum proportion of edge additions plus edge deletions applied to a graph of edge density p sufficient to ensure that the resulting graph satisfies $$\mathcal{H}$$ . The edit distance function is directly related to other well-studied quantities such as the speed function for $$\mathcal{H}$$ and the $$\mathcal{H}$$ -chromatic number of a random graph. Let $$\mathcal{H}$$ be the property of forbidding an Erdős–Rényi random graph $$F\sim \mathbb{G}(n_0,p_0)$$ , and let $$\varphi$$ represent the golden ratio. In this paper, we show that if $$p_0\in [1-1/\varphi,1/\varphi]$$ , then a.a.s. as $$n_0\to\infty$$ , \begin{align*} {\textrm{ed}}_{\mathcal{H}}(p) = (1+o(1))\,\frac{2\log n_0}{n_0} \cdot\min\left\{ \frac{p}{-\log(1-p_0)}, \frac{1-p}{-\log p_0} \right\}. \end{align*} Moreover, this holds for $$p\in [1/3,2/3]$$ for any $$p_0\in (0,1)$$ . A primary tool in the proof is the categorization of p -core coloured regularity graphs in the range $$p\in[1-1/\varphi,1/\varphi]$$ . Such coloured regularity graphs must have the property that the non-grey edges form vertex-disjoint cliques. 

   more » « less
5. Fluctuations of subgraph counts in graphon based random graphs

   https://doi.org/10.1017/S0963548322000335  

   Bhattacharya, Bhaswar B.; Chatterjee, Anirban; Janson, Svante (May 2023, Combinatorics, Probability and Computing)

   Abstract Given a graphon $$W$$ and a finite simple graph $$H$$ , with vertex set $V(H)$ , denote by $$X_n(H, W)$$ the number of copies of $$H$$ in a $$W$$ -random graph on $$n$$ vertices. The asymptotic distribution of $$X_n(H, W)$$ was recently obtained by Hladký, Pelekis, and Šileikis [17] in the case where $$H$$ is a clique. In this paper, we extend this result to any fixed graph $$H$$ . Towards this we introduce a notion of $$H$$ -regularity of graphons and show that if the graphon $$W$$ is not $$H$$ -regular, then $$X_n(H, W)$$ has Gaussian fluctuations with scaling $$n^{|V(H)|-\frac{1}{2}}$$ . On the other hand, if $$W$$ is $$H$$ -regular, then the fluctuations are of order $$n^{|V(H)|-1}$$ and the limiting distribution of $$X_n(H, W)$$ can have both Gaussian and non-Gaussian components, where the non-Gaussian component is a (possibly) infinite weighted sum of centred chi-squared random variables with the weights determined by the spectral properties of a graphon derived from $$W$$ . Our proofs use the asymptotic theory of generalised $$U$$ -statistics developed by Janson and Nowicki [22]. We also investigate the structure of $$H$$ -regular graphons for which either the Gaussian or the non-Gaussian component of the limiting distribution (but not both) is degenerate. Interestingly, there are also $$H$$ -regular graphons $$W$$ for which both the Gaussian or the non-Gaussian components are degenerate, that is, $$X_n(H, W)$$ has a degenerate limit even under the scaling $$n^{|V(H)|-1}$$ . We give an example of this degeneracy with $$H=K_{1, 3}$$ (the 3-star) and also establish non-degeneracy in a few examples. This naturally leads to interesting open questions on higher order degeneracies. 

   more » « less