User sergey norin - MathOverflow

Answer by Sergey Norin for Maximum number of edges $f(n,k)$ in a graph on $n$ vertices with no $k$-core?

2013-03-01T18:42:33Z

$$f(n,k)= (n-k)(k-1)+\frac{k(k-1)}{2}, \; \mathrm{for} \; n \geq k, $$ $$f(n,k) = \frac{n(n-1)}{2}, \; \mathrm{for} \; n \leq k. $$

Proof: Every graph with no $k$-core on $n$ vertices contains a vertex of degree $\leq k-1$ which one can delete, obtaining a graph with no $k$-core. Thus $$f(n,k) \leq f(n-1,k) + k-1.$$

The formula now follows by induction. In the base case $n \leq k$ the formula gives the number of edges in the complete graph.

For an example that the bound can be achieved, let $G$ be a graph with $V(G) = \{1,2, \ldots, n \}$ and let the vertices $i$ and $j$ be adjacent if and only if $|i-j| < k$. It is easy to check that $G$ has no $k$-core and has the right number of edges.

Answer by Sergey Norin for Most inconsistent ranking

2013-02-19T19:44:45Z

$\newcommand{\E}{\mathrm{E}}$ $\newcommand{\Var}{\mathrm{Var}}$ $\newcommand{\Cov}{\mathrm{Cov}}$ Extending Kevin's answer let me show that

$$S_{k,n} \leq \frac{k^3-k}{12}.$$

It is easy to see that $$\Var(X) \leq \E[(X-c)^2]$$ for any random variable $X$ and any constant $c$.

Let $a_{i,j}$ denote the entry of the matrix on the intersection of $i^\mathrm{th}$ row and $j^\mathrm{th}$ column. Let $R_i$ (resp. $C_j$) be the random variables corresponding to uniformly sampling entries of $i^\mathrm{th}$ row (resp. $j^\mathrm{th}$ column). Then

\begin{align*} S_{k,n} &= \max \sum_{i=1}^k \Var(R_i) \leq \sum_{i=1}^k \E[(R_i - \frac{k+1}{2})^2]=\frac{1}{n}\sum_{1\leq i \leq k, 1 \leq j \leq n} ( a_{ij}-(k+1)/2)^2 \newline &= \frac{k}{n}\sum_{j=1}^n \Var(C_j)= \frac{k}{n} \cdot n \cdot \frac{k^2-1}{12} \end{align*}

It is clear that the bound is achieved if and only if the average value of each row is $(k+1)/2$. Examples with this property can be constructed for all even $n$. It is also easy to see that for fixed $k$ and $n \to \infty$ one can make the row averages be arbitrarily close to $(k+1)/2$ and thus the total variance arbitrarily close to the upper bound.

If $k$ is even and $n$ is odd then the bound can not be achieved exactly, as $n(k+1)/2$ is not integral. When $k$ is odd and $n=3$ then one can have $i^\mathrm{th}$ row consisting of $$\langle i; (i + (k-1)/2) \:\mathrm{mod}\: k; (k-2i +2) \:\mathrm{mod}\: k \rangle.$$ Combining this construction with pairs of ``reverse" columns, one achieves the bound for all $n \geq 3$. To summarize:

$\max S_{k,n} = \frac{k^3-k}{12}$, when $n$ is even, or $k$ is odd and $n \geq 3$;

$\max S_{k,n} < \frac{k^3-k}{12}$, otherwise, but $\lim_{n \to \infty} \max S_{k,n}=\frac{k^3-k}{12}$ for all $k$.

Answer by Sergey Norin for Is the empty graph a tree?

2013-02-01T20:15:37Z

In a paper ``Is the null-graph a pointless concept?" Harary and Read examine reasons for assigning certain properties to the empty graph. They observe that from the enumeration perspective it appears to be convenient to consider the empty graph as a forest, but not a tree.

Answer by Sergey Norin for Erdős-Szekeres for first differences

2012-03-13T22:04:57Z

For brevity let me call a sequence with non-decreasing first differences convex, and a sequence with non-increasing first differences concave.

Let $M(r,s)$ denote the minimum integer $N$ so that every $N$-element sequence of real numbers contains a convex subsequence of length $r+1$ or a concave subsequence of length $s+1$. Below I attempt to show that

$$M(r,s)=\binom{r+s-2}{r-1}+1.$$

The lower bound: Let $[m]$ denote the set $\{1,\ldots,m\}$.

For $S \subseteq [r+s-2]$, let $x_S := \sum_{i \in S}3^i$. Consider the sequence $(x_S\;|\; S \subseteq [r+s-2], |S|=s-1)$ with elements in increasing order. It has $\binom{r+s-2}{r-1}$ elements. We will show that this sequence contains no convex subsequence of length $r+1$ and no concave subsequence of length $s+1$.

