## Unique-neighbor expander

I want to solve Problem 4.10 from Randomness by Salil Vadhan. https://people.seas.harvard.edu/~salil/cs225/spring15/PS3.pdf

Consider a bipartite expander $$G$$ with left degree $$D$$ so that every subset $$S$$ of the left vertices with at most $$K$$ vertices has at least $$(1-\epsilon)D|S|$$ neighbors. Then $$G$$ also has the property that it has $$(1-2\epsilon)D|S|$$ unique neighbors. Unique meaning that it has exactly one corresponding vertex from $$S$$.

I recognize that the new expansion factor is $$(1-2\epsilon)D = 2\cdot(1-\epsilon)D -D$$

Posted on Categories proxies

## Understanding Gillman’s proof of the Chernoff bound for expander graphs

My question is about Claim 1 in the proof here: Gillman (1993). At the end of the proof, the author says:

The matrix product $$U^\top\sqrt{D^{-1}}(P+(\mathrm{e}^x-1)B(0)-\mu I)\sqrt{D}U$$, which is equal to $$(D’-\mu I)(I+(D’-\mu I)^{-1}(\mathrm{e}^x-1)D’U^\top D_A U)$$, is singular. Therefore,

\begin{align*} 1&\leq \lVert (D’-\mu I)^{-1}(\mathrm{e}^x-1)D’U^\top D_A U \rVert_2 \ &\leq \frac{1}{\mu-\lambda_2}(\mathrm{e}^x -1). \end{align*}

(The first inequality uses the continuity of the function $$\lambda_2(y)$$.)

I understand why the two expressions at the beginning are equal and I understand the second inequality, but I do not understand the first inequality and also why the matrix product is singular.

Let me provide the definitions so you can avoid reading the whole paper. There is a weighted undirected graph $$G=(V, E, w)$$ where $$w_{ij}=0$$ if $$\{i,j\}\notin E$$. Denote $$w_i:=\sum_j w_{ij}$$. Let $$P$$ denote the transition matrix, so $$P_{ij}:=\frac{w_{ij}}{w_i}$$. Denote by $$\lambda_2$$ the second largest eigenvalue of $$P$$ and by $$\epsilon:=1-\lambda_2$$ the spectral gap. Next, let $$M$$ be the weighted adjacency matrix $$M_{ij}:=w_{ij}$$. Let $$A$$ be a set of vertices and $$\chi_A$$ be an indicator function. Some more definitions are:

\begin{align*} &E_r:=\operatorname{diag}(\mathrm{e}^{r\chi_A}) & &P(r):=PE_r \ &D:=\operatorname{diag}(\frac{1}{w_i}) & &S:=\sqrt{D}M\sqrt{D} \ &S_r:=\sqrt{DE_r}M\sqrt{DE_r} & & B(r):=\frac{1}{\mathrm{e}-1}(P(r+1)-P(r)) \end{align*}

Moreover, since $$S$$ is unitarily diagonalizable, there exist a unitary matrix $$U$$ and a diagonal matrix $$D’$$ such that $$D’=U^\top SU$$. Furthermore, there exists a diagonal matrix $$D_A$$ such that $$B(0)=PD_A$$.

Define $$\lambda(r)$$ to be the largest eigenvalue of $$P(r)$$ and $$\lambda_2(r)$$ to be its second largest eigenvalue. As before, $$\epsilon_r := \lambda(r)-\lambda_2(r)$$ is the spectral gap.

In Claim 1 the author lets $$0\leq x\leq r$$ be some number. He also defines $$\mu<\lambda(x)$$ to be any other eigenvalue of $$P(x)$$. At the end of the proof, we are only interested in $$\mu>\lambda_2$$.

Some other facts are:

\begin{align*} &\lVert D’ \rVert_2 = \lVert D_A \rVert_2 = 1 & &D’=U^\top\sqrt{D^{-1}}P\sqrt{D}U \ &P(0)=P & &\lambda(0)=1 & &\lambda_2(0)=\lambda_2 \ &P=\sqrt{D}S\sqrt{D^{-1}} & &P(r)=\sqrt{DE_r^{-1}}S_r\sqrt{E_rD^{-1}} \end{align*}

