Efficient counting of degree sequences

We present formulas to count the set $D_0\left(n\right)$ of degree sequences of simple graphs of order $n$, the set $D\left(n\right)$ of degree sequences of those graphs with no isolated vertices, and the set $D_{k\text{\_}con}\left(n\right)$ of degree sequences of those graphs that are $k$-connected for fixed $k$. The formulas all use a function of Barnes and Savage and the associated dynamic programming algorithms all run in time polynomial in $n$ and are asymptotically faster than previous known algorithms for these problems. We also show that $\left|D\left(n\right)\right|$ and $\left|D_{1\text{\_}con}\left(n\right)\right|$ are asymptotically equivalent but $\left|D\left(n\right)\right|$ and $\left|D_0\left(n\right)\right|$ as well as $\left|D\left(n\right)\right|$ and $\left|D_{k\text{\_}con}\left(n\right)\right|$ with fixed $k\ge 2$ are asymptotically inequivalent. Finally, we explain why we are unable to obtain the absolute asymptotic orders of these functions from their formulas.     

Monochromatic subgraphs in randomly colored graphons

Let $T(H,G_n)$ be the number of monochromatic copies of a fixed connected graph $H$ in a uniformly random coloring of the vertices of the graph $G_n$. In this paper we give a complete characterization of the limiting distribution of $T(H,G_n)$, when ${\left\{G_n\right\}}_{n\ge 1}$ is a converging sequence of dense graphs. When the number of colors grows to infinity, depending on whether the expected value remains bounded, $T(H,G_n)$ either converges to a finite linear combination of independent Poisson variables or a normal distribution. On the other hand, when the number of colors is fixed, $T(H,G_n)$ converges to a (possibly infinite) linear combination of independent centered chi-squared random variables. This generalizes the classical birthday problem, which involves understanding the asymptotics of $T(K_s,K_n)$, the number of monochromatic $s$-cliques in a complete graph $K_n$ ($s$-matching birthdays among a group of $n$ friends), to general monochromatic subgraphs in a network.     

Turán numbers for Berge-hypergraphs and related extremal problems

Let $F$ be a graph. We say that a hypergraph $H$ is a Berge-$F$ if there is a bijection $f:E\left(F\right)\to E\left(H\right)$ such that $e?f\left(e\right)$ for every $e\in E\left(F\right)$. Note that Berge-$F$ actually denotes a class of hypergraphs. The maximum number of edges in an $n$-vertex $r$-graph with no subhypergraph isomorphic to any Berge-$F$ is denoted ${\mathrm{ex}}_r(n,\text{Berge-}F)$. In this paper, we investigate the case when $F=K_{s,t}$ and establish an upper-bound when $r\ge 3$, and a lower-bound when $r=4$ and $t$ is large enough compared to $s$. Additionally, we prove a counting result for $r$-graphs of girth five that complements the asymptotic formula ${\text{ex}}_3(n,\text{Berge-}\{C_2,C_3,C_4\})=\frac{1}{6}{n}^{3∕2}+o\left(n^{3∕2}\right)$ of Lazebnik and Verstraëte (2003).     

Extremal general affine surface areas

For a convex body K in ${\mathbb{R}}^n$, we introduce and study the extremal general affine surface areas, defined by${\mathrm{\text{IS}}}_{\phi }(K):=\underset{K^{\prime }?K}{\sup }?{\mathrm{as}}_{\phi }(K),{\mathrm{\text{os}}}_{\psi }(K):=\underset{K^{\prime }?K}{\inf }?{\mathrm{as}}_{\psi }(K)$ where ${\mathrm{as}}_{\phi }(K)$ and ${\mathrm{as}}_{\psi }(K)$ are the $L_{\phi }$ and $L_{\psi }$ affine surface area of K, respectively. We prove that there exist extremal convex bodies that achieve the supremum and infimum, and that the functionals ${\mathrm{\text{IS}}}_{\phi }$ and ${\mathrm{\text{os}}}_{\psi }$ are continuous. In our main results, we prove Blaschke-Santaló type inequalities and inverse Santaló type inequalities for the extremal general affine surface areas. This article may be regarded as an Orlicz extension of the recent work of Giladi, Huang, Schütt and Werner (2020), who introduced and studied the extremal $L_p$ affine surface areas.     

The combinatorial properties of the Benoumhani polynomials for the Whitney numbers of Dowling lattices

In the papers (Benoumhani 1996;1997), Benoumhani defined two polynomials $F_{m,n,1}\left(x\right)$ and $F_{m,n,2}\left(x\right)$. Then, he defined $A_m(n,k)$ and $B_m(n,k)$ to be the polynomials satisfying $F_{m,n,1}\left(x\right)={\sum }_{k=0}^n{A}_m(n,k)x^{n?k}{(x+1)}^k$ and $F_{m,n,1}\left(x\right)={\sum }_{k=0}^n{B}_m(n,k)x^{n?k}{(x+1)}^k$. In this paper, we give a combinatorial interpretation of the coefficients of $A_{m+1}(n,k)$ and prove a symmetry of the coefficients, i.e., $\left[m^s\right]A_{m+1}(n,k)=\left[m^{n?s}\right]A_{m+1}(n,n?k)$. We give a combinatorial interpretation of $B_{m+1}(n,k)$ and prove that $B_{m+1}(n,n?1)$ is a polynomial in $m$ with non-negative integer coefficients. We also prove that if $n\ge 6$ then all coefficients of $B_{m+1}(n,n?2)$ except the coefficient of $m^{n?1}$ are non-negative integers. For all $n$, the coefficient of $m^{n?1}$ in $B_{m+1}(n,n?2)$ is $?(n?1)$, and when $n\le 5$ some other coefficients of $B_{m+1}(n,n?2)$ are also negative.     