Let $x_{S_1},x_{S_2}, \ldots,x_{S_n}$ be a convex subsequence. Let $d_i$ be the maximum element of $S_{i+1} \setminus S_{i}$. Then $ 3^{d_i}/2 < x_{S_{i+1}}-x_{S_i}< 3^{d_i+1}/2.$ It follows that $(d_1,d_2,\ldots,d_{n-1})$ is a strictly increasing sequence, and that $d_i \not \in S_1$ for $i \in [n-1]$. Therefore $n \leq r$ as desired.

The proof showing that there is no concave subsequence of length $s+1$ is symmetric. (One can replace $x_{S_i}$ by $x_{[r+s-2]}-x_{S_i}$.)

The upper bound: The goal is to imitate the elegant pigeonhole argument of Seidenberg for Erdős-Szekeres theorem. (See e.g. Wikipedia.)

Let $N = \binom{r+s-2}{r-1}+1$. Let ${\bf a}=(a_1,\ldots, a_N)$ be a sequence.

For $i \in [N]$ and $k \in [r-1]$ let $\alpha_i(k)$ be the minimum real number so that a $(k+1)$-term convex subsequence of ${\bf a}$ ending with $a_i$ has $\alpha_i(k)$ as the difference of the last two terms. Set $\alpha_i(k)=+\infty$ if no such subsequence exists. Note that for fixed $i$ the sequence $\alpha_i(\cdot)$ is non-decreasing.

Analogously, for $k \in [s-1]$ we define $\beta_i(k)$ to be the maximum real number so that a $(k+1)$-term concave subsequence of ${\bf a}$ ending with $a_i$ has $\beta_i(k)$ as the difference of the last two terms. Set $\beta_i(k)=-\infty$ if no such subsequence exists. The sequence $\beta_i(\cdot)$ is non-increasing.

For given $i$ arrange the elements of the multiset ${\alpha_i(1),\ldots, \alpha_i(r-1),\beta_i(1),\ldots,\beta_i(s-1)}$ in increasing order, with alphas preceding betas, when the values are the same. Now we consider the resulting sequence as a sequence of $r+s-2$ symbols each of which is either $\alpha$ or $\beta$, ignoring the indexing. Call this sequence $\bf \chi_i$. For example, we always have $${\bf \chi_1}=(\beta, \ldots,\beta, \alpha, \ldots, \alpha),$$ $${\bf \chi_2}=(\beta,\ldots,\beta, \alpha, \beta, \alpha, \ldots, \alpha),$$ and ${\bf \chi_3}$ depends on $a_1$, $a_2$ and $a_3$.

There are $N-1$ possible sequences and by pigeonhole principle we have ${\bf \chi_i}={\bf \chi_j}$ for some $1 \leq i < j \leq N$. Let $z=a_j-a_i$. Let $r'$ be chosen to be maximum so that $\alpha_{i}(r') \leq z$, and let $r'=0$ if no such $r'$ exists. Let $s'$ be chosen to be maximum so that $\beta_{i}(s') \geq z$, and let $s'=0$ if no such $s'$ exists. Note that $\alpha_{j}(r'+1) \leq z$ and $\beta_{j}(s'+1) \geq z$. If $r'=r-1$ or $s'=s-1$ then $\bf{a}$ contains a convex subsequence of length $r+1$ or a concave subsequence of length $s+1$ as desired. Otherwise, $r'+1$ alphas precede $s'+1$ betas in $\chi_j$, while in $\chi_i$ after the first $r'+1$ alphas we encounter only $\leq s'$ betas. This contradiction finishes the proof.

Answer by Sergey Norin for Induced Paths of Order 4

2012-03-12T20:47:16Z

The question appears to be difficult. The best lower bound that I am aware of is still the one provided by the question author in 1986:

$$\frac{960}{4877}\binom{n}{4}\sim 0.19684\binom{n}{4}.$$

An upper bound is referred to in the paper ``The Inducibility of Graphs on Four Vertices" by James Hirst. It is

$$\sim 0.2064 \left( \binom{n}{4} + o(n^4)\right).$$

The bound is obtained via semi-definite programming using the flag algebra technique. This method was introduced by Razborov in 2007 and it can be used to automatically produce upper bounds on asymptotic number of induced configurations in graphs and hypergraphs. These bounds are occasionally tight. In particular, James Hirst in the paper linked above deduces asymptotically tight upper bounds on the number of induced subgraphs on $4$ vertices of any fixed type, except for the $4$ vertex path.

