On generalized Erdős–Ginzburg–Ziv constants of Cnr

Let $G$ be an additive finite abelian group with exponent $exp\left(G\right)=n$. For any positive integer $k$, the $k$th Erdős–Ginzburg–Ziv constant ${\mathsf{s}}_{kn}\left(G\right)$ is defined as the smallest positive integer $t$ such that every sequence $S$ in $G$ of length at least $t$ has a zero-sum subsequence of length $kn$. It is easy to see that ${\mathsf{s}}_{kn}\left(C_n^r\right)\ge (k+r)n-r$ where $n,r\in \mathbb{N}$. Kubertin conjectured that the equality holds for any $k\ge r$. In this paper, we prove the following results:

• •[(1)] For every positive integer $k\ge 6$, we have ${\mathsf{s}}_{kn}\left(C_n^3\right)=(k+3)n+O\left(\frac{n}{lnn}\right).$
• •[(2)] For every positive integer $k\ge 18$, we have ${\mathsf{s}}_{kn}\left(C_n^4\right)=(k+4)n+O\left(\frac{n}{lnn}\right).$
• •[(3)] For $n\in \mathbb{N}$, assume that the largest prime power divisor of $n$ is $p^a$ for some $a\in \mathbb{N}$. Forany fixed $r\ge 5$, if $p^t\ge r$ for some $t\in \mathbb{N}$, then for any $k\in \mathbb{N}$ we have ${\mathsf{s}}_{k{p}^{t}n}\left(C_n^r\right)\le (k{p}^t+r)n+c_r\frac{n}{lnn},$where $c_r$ is a constant that depends on $r$.

Our results verify the conjecture of Kubertin asymptotically in the above cases.     

Erdős–Ko–Rado theorems in finite classical polar spaces

Recently, Erdős–Ko–Rado theorems in finite classical polar spaces have been derived. We present the table with the results of Pepe, Storme and Vanhove on the largest Erdős–Ko–Rado sets of generators in the finite classical polar spaces, and other more recent results by De Boeck, Ihringer and Metsch.     

When are stars the largest cross-intersecting families?

We provide a necessary and sufficient condition for stars to be the largest cross-intersecting families.     

A variant of the Erdős-Sós conjecture

A well-known conjecture of Erdős and Sós states that every graph with average degree exceeding $m-1$ contains every tree with $m$ edges as a subgraph. We propose a variant of this conjecture, which states that every graph of maximum degree exceeding $m$ and minimum degree at least $\lfloor 2m/3\rfloor$ contains every tree with $m$ edges. As evidence for our conjecture we show (a) for every $m$ there is a $g\left(m\right)$ such that the weakening of the conjecture obtained by replacing the first $m$ by $g\left(m\right)$ holds, and (b) there is a such that the weakening of the conjecture obtained by replacing $\lfloor 2m/3\rfloor$ by $\text{◂⋅▸}\left(1-\gamma \right)m$ holds.     

Low-discrepancy sequences for piecewise smooth functions on the two-dimensional torus

We produce explicit low-discrepancy infinite sequences which can be used to approximate the integral of a smooth periodic function restricted to a convex domain with positive curvature in ${\mathbb{R}}^2$. The proof depends on simultaneous diophantine approximation and a general version of the Erdős–Turán inequality.     

On the kernel size of clique cover reductions for random intersection graphs

Covering all edges of a graph by a minimum number of cliques is a well known $\mathsf{NP}$-hard problem. For the parameter k being the maximal number of cliques to be used, the problem becomes fixed parameter tractable. However, assuming the Exponential Time Hypothesis, there is no kernel of subexponential size in the worst-case.We study the average kernel size for random intersection graphs with n vertices, edge probability p, and clique covers of size k. We consider the well-known set of reduction rules of Gramm, Guo, Hüffner, and Niedermeier (2009) [17] and show that with high probability they reduce the graph completely if p is bounded away from 1 and $k<c\log n$ for some constant $c>0$. This shows that for large probabilistic graph classes like random intersection graphs the expected kernel size can be substantially smaller than the known exponential worst-case bounds.     

Vertex-minors and the Erdős–Hajnal conjecture

We prove that for every graph $H$, there exists $\epsilon >0$ such that every $n$-vertex graph with no vertex-minors isomorphic to $H$ has a pair of disjoint sets $A$, $B$ of vertices such that $\left|A\right|,\left|B\right|\ge \epsilon n$ and $A$ is complete or anticomplete to $B$. We deduce this from recent work of Chudnovsky, Scott, Seymour, and Spirkl (2018). This proves the analog of the Erd?s–Hajnal conjecture for vertex-minors.     

On the maximum size of connected hypergraphs without a path of given length

In this note we asymptotically determine the maximum number of hyperedges possible in an $r$-uniform, connected $n$-vertex hypergraph without a Berge path of length $k$, as $n$ and $k$ tend to infinity. We show that, unlike in the graph case, the multiplicative constant is smaller with the assumption of connectivity.