Joint Poisson Convergence of Monochromatic Hyperedges in Multiplex Hypergraphs

Yangxinyu Xie, Bhaswar B. Bhattacharya · 2024

Read Joint Poisson Convergence of Monochromatic Hyperedges in Multiplex Hypergraphs by Yangxinyu Xie, Bhaswar B. Bhattacharya (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-00610.txt.

Introduction

Yangxinyu Xie and Bhaswar Bhattacharya study same-color hyperedges in layered hypergraphs in a 2024 paper. Color the corners of a hypergraph at random, and count the hyperedges that end up all one color. When a hypergraph has several layers sharing the same corners, the counts for each layer form a pair whose joint behavior matters.

The authors prove the pair settles into Poisson distributions, possibly linked ones, whenever the mean vector and covariance matrix of the counts settle down. Only the first two moments decide the limit, a broad second-moment principle. The result extends earlier work from graphs to hypergraphs and from single counts to joint ones, with applications to the birthday problem and random coloring counts.

Catalog record

CREATORYangxinyu Xie, Bhaswar B. Bhattacharya
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE95 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-00610

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Joint Poisson Convergence of Monochromatic Hyperedges in Multiplex Hypergraphs Yangxinyu Xie, Bhaswar B. Bhattacharya Abstract . Given a sequence of r r -uniform hypergraphs H n H_{n} , denote by T ⁡ ( H n ) T(H_{n}) the number of monochromatic hyperedges when the vertices of H n H_{n} are colored uniformly at random with c = c n c=c_{n} colors. In this paper, we study the joint distribution of monochromatic hyperedges for hypergraphs with multiple layers (multiplex hypergraphs). Specifically, we consider the joint distribution of 𝑻 n := ( T ⁡ ( H n ( 1 ) ) , T ⁡ ( H n ( 2 ) ) ) \bm{T}_{n}:=(T(H_{n}^{(1)}),T(H_{n}^{(2)})) , for two sequences of hypergraphs H n ( 1 ) H_{n}^{(1)} and H n ( 2 ) H_{n}^{(2)} on the same set of vertices. We will show that the joint distribution of 𝑻 n \bm{T}_{n} converges to (possibly dependent) Poisson distributions whenever the mean vector and the covariance matrix of 𝑻 n \bm{T}_{n} converge. In other words, the joint Poisson approximation of 𝑻 n \bm{T}_{n} is determined only by the convergence of its first two moments. This generalizes recent results on the second moment phenomenon for Poisson approximation from graph coloring to hypergraph coloring and from marginal convergence to joint convergence. Applications include generalizations of the birthday problem, counting monochromatic subgraphs in randomly colored graphs, and counting monochromatic arithmetic progressions in randomly colored integers. Extensions to random hypergraphs and weighted hypergraphs are also discussed. 2010 Mathematics Subject Classification 05C15, 60C05, 60F05 1. Introduction Fix r\geq 2 and consider a sequence of r -uniform hypergraphs H_{n}=(V(H_{n}),E(H_{n})) , with vertex set V(H_{n}) and hyperedge set E(H_{n}) such that |E(H_{n})|\rightarrow\infty , as n\rightarrow\infty . Suppose the vertices of H_{n} are colored uniformly at random with c=c_{n} colors, that is, \displaystyle\mathbb{P}(v\in V(H_{n})\text{ has color }a\in\{1,2,\ldots,c_{n}\})=\frac{1}{c_{n}}, (1.1) independently from the other vertices. Given such a coloring a hyperedge \bm{e}\in E(H_{n}) is said to be monochromatic if all the vertices in \bm{e} have the same color. Formally, if X_{v} denotes the color of the vertex v\in V(H_{n}) , then an edge \bm{e}\in E(H_{n}) is monochromatic if X_{v}=X_{v^{\prime}} , for all v,v^{\prime}\in\bm{e} . Denote by T(H_{n}) the number of monochromatic hyperedges in H_{n} , that is, T(H_{n}):=\sum_{\bm{e}\in E(H_{n})}\bm{1}\{X_{=\bm{e}}\}, (1.2) where \bm{1}\{X_{=\bm{e}}\}:=\bm{1}\{X_{v}=X_{v^{\prime}}\text{ for all }v,v^{\prime}\in\bm{e}\} . This general framework includes numerous celebrated problems in combinatorial probability. The following are three examples: Example 1.1 (Birthday Problem) . When r=2 , then H_{n} is a graph and T(H_{n}) counts the number of monochromatic edges in a uniformly random coloring of the vertices of H_{n} . Specifically, if H_{n} is a friendship-graph (two people are connected by an edge in the graph if they are friends) colored uniformly randomly with c=365 colors (where the colors correspond to birthdays and the birthdays are assumed to be uniformly distributed across the year), then a monochromatic edge in H_{n} corresponds to two friends with the same birthday. The birthday problem asks for the probability that there are two friends with the same birthday, that is, \mathbb{P}(T(H_{n})>0) . This is one of the most famous problems in elementary probability, which has been generalized in various directions and found applications in diverse fields (see [ 4 , 21 , 22 , 23 , 38 , 25 , 32 , 17 ] and the references therein). Note that \mathbb{P}(T(H_{n})>0)=1-\mathbb{P}(T(H_{n})=0)=1-\chi_{H_{n}}(c)/c^{|V(H_{n})|} , where \chi_{H_{n}}(c) counts the number of proper colorings of H_{n} using c colors. The function \chi_{H_{n}} is known as the chromatic polynomial of H_{n} , a central object of study in graph theory [ 24 , 29 , 30 , 38 , 45 ] . A natural generalization of the birthday problem is to consider higher-order birthday matches; that is, the probability that there is a group of r friends sharing the same birthday [ 23 , 39 , 37 , 43 ] . This corresponds to counting the number of r -cliques in H_{n} [ 11 ] , which can be reformulated in terms of ( 1.2 ) as follows: Consider the r -uniform hypergraph {\mathcal{C}}_{r}(H_{n})=(V({\mathcal{C}}_{r}(H_{n})),E({\mathcal{C}}_{r}(H_{n}))) , with V({\mathcal{C}}_{r}(H_{n}))=V(H_{n}) and E({\mathcal{C}}_{r}(H_{n}))=\left\{S\in{V(H_{n})\choose r}:S\text{ forms a }r\text{-clique in }H_{n}\right\}, where {V(H_{n})\choose r} denotes the collection of all r -element subsets of V(H_{n}) . Then T({\mathcal{C}}_{r}(H_{n})) is precisely the number of monochromatic r -cliques (the number of r -th order birthday matches) in H_{n} . Example 1.2 (Monochromatic subgraphs in random edge colorings) . Understanding the existence of monochromatic subgraphs in edge-colored graphs is one of the basic objectives in Ramsey theory [ 28 , 19 ] . Specifically, Ramsey’s theorem in its graph theoretic form, states that given a graph F=(V(F),E(F)) , any c -coloring of the edges of a complete graph K_{n} contains a monochromatic copy of F , whenever n is large enough (depending on c and F ). Although Ramsey’s theorem is a statement about any coloring, understanding what happens for a random coloring has important consequences. For instance, when c=2 , for certain graphs F (which are known as common graphs) the number of monochromatic copies of F is asymptotically minimized by a random edge-coloring (see [ 27 , 16 ] and the references therein). Going beyond complete graphs to a general graph sequence G_{n}=(V(G_{n}),E(G_{n})) , with |E(G_{n})|\rightarrow\infty , one can define R(F,G_{n}) as the number of monochromatic copies of F when the edges of G_{n} are colored uniformly at random with c -colors. 1 1 1 In a uniformly random edge coloring of a graph G_{n}=(V(G_{n}),E(G_{n})) with c colors, each edge e\in E(G_{n}) has color a\in\{1,2,\ldots,c\} with probability 1/c , independent of the other edges. This can be expressed in terms of ( 1.2 ) as follows: Consider the |E(F)| -uniform hypergraph H_{G_{n}}(F)=(V(H_{G_{n}}(F)),E(H_{G_{n}}(F))) , where V(H_{G_{n}}(F))=E(G_{n}) and E(H_{G_{n}}(F)) is the collection of |E(F)| -element subsets of E(G_{n}) that form a copy of F in G_{n} . Note that a uniformly random edge-coloring of the graph G_{n} corresponds to a uniformly random vertex coloring of the hypergraph H_{G_{n}}(F) , and hence, T(H_{G_{n}}(F))=R(F,G_{n}) . Example 1.3 (Monochromatic arithmetic progressions) . Another key result in Ramsey theory is Van der Waerden’s theorem [ 44 , 28 ] , which states that given positive integers c\geq 2 and r\geq 3 , any c -coloring of the integers [n]:=\{1,2,\ldots,n\} contains a monochromatic r -term arithmetic progression ( r -AP), that is, r equally spaced integers of the same color, when n is sufficiently large (depending on r and c ). As in the graph theoretic setting, counting the number of monochromatic arithmetic progressions in a random coloring have important consequences (see [ 41 ] and the references therein). Thus, for any set A_{n}\subseteq[n] , with |A_{n}|\rightarrow\infty , we can define W_{r}(A_{n}) to be the number of monochromatic arithmetic progressions in a random c -coloring of the elements of A_{n} . To express W_{r}(A_{n}) as ( 1.2 ) consider the hypergraph H_{A_{n}}(r) with vertex set A_{n} and edge set the collection of all r -term APs in A_{n} . Then T(H_{A_{n}}(r))=W_{r}(A_{n}) . In this paper we will study the limiting distribution of T(H_{n}) in the regime where both |E(H_{n})|\rightarrow\infty and c=c_{n}\rightarrow\infty such that \displaystyle\mathbb{E}T(H_{n})=\frac{1}{c_{n}}|E(H_{n})|\to\lambda\geq 0. (1.3) This problem is well understood when r=2 , that is, when H_{n} is a graph and T(H_{n}) counts the number of

Read the complete text