Answer by Sergey Norin for A "rewiring process" on graphs

2011-11-14T20:43:52Z

As Barry Cipra points out in his answer, the rewiring process continues as long as the graph contains some path $hijk$, such that $hj$ and $ik$ are not the edges of the graph. Equivalently, the terminal graphs are exactly the graphs which contain no induced subgraphs isomorphic to the $3$-edge path $P_4$ or to the $4$-cycle $C_4$. Such graphs have been studied before under the name trivially perfect graphs, and the Wikipedia page contains a number of equivalent characterizations of graphs in this class.

Answer by Sergey Norin for Red-blue alternating Menger's theorem

2011-10-11T19:02:12Z

It seems that the problem of determining whether there exist $2$ vertex disjoint red-blue alternating paths joining vertices $s$ and $t$ is NP-complete. Thus, unless NP $=$ co-NP, there exist no efficient characterization of obstructions to existence of such paths, similar to the one you propose in the lemma.

Below is a reduction to the classical result of Fortune, Hopcroft and Wyllie that the DIRECTED $2$-LINKAGE problem is NP-complete. ( Given a digraph $D$ and four distinct vertices $u_1,v_1,u_2,v_2$; does $D$ contain a pair of vertex-disjoint paths $P_1, P_2$, so that $P_i$ is a directed path from $u_i$ to $v_i$ for $i=1,2$?)

Given a digraph $D$, we replace every directed edge $e=xy$ of $D$ by a vertex $w_e$ joined to $x$ by a red edge and to $y$ by a blue edge. Then we add vertex $s$ joined by a blue edge to $u_1$ and by a red edge to $v_2$, and a vertex $t$ joined by a blue edge to $u_2$ and a red edge to $v_1$. It is not hard to see that a pair of vertex disjoint paths from $s$ to $t$ in the new graph corresponds exactly to the $2$-linkage as described above.

Answer by Sergey Norin for Open problems with monetary rewards

2011-05-30T18:19:34Z

Gerard Cornuejols offers $5000 for the first proof (or refutation) of each of the 18 conjectures in his 2001 book "Combinatorial Optimization: Packing and Covering". Six of the conjectures have been resolved so far, five - by Maria Chudnovsky, Paul Seymour and coauthors.

Answer by Sergey Norin for Upper bounds on number of vertices of graphs whose complements has no induced cycles of certain lengths

2011-05-26T21:22:03Z

Excluding induced matching of size $2$ appears to be the most restrictive condition and the bound is independent on $l$:

(a) Let $G$ be a connected graph with maximum degree $d$ and no induced matching of size $2$. Then $|V(G)| \leq \lfloor\frac{d+2}{2} \rfloor \lceil \frac{d+2}{2}\rceil$.

(b) For every $d \geq 1$ there exists a connected graph $G$ with maximum degree $d$, every induced cycle in the complement of $G$ of length $3$, and $|V(G)| = \lfloor\frac{d+2}{2} \rfloor \lceil \frac{d+2}{2}\rceil.$

(Updated 5/27/11 to extend the proof to $l=4$.)

Proof: (a) Let $M$ be a maximum (non-induced) matching in $G$ chosen so that the sum of degrees of vertices of $M$ in $G$ is minimal. Let $M$ consist of $m$ edges, let $X:=V(M)$ and let $Y:=V(G)-X$. Note that:

(i) $Y$ is an independent set. (Vertices of $Y$ are pairwise non-adjacent as $M$ is maximal.)

(ii) If $v \in Y$ is adjacent to $u \in X$ and $uw \in M$ is the matching edge incident to $u$ then $\deg(v) \geq \deg(w)$, as otherwise replacing $uw$ by $uv$ in $M$ decreases the sum of degrees of vertices in $M$.

(iii) For every $uw \in M$ at least $m-1$ edges incident with $u$ or $w$ have the other end in $X$, not counting $uw$. (There must be an edge between $uw$ and any other edge in $M$, as otherwise these two edges will form an induced matching.)

Let $n:=|V(G)|$. We use (i),(ii) and (iii) in a counting argument, which is described in terms of discharging as follows. Let every vertex in $Y$ start with a charge $1$. Then the total charge is $|Y|=n-2m$. In a discharging step let every vertex $v \in Y$ distribute its charge uniformly among its neighbors, which are all in $X$ by (i). (Every $v \in Y$ sends a charge $1/\deg(v)$ to each of its neighbors.)

