KPPY 84

A set $S$ of natural numbers is a Sidon set if all the sums $s_1+s_2$ with $s_1$, $s_2\in S$ and $s_1\leq s_2$ are distinct. Let constants $\alpha>0$ and $0<\delta<1$ be fixed, and let $p_m=\min\{1,\alpha m^{-1+\delta}\}$ for all positive integers $m$. Generate a random set $R\subset\mathbb{N}$ by adding $m$ to $R$ with probability $p_m$, independently for each $m$. We investigate how dense a Sidon set $S$ contained in $R$ can be. Our results show that the answer is qualitatively very different in at least three ranges of $\delta$. We prove quite accurate results for the range $0<\delta\leq2/3$, but only obtain partial results for the range $2/3<\delta\leq1$.

This is joint work with Y. Kohayakawa, C. G. Moreira and V. Rödl.

A colored space is the pair of a set $X$ and a function $r$ whose domain is $\binom{X}{2}$. Let $(X,r)$ be a finite colored space and $Y,Z\subseteq X$. We shall write $Y\simeq_r Z$ if there exists a bijection $f:Y\to Z$ such that $r(U)=r(f(U))$ for each $U\in\binom{Y}{2}$. Notice that, for $U,V\in \binom{X}{2}$, $U\simeq_r V$ if and only if $r(U)=r(V)$, and for $Y,Z\in \binom{X}{3}$, $Y\simeq_r Z$ if and only if $(r(U)\mid U\in \binom{Y}{2})$ is a replacement of $(r(V)\mid V\in \binom{Z}{2})$. We denote the numbers of equivalence classes contained in $\binom{X}{2}$ and $\binom{X}{3}$ by $a_2(r)$ and $a_3(r)$, respectively.

In this talk we aim to classify colored spaces with $a_2(r)=a_3(r)$.

This is a joint work with Masashi Shinohara.

$ \def\cA{\mathcal A} \def\cB{{\mathcal B}} \def\cF{{\mathcal F}} $ For a positive integer $n$ let $[n]:=\{1,2,\ldots,n\}$ and let $\Omega:=2^{[n]}$ denote the power set of $[n]$. A family of subsets ${\mathcal A}\subset \Omega$ is called $t$-intersecting if $|A\cap A'|\geq t$ for all $A,A'\in{\mathcal A}$. Let $p\in(0,1)$ be a fixed real number. We define the product measure $\mu:2^{\Omega}\to[0,1]$ by $\mu(\cA):=\sum_{A\in\cA}p^{|A|}(1-p)^{n-|A|}$ for $\cA\in 2^{\Omega}$. Ahlswede and Khachatrian proved that if \begin{equation*} \frac r{t+2r-1}\leq p\leq \frac{r+1}{t+2r+1} \end{equation*} and $\cA\subset\Omega$ is $t$-intersecting, then $\mu(\cA)\leq\mu(\cF^t_r)$, where $\cF_r^t$ is a $t$-intersecting family defined by $\cF_r^t:=\{F\subset[n]:|F\cap[t+2r]|\geq t+r\}$.

We extend this result to two families. We say that two families $\cA,\cB\subset\Omega$ are cross $t$-intersecting if $|A\cap B|\geq t$ for all $A\in\cA,B\in\cB$. In this case it is conjectured that $\mu(\cA)\mu(\cB)\leq\mu(\cF^t_r)^2$ for $p$ in the range given above. In my talk I will report that this conjecture is true if $t\gg r$. I will also discuss a related stability result.

This is joint work with Sang June Lee and Mark Siggers.

We introduce the notion of effective resistance for a simplicial network $(X,R)$ where $X$ is a simplicial complex and $R$ is a set of resistances for the top simplices, and prove two formulas generalizing previous results concerning effective resistance for resistor networks. Our approach, based on combinatorial Hodge theory, is to assign a unique harmonic class to a current generator $\sigma$, an extra top-dimensional simplex to be attached to $X$. We will show that the harmonic class gives rise to the current $I_{\sigma}$ and the voltage $V_{\sigma}$ for $X\cup\sigma$, satisfying Thompson's energy-minimizing principle and Ohm's law for simplicial networks.

The effective resistance $R_{\sigma}$ of a current generator $\sigma$ shall be defined as a ratio of the $\sigma$-components of $V_{\sigma}$ and $I_{\sigma}$. By introducing potential for voltage vectors, we present a formula for $R_\sigma$ via the inverse of the weighted combinatorial Laplacian of $X$ in codimension one. We also derive a formula for $R_{\sigma}$ via weighted high-dimensional tree-numbers for $X$, providing a combinatorial interpretation for $R_{\sigma}$. As an application, we generalize Foster's Theorem, and discuss various high-dimensional examples.

This is a joint work with Woong Kook.

Let $\Gamma$ be a distance-regular graph with valency $k$ and diameter $D$, and let $x$ be a vertex of $\Gamma.$ We denote by $k_i$ $(0\leq i \leq D)$ the number of vertices at distance $i$ from $x$. In this talk, we try to quantify the difference between antipodal and non-antipodal distance-regular graphs. We will look at the sum $k_{D-1} + k_D$, and consider the situation where $k_{D-1}+k_D\leq 2k$. If $\Gamma$ is an antipodal distance-regular graph, then $k_{D-1} + k_{D} = k_D (k+1)$. It follows that either $k_D =1$ or the graph is non-antipodal. And for a non-antipodal distance-regular graph, it was known that $k_D(k_D-1) \geq k$ and $k_{D-1} \geq k$ both hold. So, this talk concerns on obtaining more detailed information on the number of vertices for a non-antipodal distance-regular graph. We first concentrate on the case where the diameter equals three. In this case, the condition $k_D + k_{D-1} \leq 2k$ is equivalent to the condition that the number of vertices is at most $3k+1$. And we extend this result to all diameters. We note that although the result of the diameter $3$ case is a corollary of the result of all diameters, the main difficulty is the diameter $3$ case, and that the diameter $3$ case confirms the following conjecture: there is no primitive distance-regular graph with diameter $3$ having the $M$-property.