I hope I didn’t miss anything relevant. Thank you for your help.

## Unit testing extension method adding view location expander

### Introduction

I’m writing unit tests for an extension method I wrote. Its only purpose it is to wrap startup logic which extends ViewLocationExpanders list by an instance implementating IViewLocationExpander. ViewLocationExpanders is a property of RazorViewEngineOptions, which can be configured in application startup in ConfigureServices() method. I’m using XUnit 2.4.1.

### Usage

services.Configure<RazorViewEngineOptions>(options => {     options.ViewLocationExpanders.Add(new ViewLocationExpander()); }); 

I can use:

services.AddViewLocationExpander(new ViewLocationExpander()); 

### ViewLocationExpander

public class ViewLocationExpander : IViewLocationExpander {     public IEnumerable<string> ExpandViewLocations(         ViewLocationExpanderContext context,          IEnumerable<string> viewLocations)     {         if (context == null)         {             throw new ArgumentNullException(nameof(context));         }          if (viewLocations == null)         {             throw new ArgumentNullException(nameof(viewLocations));         }          /*             * Note:             * {0} = action name             * {1} = controller name             * {2} = area name             */          var newViewLocations = new string[]         {             // Example: '/Views/Home/_Partials/FooBar.cshtml'             "/Views/{1}/_Partials/{0}.cshtml",         };          // Add new locations *AFTER* MVC default locations.         return viewLocations.Union(newViewLocations);     }      public void PopulateValues(ViewLocationExpanderContext context)     {         context.Values["customviewlocation"] = nameof(ViewLocationExpander);     } } 

### Extension method

public static IServiceCollection AddViewLocationExpander(     this IServiceCollection services,      IViewLocationExpander viewLocationExpander) {     if (services == null)     {         throw new ArgumentNullException(nameof(services));     }      if (viewLocationExpander == null)     {         throw new ArgumentNullException(nameof(viewLocationExpander));     }      return services.Configure<RazorViewEngineOptions>(options =>     {         options.ViewLocationExpanders.Add(viewLocationExpander);     }); } 

### Unit tests

[Fact] public void ExtensionMethodAddsNewViewLocationExpander() {     // Arrange     var services = new ServiceCollection();     services.AddMvc();      // These two are required to active the RazorViewEngineOptions.     services.AddSingleton<IHostingEnvironment, HostingEnvironment>();     services.AddSingleton<ILoggerFactory, LoggerFactory>();      // Act     var serviceProvider = services.BuildServiceProvider();     var oldOptions = serviceProvider.GetRequiredService<IOptions<RazorViewEngineOptions>>().Value;     services.AddViewLocationExpander(new ViewLocationExpander());     serviceProvider = services.BuildServiceProvider();     var newOptions = serviceProvider.GetRequiredService<IOptions<RazorViewEngineOptions>>().Value;      // Assert     Assert.True(newOptions.ViewLocationExpanders.Count > oldOptions.ViewLocationExpanders.Count); } 

### Questions

1. Am I going beyond the scope of what unit testing should include? I’m afraid that my code is actually testing the basic functions of generic collections and/or aspects of ASP.NET Core.
2. If my concern above is true, that should I write unit tests to this at all? How should it work?
Posted on Categories buy elite proxies

## Ambiguous chevron styles in an expander

I’ve begun to notice that a lot of apps have opted to use a right arrow chevron on the right edge of the header.

However, I am used to seeing it to indicate that it will transition to a different page. This is common in mobile applications as well as some desktop applications like firefox overflow menu’s.

From my personal observation and experience, a right arrow chevron, if used as an expander, should not be on the right side. It can be either on the left of the header or a different icon like a down arrow chevron.

For example, I find the following pictures quite misleading, and I believe in their current positions, they should be down arrow chevrons instead.

Am I correct to say this? I realize there isn’t a black or white solution, but I’m leaning towards my reasoning. But because a lot of apps made specifically for UI designs do in fact follow this pattern makes me uncertain.  