The ends of some edge $uw \in M$ must as a result receive total charge at least $(n-2m)/m$. Let $d_1 :=\deg(u)$, $d_2 :=\deg(w)$ and suppose that $d_1 \geq d_2$, without loss of generality. By (ii) the charge that $u$ and $w$ receive from any single vertex in $Y$ is no greater than $1/d_2$. Finally, by (iii) there are at most $d_1+d_2 - 2 - (m-1)$ neighbors of $u$ and $w$ in $Y$. We get $$ \frac{n-2m}{m} \leq \frac{1}{d_2}\left( d_1+d_2 -m -1\right).$$ It is easy to see that the right side is maximized when $d_1=d$ and $d_2=1$. With these choices of degrees we have $$ n \leq 2m + (d-m)m=(d+2-m)m \leq \lfloor\frac{d+2}{2} \rfloor \lceil \frac{d+2}{2}\rceil.$$

(b) One can extract an example achieving the bound from the above argument. Let $G$ consist of a set of $\lfloor \frac{d+2}{2} \rfloor$ pairwise adjacent vertices, each of which is joined to $\lceil \frac{d}{2} \rceil$ additional degree one vertices. Then the complement of $G$ consists of a clique and $\lfloor \frac{d+2}{2} \rfloor$ pairwise non-adjacent vertices only having neighbors in this clique. From this description it is not hard to see that all induced cycles in the complement of $G$ are of length $3$.

Answer by Sergey Norin for Maximal number of directed edges in suitable simple graphs on $n$ vertices without directed triangles.

2011-04-12T20:11:01Z

Updated 4/17/11:

(Originally, this answer contained a different proof of the result below for $k=3$. Not only did the proof not generalize, but it was wrong.)

The maximum number of edges in a strongly-connected digraph with $n \geq k+1$ vertices and no cycles of length at most $k$ is $${\binom{n}{2}} - n(k-2) + \frac{(k+1)(k-2)}{2}.$$ (A digraph where every vertex is reachable from every other vertex by a directed path is called strongly connected.)

Gordon Royle conjectured this bound an gave an example achieving it for $k=3$. For general $k$ and $n$ the bound is attained by the following construction, almost identical to the one provided by Nathann Cohen in the comments:

Let vertices $x_1,x_2,\ldots,x_{n-k+2}$ form a transitive tournament with $x_i \to x_j$ being an edge for all $1 \leq i < j \leq n-k+2$. Now delete the edge $x_1 \to x_{n-k+2}$ and replace it with a path $x_{n-k+2} \to x_{n-k+3} \to \ldots \to x_n \to x_1$. (The vertices $x_{n-k+3},\ldots, x_n$ will have in-degree one and out-degree one in the resulting graph.)

It remains to prove that the above number is a valid upper bound. The proof is by induction on $n$.

Simple counting shows that the bound is valid if $G$ is a directed cycle. It is tight if $G$ is a cycle of length $k+1$. Assume now that $G$ is not a cycle. Then there exist $\emptyset \neq X \subsetneq V(G)$ such that $G|X$ is strongly connected. (For example, one can choose the vertex set of any induced cycle in $G$.) Choose $X$ maximal subject to the above. Let $u \to v_1$ be an edge of $G$ with $u \in X$, $v_1 \not \in X$, and let $P$ be a shortest path in $G$ from $v_1$ to $X$. Let $P=v_1 \to v_2 \to \ldots \to v_l \to w$.

Note that adding to $G|X$ any path starting and ending in $X$ produces a strongly connected digraph. It follows from the choice of $X$ that any non-trivial such path must include all the vertices in $V(G)-X$. In particular, if $l\geq 3$, $v_2,\ldots,v_{l-1}$ have no neighbors in $X$.

Let us further assume that $u$ and $w$ are chosen so that the directed path $Q$ from $w$ to $u$ in $G|X$ is as short as possible. (Perhaps, $w=u$.) Then $V(P) \cup V(Q)$ induces a cycle in $G$, and so $v_1$ and $v_l$ have at least $k-2$ non-neighbors on $V(P) \cup V(Q)$. At least $k-l$ of those non-neighbors are in $X$ if $l\geq 2$. Therefore there are at least $k-2$ non-edges (pairs of non-adjacent vertices) between $X$ and $V(G)-X$ if $l=1$, and at least $$2(k-l)+(l-2)(k+1) \geq l(k-2)$$ non-edges if $l \geq 2$. By the induction hypothesis there are at least $|X|(k-2)- \frac{(k+1)(k-2)}{2}$ non-edges between vertices of $X$, and therefore at least $$(l+|X|)(k-2)- \frac{(k+1)(k-2)}{2}=n(k-2) - \frac{(k+1)(k-2)}{2}$$ non-edges in total, as desired.

Answer by Sergey Norin for How to keep subsets disjoint?

2011-04-11T18:27:37Z

