Search Results

Here is a family of counterexamples with arbitrarily large $l$ in the case $m=n=2$: $$T_1 = {*}111111\cdots1$$ $$T_2 = 0{*}11111\cdots1$$ $$T_3 = 00{*}1111\cdots1$$ $$T_4 = 000{*}111\cdots1$$ $$T_5 = …

The answer is indeed ${n \choose \lfloor n/2 \rfloor}$, here is a proof. It's equivalent to finding the maximal number of vectors $v$ in the hypercube $H=\{-1,1\}^n$ with all the same dot product with …

With the acyclic condition, the answer is yes. Starting at $v$ and repeatedly following any edge exiting the current vertex, you will eventually end up at $t$, by acyclicity and uniqueness of the sink …

In general, this is an open problem. In the special case where $n$ is divisible by $4$ and $k=n/2$, the clique number is believed to be $n$ but this is equivalent to the Hadamard matrix conjecture. I …

We can see any tree $T$ as the Hasse diagram of a poset whose smallest element is the root. I will freely identify the tree with the corresponding poset. If we label by $i$ the $i$'th vertex added in …

Without any condition on the matroid structure, there is really no reason for your inequality to hold. For example, take $X=\{a\},Y=\{b\}$ so that $X+Y=\{a+b\}$ where $a,b$ are any nonzero elements of …

Here is a combinatorial proof I found. First, note that this is equivalent to allowing loops but demanding that all vertices have indegree and outdegree 2 (add a loop to each vertex of in/outdegree 1) …

Take the graph on $2k+2$ vertices $x_0, \ldots, x_k, y_0, \ldots, y_k$ with an edge between any pair of distinct vertices except $(x_i, y_i)$ for $0\le i \le k$. There are plenty of $2$-factors, e.g. …

In Discrete groups, expanding graphs, and invariant measures (in the notes at the end of Chapter 7), Lubotzky mentions that certain estimates for the number of spanning trees $\kappa(G)$ of a $k$-regu …

Let $G$ be a digraph such that there is an unique directed walk of length $k$ between any two vertices. Equivalently, if $A$ is the adjacency matrix of $G$, then $A^k$ is the matrix with all entries $ …

It is known (see here for example) that, in a simple graph of odd genus $g$ with $n$ vertices and $m$ edges, the number of cycles of lenght $g$ is at most $\frac{n(m-n+1)}{g}$. Since this can be be ph …

I don't know about having one vertex per square, but there is a similar very interesting construction with edges at squares. It does not answer your question but it will still surely interest you. Spe …

Some computation in sage yielded the following example, with $n=8$ and $P$ the cyclic permutation $(12345678)$: $$M=\left( \begin{array}{cc} 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 1 & …

Here is my favorite conceptual definition of the determinant, which answers point 6 and looks pretty much inevitable. If $V$ is an $n$-dimensional $k$-vector space and $T$ is an endomorphism of $V$, t …

Ramanujan graphs are defined as $(q+1)$-regular graphs for which all nontrivial eigenvalues of the adjacency operator are contained in the interval $$[-2\sqrt{q}, 2\sqrt{q}].$$ The reason for this def …