Learning from MOM’s principles: Le Cam’s approach

New robust estimators are introduced, derived from median-of-means principle and Le Cam’s aggregation of tests. Minimax sparse rates of convergence are obtained with exponential probability, under weak moment’s assumptions and possible contamination of the dataset. These derive from general risk bounds of the following informal structure $max\left(\text{minimax rate in the i.i.d. setup},\frac{\text{number of outliers}}{\text{number of observations}}\right).$In this result, the number of outliers may be as large as (number of data)$\times$(minimax rate) without affecting the rates. As an example, minimax rates $slog(ed∕s)∕N$ of recovery of $s$-sparse vectors in ${\mathbb{R}}^d$ holding with exponentially large probability, are deduced for median-of-means versions of the LASSO when the noise has $q_0$ moments for some $q_0>2$, the entries of the design matrix have $C_{0}log\left(ed\right)$ moments and the dataset is corrupted by up to $C_{1}slog(ed∕s)$ outliers.     

No-three-in-line problem on a torus: Periodicity

Let ${\tau }_{m,n}$ denote the maximal number of points on the discrete torus (discrete toric grid) of sizes $m\times n$ with no three collinear points. The value ${\tau }_{m,n}$ is known for the case where $gcd(m,n)$ is prime. It is also known that ${\tau }_{m,n}\le 2gcd(m,n)$. In this paper we generalize some of the known tools for determining ${\tau }_{m,n}$ and also show some new. Using these tools we prove that the sequence ${\left({\tau }_{z,n}\right)}_{n\in \mathbb{N}}$ is periodic for all fixed $z>1$. In general, we do not know the period; however, if $z=p^a$ for $p$ prime, then we can bound it. We prove that ${\tau }_{p^a,p^{(a?1)p+2}}=2p^a$ which implies that the period for the sequence is $p^b$, where $b$ is at most $(a?1)p+2$.     

On the k-planar local crossing number

Given a fixed positive integer $k$, the $k$-planar local crossing number of a graph $G$, denoted by ${\text{<mi mathsize="small" is="true">LCR</mi>}}_k\left(G\right)$, is the minimum positive integer $L$ such that $G$ can be decomposed into $k$ subgraphs, each of which can be drawn in a plane such that no edge is crossed more than $L$ times. In this note, we show that under certain natural restrictions, the ratio ${\text{<mi mathsize="small" is="true">LCR</mi>}}_k\left(G\right)∕{\text{<mi mathsize="small" is="true">LCR</mi>}}_1\left(G\right)$ is of order $1∕k^2$, which is analogous to the result of Pach et al. (2018) for the $k$-planar crossing number ${\text{<mi mathsize="small" is="true">CR</mi>}}_k\left(G\right)$ (defined as the minimum positive integer $C$ for which there is a $k$-planar drawing of $G$ with $C$ total edge crossings). As a corollary of our proof we show that, under similar restrictions, one may obtain a $k$-planar drawing of $G$ with both the total number of edge crossings as well as the maximum number of times any edge is crossed essentially matching the best known bounds. Our proof relies on the crossing number inequality and several probabilistic tools such as concentration of measure and the Lovász local lemma.     

Separable discrete functions: Recognition and sufficient conditions

A discrete function of $n$ variables is a mapping $g:X_1\times \dots \times X_n\to A$, where $X_1,\dots ,X_n$, and $A$ are arbitrary finite sets. Function $g$ is called separable if there exist $n$ functions $g_i:X_i\to A$ for $i=1,\dots ,n$, such that for every input $x_1,\dots ,x_n$ the function $g(x_1,\dots ,x_n)$ takes one of the values $g_1\left(x_1\right),\dots ,g_n\left(x_n\right)$. Given a discrete function $g$, it is an interesting problem to ask whether $g$ is separable or not. Although this seems to be a very basic problem concerning discrete functions, the complexity of recognition of separable discrete functions of $n$ variables is known only for $n=2$. In this paper we will show that a slightly more general recognition problem, when $g$ is not fully but only partially defined, is NP-complete for $n\ge 3$. We will then use this result to show that the recognition of fully defined separable discrete functions is NP-complete for $n\ge 4$.The general recognition problem contains the above mentioned special case for $n=2$. This case is well-studied in the context of game theory, where (separable) discrete functions of $n$ variables are referred to as (assignable) $n$-person game forms. There is a known sufficient condition for assignability (separability) of two-person game forms (discrete functions of two variables) called (weak) total tightness of a game form. This property can be tested in polynomial time, and can be easily generalized both to higher dimension and to partially defined functions. We will prove in this paper that weak total tightness implies separability for (partially defined) discrete functions of $n$ variables for any $n$, thus generalizing the above result known for $n=2$. Our proof is constructive. Using a graph-based discrete algorithm we show how for a given weakly totally tight (partially defined) discrete function $g$ of $n$ variables one can construct separating functions $g_1,\dots ,g_n$ in polynomial time with respect to the size of the input function.     

Stable-like fluctuations of Biggins’ martingales

Let ${\left(W_n\left(\theta \right)\right)}_{n\in {\mathbb{N}}_0}$ be Biggins’ martingale associated with a supercritical branching random walk, and let $W\left(\theta \right)$ be its almost sure limit. Under a natural condition for the offspring point process in the branching random walk, we show that if the law of $W_1\left(\theta \right)$ belongs to the domain of normal attraction of an $\alpha$-stable distribution for some $\alpha \in (1,2)$, then, as $n\to \infty$, there is weak convergence of the tail process ${(W\left(\theta \right)?W_{n?k}\left(\theta \right))}_{k\in {\mathbb{N}}_0}$, properly normalized, to a random scale multiple of a stationary autoregressive process of order one with $\alpha$-stable marginals.