As far as I know, a paper of Alon and Frankl "The Maximum Number of Disjoint Pairs in a Family of Subsets" (available here) contains state of the art knowledge on the problem.

Briefly outlining some of its conclusions, let me mention that for a wide range of values of $k$ keeping the sets in $C$ supported on disjoint subsets of $[n]=\{1,2,\ldots,n\}$ works much better than keeping them individually small. For example, for even $n$ and $k=2^{n/2 +1}-1$, if we choose $C$ to consist of sets of smallest possible size than typical set in $C$ will have size $\Omega(n/\log{n})$ and two such sets almost surely intersect. On the other hand, if we choose $A$ to be the set of all subsets of $\{1,\ldots,n/2\}$, $B$ to be the set of all subsets $\{n/2+1, \ldots, n\}$ and $C =A \cup B$, then at least half of the pairs of sets in $C$ are disjoint. Solving a problem of Erdős, Alon and Frankl show that this example is essentially the best possible.

Answer by Sergey Norin for Flow on Infinite Graphs

2011-04-05T14:32:24Z

I think the following provides a counterexample.

The idea is to use the fact that on a graph $G$ with maximum degree $\Delta$ and diameter $D$ reasonably close to the natural lower bound $\log_{\Delta-1}|V(G)|$ the traffic is almost uniformly distributed.

Explicitly, for a vertex $v$, let $S_k(v):=\{x \in V(G) \: | \: d(x,v)=k\}$. Then $|S_k(v)| \leq \Delta(\Delta-1)^{k-1}$ and the traffic through $v$ can be estimated as $$T_G(v) \leq \sum_{k+l \leq D} |S_k(v)||S_l(v)| < D^2\Delta^2(\Delta-1)^{D-2}.$$

Bollobas and de la Vega in a paper "The diameter of random regular graphs" (last reference for Lecture 1 at the link.) show that for sufficiently large $N'$ a random $r$-regular graph on $N'$ vertices has diameter at most $\log_{r-1}(N') + \log_{r-1}(\log_{r-1}(N'))+C$, where $C$ is a (small) constant depending on $r$. By adjusting $C$, we may assume that an $r$-regular graph on $N'$ vertices satisfying this bound on diameter exists for any $N'$.

Finally, we construct $G$ by, first, taking an infinite $r$-regular tree, except that for simplicity of calculations we let the degree of $x_0$ be $r-1$. Secondly, we put an $r$-regular graph with the diameter bound listed above on the set of vertices $S_k(x_0)$, that is on each level of our infinite tree, considered as rooted at $x_0$.

Note that $|S_k(x_0)|=(r-1)^k$ and the diameter of $G|S_k(x_0)$ (i.e. $G$ restricted to $S_k(x_0)$) is at most $k + \log_{r-1}(k)+C$. It follows that the diameter of $G_n$ is at most $$\max_{k \leq l \leq n}( \mathrm{diam}(G|S_k(x_0)) + l-k) \leq n + \log_{r-1}(n)+C$$

The graph $G_n$ has maximum degree $\Delta = 2r$ and by the bound on the traffic load above we have $$ T_n(v) \leq n^2(2r-1)^{n+\log_{r-1}(n)+C'}$$ for any $v \in V(G_n)$ and some choice of $C'(r)$ independent on $n$. On the other hand $$|V(G_n)|=N =\sum_{k=0}^n (r-1)^k > (r-1)^n$$

It follows that, for any $\epsilon >0$ we can choose large enough $r$ so that for large $n$ we have $T_n(v) \leq N^{1 + \epsilon}$ for every $v \in G_n$.

Answer by Sergey Norin for Identifying poisoned wines

2011-04-01T17:29:34Z

Each bottle of wine corresponds to the set of rats who tasted it. Let $\mathcal{F}$ be the family of the resulting sets. If bottles corresponding to sets $A$ and $B$ are poisoned then $A \cup B$ is the set of dead rats. Therefore we can identify the poisoned bottles as long as for all $A,B,C,D \in \mathcal{F}$ such that $A \cup B = C \cup D$ we have $\{ A, B \} = \{ C, D \}$. Families with this property are called (strongly) union-free and the maximum possible size $f(n) $ of a union free family $\mathcal{F} \subset 2^{ [n] } $ has been studied in extremal combinatorics. In the question context, $f(n)$ is the maximum number of bottles of wine which can be tested by $n$ rats.

In the paper "Union-free Hypergraphs and Probability Theory" Frankl and Furedi show that $$2^{(n-3)/4} \leq f(n) \leq 2^{(n+1)/2}.$$ The proof of the lower bound is algebraic, constructive, and, I think, very elegant. In particular, one can find $2$ poisoned bottles out of $1000$ with $43$ rats.

Answer by Sergey Norin for A graph with few edges everywhere

2010-12-18T22:44:34Z

I think one can push through the probabilistic arguments of Tim Gowers and Fedor Petrov in the general case, as follows.

Let $c$ be a constant such that the number of red edges in $G[S]$ is at most $c|S|$ for every $S \subseteq V(G)$. One can order the vertices of $G$: $v_1, v_2, \ldots, v_n$, so that every vertex has at most $2c$ neighbors with lower indices. (Define the ordering starting with the highest index. If $v_n, \ldots,v_{i+1}$ are defined, set $v_i$ to be the vertex with the smallest degree in the subgraph induced by the vertices which are not yet indexed. This is a standard trick.)

Now we define a random subset $S$ of $V(G)$ recursively: if $S \cap$ {$v_1, \ldots, v_i$} is chosen put $v_{i+1}$ in $S$ with probability $1/2$ if it is not joined by a red edge to any of the vertices already in $S$, otherwise don't put it in $S$. Then $S$ is red-free and, just as in Fedor's answer, we can see that the probability that a pair of vertices $u$ and $v$ joined by a blue edge both lie in $S$ is at least $2^{-4c-2}$. Therefore the number of blue edges is at most

$2^{4c+2}c' \mathbf{E}[|S|] \leq 2^{4c+1}c'|V(G)|,$

where $c'$ is the constant implicitly present in the condition on the density of the blue edges.

Answer by Sergey Norin for 4-coloring maps of pentagons

2010-12-17T20:19:33Z

If $v$ is a vertex of degree at most 4 in a planar graph $G$ then one can extend a proper 4-coloring of $V(G) \setminus {v}$ to $v$ after possibly modifying it using the classical Kempe chain argument. See for example paragraph 5 of the "Summary of proof ideas" section of the Wikipedia entry on the 4-color theorem: http://en.wikipedia.org/wiki/Four_color_theorem

As pentagons with exposed edges correspond to vertices of degree 4 in the dual graph, one can color the map by induction using this trick.

Answer by Sergey Norin for union of regular polygons

2010-11-18T03:11:12Z

Let me attempt a proof using the group-theoretic formulation. I will use the additive notation for the group operation.

The proof is by induction on $n=|G|$, with the base being trivial. Let $n=p^rm$ for some prime $p$ with $\gcd(p,m)=1$. Consider $G' = pG$. Our goal is to reduce the problem for $G$ to its instance for $G'$. Let $R_j:=G' + jm$. Then ${R_0,R_1,\ldots, R_{p-1}}$ is a partition of $G$ into $G'$-cosets.

Let $G_i=d_iG$ be a subgroup of $G$ with $d_i | n$. If $p|d_i$ then $G_i \subseteq G'$ and every $G_i$ coset belongs to some $R_j$. In this case we say that $G_i$ is of the first kind. Otherwise, $d_i | m$, and translating $G_i$ by $m$ does not change $G_i$. We say that such $G_i$ is of the second kind.

Let $S = \cup_{i=1}^k (G_i+x_i)$ be the union under consideration, let $S_1$ be the union of cosets of the first kind among cosets comprising $S$, and $S_2$ -- of the second. Let $T_j=S_1 \cap R_j$ for $0\leq j \leq p-1$. Then $T_j$ is actually union of some of our cosets, and the sets $T_0,T_1,\ldots,T_{p-1}$ are disjoint. Let $T_j'=T_j-jm$: we shift all the cosets in $T_j$ from $R_j$ to $R_0=G'$. Note that $S_2-jm=S_2$ and therefore the intersection of $T_j$ and $S_2$ shifts with $T_j$. In particular, $|T_j'-S_2|=|T_j-S_2|$.

The set $S'=S_2 \cup (\cup_{j=0}^{p-1}T'_j) $ is still a union of cosets of $G_i$'s. We have

$|S'| \leq |S_2|+ \sum_{j=1}^{p-1}|T'_{j}-S_2| = |S_2|+ \sum_{j=1}^{p-1}|T_{j}-S_2|=|S|$.

Thus it suffices to consider $S'$, which means that we may assume that $S_1 \subseteq G'$. Let $G_i'=G_i \cap G'$ and let $x_i'$ be chosen so that $G_i'+x_i'= (G_i+x_i) \cap G'$. By the induction hypothesis applied to $G'$, we get

$a_1:=| \cup_{i=1}^k G_i' | \leq | \cup_{i=1}^k (G_i' + x_i')|=: b_1$

and also

$a_2:=|\cup_{i: G_i \not \subseteq G'} G_i'| \leq |\cup_{i: G_i \not \subseteq G'} (G_i' + x_i')|=:b_2$,

where in this second inequality we restrict our attention to $G_i$'s of the second kind. The set $S_2$ is the disjoint union of $p$ translates of its intersection with $G'$, which intersection is present on the right side of the inequality directly above. It follows that

$|S|=|S \cap G'|+|S_2 - G'|=b_1 + (p-1)b_2,$

while similarly we have

$|\cup_{i=1}^k G_i|=a_1 + (p-1)a_2$.

It follows that $|S| \geq |\cup_{i=1}^k G_i|$, as desired.

Finally, let me note that the inequality does not hold for non-cyclic groups. Already for $G = \mathbf{Z}_2 \times \mathbf{Z}_2$ the union of three distinct subgroups of $G$ of size $2$ is $G$, while it is possible to choose their cosets with the union of size $3$.

Answer by Sergey Norin for Can assignment solve stable marriage?

2010-11-14T18:35:09Z

David's question is sufficiently more precise than the question of Donald Knuth referred to in the answer below. I believe it can be answered in the negative for $n \geq 3$, as follows.

Let ${m_1,m_2,\ldots,m_n}$ and ${w_1,w_2,\ldots,w_n}$ be the vertices of the parts of our graph $K_{n,n}$. Consider a choice of preferences where for $i\geq 3$ the man $m_i$ and the woman $w_i$ are each other's top choice. Then any stable marriage must match them to each other.

We consider now the preferences of $m_1,m_2,w_1$ and $w_2$. I will write $m_1 : w_1 \to 1, w_2 \to 3$ to denote that $w_1$ is $m_1$-th first choice and $w_2$ is his third, etc.

$m_1 : w_1 \to 1, w_2 \to 2,$

$m_2 : w_1 \to 2, w_2 \to 3,$

$w_1 : m_1 \to 2, m_2 \to 3,$

$w_2 : m_1 \to 1, m_2 \to 2.$

Here $m_1w_1, m_2w_2$ is a stable matching and therefore if the function $f$ is as desired then we must have

$f(1,2)+f(3,2) < f(2,1)+f(2,3),$

where on the left we have the weight of the stable matching and on the right is the weight of the matching $m_1w_2, m_2w_1$.

But the left and right side of the inequality above are symmetric and so by switching the $m$'s and $w$'s we can design another set of preferences implying

$f(2,1)+f(2,3) < f(1,2)+f(3,2).$

It follows that the function $f$ as specified in the question can not exist.

Answer by Sergey Norin for Cauchy-Davenport strengthening?

2010-08-29T15:06:50Z

I believe that your statement follows from Cauchy-Davenport via matroid intersection theorem. (Matroid intersection theorem is stated in Chapter 41 of Alexander Schrijver's "Combinatorial optimization" book and can be also found here.)

You want to find a "rainbow" spanning tree in a complete bipartite graph you define, where colors correspond to edgesums. "Rainbow" spanning trees, in fact, seem to be commonly used as an example of matroid intersection.

By matroid intersection it suffices to show that for any set of edges $U$ in your graph

$r_1(U)+r_2(E \setminus U) \geq |A|+|B|-1,$

where:

$E$ is the set of all $|A||B|$ edges,

$r_1(U)$ is the rank of $U$ in the cycle matroid, and is equal to $|A|+|B|-c(U)$ where $c(U)$ is the number of connected components in the graph induced by $U$, and

$r_2(E \setminus U)$ is the number of edgesums obtained by the edges not in $U$.

If $c(U)=1$ then we are done. Otherwise, let $A' \subseteq A$, $B' \subseteq B$ be obtained from $A$ and $B$ by choosing one element from each component of the graph induced by $U$, so that both are non-empty. Then the edges between $A'$ and $B'$ are not in $U$ and thus by Cauchy-Davenport

$r_2( E\setminus U) \geq c(U)-1$,

as desired.

Answer by Sergey Norin for Stability of medians in Median graphs

2010-08-25T22:53:33Z

Here is an attempt to prove that the answer is yes.

Claim 1: Median graphs are bipartite.

This surely appears in the literature and is easy to verify. (Consider for a contradiction the shortest odd cycle and a median of 3 vertices on it: a pair of adjacent ones and a third one "opposite" of this pair.)

Claim 2: If $z \neq m(x,y,z)$ then there exists a vertex $z'$ adjacent to $z$ such that $d(x,z')=d(x,z)-1$ and $d(y,z')=d(y,z)-1$. Further, for each such vertex $z'$ we have $m(x,y,z')=m(x,y,z)$.

Let $m=m(x,y,z)$ and let $P(z,m)$ be as in Tony's comment. Then the neighbor of $z$ on $P(z,m)$ satisfies the claim. The second part of the claim holds as one can extend to $z$ the shortest paths between $z'$ and $x$ and $y$.

Main argument: By induction on $d(x,y)+d(x,z)+d(y,z)$. By Claim 1 $d(x,y)=d(x',y)\pm 1$ and $d(x,z)=d(x',z)\pm 1$. If the signs in both of these identities are the same then $m(x,y,z) = m(x',y,z)$ by Claim 2. Thus, wlog, $d(x,y)=d(x',y)+1$ and $d(x,z)=d(x',z)-1$.

If $z \neq m(x,y,z)$ then let $z'$ be as in Claim 2. We have $m(x,y,z')=m(x,y,z)$. As $d(x',z') \leq d(x,z')+1 = d(x',z)-1$, by the second part of the claim we have $m(x',y,z')=m(x',y,z)$. We can now replace $z$ by $z'$ and apply induction hypothesis.

We assume therefore that $z = m(x,y,z)$. Symmetrically, $y=m(x',y,z)$. We have

$(d(x,z) + d(z,y)) + (d(x',y)+d(y,z))=d(x,y)+d(x',z) \leq (d(x',y)+1)+(d(x,z)+1)$.

Thus $d(y,z) \leq 1$, as desired.

Comment by Sergey Norin

2012-03-14T19:00:20Z

@Boris: I have changed the penultimate sentence slightly after your first comment. (The original version was unnecessarily strong and false.) As $\alpha_i(r'+1)>z$ and $\beta_i(s'+1)< z$, using the monotonicity of the $\alpha$ and $\beta$ sequences we see that to the right of the first $r'+1$ alphas there are at most $s'$ betas.

Comment by Sergey Norin

2012-03-14T12:58:30Z

@Boris: If $r'=r-1$ then $\alpha_i(r'+1)$ is not in the sequence.

Comment by Sergey Norin

2011-10-18T14:56:21Z

As mentioned in mathworld.wolfram.com/PerfectMatching.html , this graph has been implemented in Mathematica as GraphData["NoPerfectMatchingGraph"]. This appears to confirm that the absence of perfect matchings is its most recognized property.

Comment by Sergey Norin

2011-05-27T18:49:35Z

Dear Hailong: I changed the answer to a proof which works for all $l \geq 4$. Can the construction achieving the bound be realized in your setting, or, perhaps, there are some additional constraints?

Comment by Sergey Norin

2011-04-11T21:14:23Z

@Seva: In Alon & Frankl's paper it is shown that for families of subsets of size $m=2^{(1/2+\delta)n}$ the number of pairs is at most $m^{2 - \delta^2/2}$. This is not exact, but does provide some information. It would be interesting to improve on this bound and a quick internet search provided no indication that anybody did.

Comment by Sergey Norin

2011-04-05T16:55:43Z

@Gabriel: It would make the difference, but I am not sure where your factor of $2$ comes from. $G|S_k$ has the structure of the $r$-regular graph I am discussing above with $N'=(r−1)^k$.

Comment by Sergey Norin

2011-04-04T20:04:26Z

In the sentence "The total traffic in $G_n$ is equal to $n(n-1)/2$" and later on you seem to be using $n$ to denote both the radius of the graph and its number of vertices. Could you, please, change the notation?

Comment by Sergey Norin

2010-12-18T23:15:55Z

@Tracy: Thank you, corrected $2c$ to $4c$. Additive constants in big-O could be absorbed into multiplicative ones.

Comment by Sergey Norin

2010-11-22T16:12:09Z

@Gerry Myerson: Thank you. I've implemented the suggested corrections.

Comment by Sergey Norin

2010-11-18T22:27:44Z

@Fedor: I assumed that it follows from standard compactness arguments, but I don't see it now. My bad.

Comment by Sergey Norin

2010-11-16T23:37:26Z

@Fedor: Yes. I like the statement. Without loss of generality, we can restrict our attention to finite such sets P. Then we can work modulo their least common multiple, transforming the original statement into a very combinatorial statement about finite abelian groups. I don't have any good ideas about how to prove it, though...

Comment by Sergey Norin

2010-11-16T22:35:39Z

Does $C(S)$ have to consist only of numbers divisible by an element of $P$? I think it is possible for primes $p_1$ and $p_2$ to be covered by $S$, while the product $p_1p_2$ is not (e.g. $S$ is the set of all integers not congruent to $5$ modulo $6$).

Comment by Sergey Norin

2010-11-15T00:07:10Z

Tsuyoshi Ito: Thank you. Made the correction.