# Tagged Questions

**4**

votes

**1**answer

122 views

+100

### Induced subgraphs of small strongly regular graphs

Consider a strongly regular graph $G$ with parameters $(76,30,8,14).$ Hoffman's bound tells us that $\overline{G}$ has an independent set of size at most $4$ and its not hard to see there are indeed ...

**4**

votes

**1**answer

40 views

### Linear intersection number and vertex covering number

A linear hypergraph is a pair $\pi=(X, L)$ where $X\neq \emptyset$ is a set and $L\subseteq {\cal P}(X)$ has the following properties:
for $e\in L$ we have $|e|\geq 2$;
if $e_1\neq e_2 \in L$ then ...

**0**

votes

**0**answers

12 views

### Optimization of a multilinear function over a product of hypersimplices

Let $P = \Delta_1 \times \cdots \times \Delta_N$ be the Cartesian product of $N$ hypersimplices. Let $f : P \to \mathbb{R}$ be a multilinear function of $N$ variables, ie $x_i \mapsto f(x_1, \ldots, ...

**2**

votes

**0**answers

33 views

### Can we replace 2-fold cover by n rectangles with 1-fold cover by n rectangles?

Suppose that $n$ rectangles cover every point of their union exactly twice (except for points on their boundaries).
Can we partition this union into at most $n$ rectangles?
I think it's pretty ...

**55**

votes

**2**answers

3k views

### What is the amplituhedron?

The paper ”Scattering Amplitudes and the Positive Grassmannian” by Nima Arkani-Hamed, Jacob L. Bourjaily, Freddy Cachazo, Alexander B. Goncharov, Alexander Postnikov, and Jaroslav Trnka, introduces ...

**4**

votes

**1**answer

66 views

### Compiling self-referential forms

Fix $1\leq d\in\mathbb{N}$ and set $D:=\{0,1,\ldots,d-1\}$.
Consider the system of equations
\begin{equation}
x_i=c_i + \sum_{j\in D}\delta_{x_j,i}
\end{equation}
with $c_i\in D$ given and $x_i\in D$ ...

**0**

votes

**2**answers

233 views

### On independent sets of graph

Given $G$ a regular graph on $n$ vertices, denote $\alpha(G)>1$ to be independence number.
Denote $\Gamma(G)$ to be collection of possible subset of independent vertices in $G$ of cardinality ...

**0**

votes

**0**answers

16 views

### About adjacency matrices of $k-$shift lifts of graphs

I am finding the notation of cyclic lifts of graphs to be very confusing.
Lets say one is looking at a cyclic $k-$lift of a $\vert V \vert$ sized graph.
I would like to understand what is the ...

**17**

votes

**13**answers

3k views

### Generalizations of the Birkhoff-von Neumann Theorem

The famous Birkhoff-von Neumann theorem asserts that every doubly stochastic matrix can be written as a convex combination of permutation matrices.
The question is to point out different ...

**16**

votes

**2**answers

921 views

### Has Reifegerste's Theorem on RSK and Knuth relations received a slick proof by now?

For the notations I am using, I refer to the Appendix at the end of this post.
Here is what, for the sake of this post, I consider to be Reifegerste's theorem:
Theorem 1. Let $n\in\mathbb N$ and ...

**5**

votes

**1**answer

132 views

### Finding sparsest solution of a linear system

I want to find the solution with most zero-components for the following problem:
$Ax=b$ for $A\in \mathbb{R}^{k\times n}, b \in \mathbb{R}^{k},k<n$, where $x$ is real and has no additional ...

**3**

votes

**0**answers

32 views

### Signatures of latin squares: what about the extremal cases?

For a latin square (LS) of order $n$, we will define a cut (or maybe general transversal, I don't know whether there is an entrenched name for this) as a collection of $n$ cells such that no two share ...

**4**

votes

**1**answer

169 views

### Continuous-piecewise-linear versus piecewise-linear

Some authors use the term "continuous piecewise-linear" where other authors use the shorter term "piecewise-linear" (with continuity tacit).
I'd be interested in people's thoughts about this ...

**5**

votes

**2**answers

268 views

### Identity for Power Series and Binomial Coefficients

This question concerns a combinatorial identity obeyed by power series coefficients. Throughout we let $[x^{M}]\{\phi(x)\}$ denote the coefficient of $x^{M}$ in a power series $\phi(x)$.
Let $k$ be ...

**14**

votes

**0**answers

266 views

+50

### Monotone embedding of complete binary tree in hypercube

Embedding different graphs, especially binary trees, in the hypercube has a huge literature. However, I could not find anything if we restrict the embedding to be monotone. So I would like to ...

**7**

votes

**1**answer

134 views

### A positivity problem involving the number of ways of expressing $n$ as a product of $k$ factors

Let $d_k(n)$ denote the number of ways of expressing $n$ as a product of $k$ factors, and let $$D_k(x)=\sum_{n\leq x}d_k(n)$$ be the summatory function. During a study of Mertens' function I was lead ...

**15**

votes

**2**answers

335 views

### Can all unit-distance graphs have their vertices at algebraic integers?

A graph $G$ is described as a unit-distance graph if there exists a function $f:G \rightarrow \mathbb{C}$ such that for every edge $(u,v) \in E(G)$, we have $|f(u) - f(v)| = 1$.
Obviously, we can ...

**4**

votes

**2**answers

130 views

### Largest eigenvalue adjacency matrix-link deletion

Let G be a connected undirected graph and G\e be a graph obtained by removing a random link e from the graph G. Let $\lambda_1(A(G))$ be the largest eigenvalue of the adjacency matrix of graph G. Is ...

**1**

vote

**0**answers

75 views

### Probabilistic statement on matrix ranks

Given $A\in\{0,1\}^{n\times n}$ with $rank(A)=r=2^{O(\sqrt{\log_2n})}$.
Denote $\mathsf{1_n}\in\{0,1\}^n$ as vector with $1$s.
Does
$$\lim_{n\rightarrow\infty}\mathsf{P_{A\in\{0,1\}^{n\times ...

**4**

votes

**0**answers

120 views

### Inversion, Koszul duality, combinatorics and geometry

According to this MO answer Koszul duality is related to operations on generating series;
1) multiplicative inversion for quadratic algebras,
2) compositional inversion for quadratic operads,
3) ...

**6**

votes

**3**answers

412 views

### Number of perfect matchings of the Dodecahedron

This question seems just to be an elementary enumeration problem, but I believe something deeper might be involved:
How many perfect matchings does a dodecahedron graph have?
Here the ...

**8**

votes

**2**answers

210 views

### Certain signed sum over $S_n$

The following question appeared in my research:
Let $G_1,G_2,G_3$ all be subgroups of $S_n$, and consider the sum
$$
\sum_{g_i \in G_i, g_1g_2g_3 = id} \epsilon(g_1)
$$
that is, we only consider ...

**16**

votes

**0**answers

429 views

### What are the products $\prod_{A\subset{\mathbb F}_p\colon |A|=n} \sum_{a\in A} \zeta^a$ equal to?

This is a somewhat more explicit version of a question I have recently asked.
Let $p$ be an odd prime, and write $\zeta:=\exp(2\pi i/p)$ (any other primitive $p$th root of unity will do as well). For ...

**2**

votes

**1**answer

75 views

### Counting linearly ordered subsets of maximal length in partially ordered $d$-tuples of nonnegative integers

Given $d\in \mathbb{N}$, let $X_d:= \{(\ell_1, \ldots , \ell_d): 0 \le \ell_1 \le \ldots \le \ell_d \le d\}\subset \mathbb{Z}^d$, and endow $X_d$ with the (usual) partial order, namely, $x\le y$ if ...

**2**

votes

**0**answers

65 views

### Asymptotic expansion for the Bell numbers

The Bell numbers $B(n)$ (that is, the numbers that count the set partitions of a set, and have exponential generating function $\exp(e^x -1)$ ) admit the asymptotic expansion
$$\frac{\log B(n)}{n} = ...

**6**

votes

**3**answers

380 views

### Complexity of high-order differentiation

Let $g(x) = \exp(f(x))$. Assuming numerical (or symbolic) values of $f(x), f'(x), f''(x), \ldots, f^{(n)}(x)$ are known, is there a way to compute $g'(x), g''(x), \ldots g^{(n)}(x)$ (or even the ...

**2**

votes

**0**answers

83 views

### Isomorphic subcategories of directed graphs and presets

For the purposes of this post, a digraph (directed graph) has neither loops nor multiple parallel edges, and a preset is an ordered pair consisting of a set $S$ and a preorder (viz., a reflexive and ...

**2**

votes

**0**answers

252 views

### Enumerating certain types of permutation polynomials

Given a prime power $q$, I would like to enumerate (preferably up to isomorphism*) all the permutation polynomials $f(x)$ on $K = GF(q^3)$ satisfying the following conditions:
$f(ax) = af(x)$ for ...

**9**

votes

**2**answers

317 views

### Can a graph be reconstructed from its cycle lengths?

All graphs discussed are finite and simple. The cycle sequence of a graph $G$, denoted $C(G)$, is the nondecreasing sequence of the lengths of all of the cycles in $G$, where cycles are distinguished ...

**3**

votes

**1**answer

269 views

### Simplest form for sum of Binomial Expressions

How difficult is the problem of reducing the number of terms in a sum of binomial expressions? Formally:
Given $a_1, a_2, a_3, … a_n$, and $b_1, b_2, b_3, ... , b_n$, where $a_i, b_i \in \mathbb{Z}$, ...

**10**

votes

**2**answers

564 views

### What is a “Ramanujan Graph”?

I noticed an apparent conflict in the definition in literature about what is a "Ramanujan graph, which I was wondering if someone could kindly clarify.
(1)
The Hoory-Linial-Wigderson review on ...

**5**

votes

**1**answer

227 views

### Infinite graphs isomorphic to their line graph

The only finite connected graphs $G$ that are isomorphic to their line graph $L(G)$ are the cycle graphs $C_n$ (see this link for example).
There are connected countable graphs that are isomorphic to ...

**2**

votes

**1**answer

318 views

### Is it possible to create an infinite sequence in which no subsequence is repeated 3 times in a row?

In Chess, there is the Threefold Repetition rule where if a sequence of moves is repeated 3 times in a row, either player can claim a draw.
Say two players wanted to play a legal, infinite game of ...

**1**

vote

**0**answers

59 views

### research on the structure/properties of permutation matrix/table with $(i,j)th$ entry as $\pi_j\circ \pi_i^{-1}$

Is there any research on the structure/properties of permutation matrix/table with $(i,j)th$ entry as $\pi_j\circ \pi_i^{-1}$, where $\{\pi_1,\pi_2,...,\pi_{k!}\}=S_k$?
I know if we apply the ...

**3**

votes

**1**answer

110 views

### Braid wiring diagrams and matroids

recently I started reading some articles about the presentation of the fundamental group of lines arrangements in $\mathbb{C}^{2}$ via Wiring diagrams.
I also found some relation with matroid theory. ...

**10**

votes

**1**answer

247 views

### Soft question: mathematics about truchet tiles

It seems that this is the first question on Truchet tiles on MO.
Shown above is a picture of a random tile, which you can see the resulting configuration is much like many membranes of cells.
I ...

**3**

votes

**2**answers

286 views

### How to flip one triangulation on a surface into another

Let $S$ be a compact orientable surface and $p_1,\dots, p_n\in S$ be distinct points. We consider all triangulations on $S$ with vertices $p_1,\dots, p_n$.
Is there an algorithm which takes two ...

**4**

votes

**0**answers

54 views

### Lower bound on the number of k-plexes in a Latin square

Let $A$ be an order-$n$ Latin square. A $k$-plex of $A$ is a set of entries , $k$ from each row and column and $k$ from each symbol.
My question is: Is there a Latin square with a large number of ...

**3**

votes

**1**answer

105 views

### Infimum of partitions

Let $X\neq\emptyset$ be a set. A partition is a subset $P\subseteq {\cal P}(X)\setminus \{\emptyset\}$ such that $\bigcup P = X$ and any distinct members of $P$ are disjoint. We denote by ...

**-1**

votes

**1**answer

79 views

### Maximal independent sets in a graph $G$ versus maximal matchings in the line graph $L(G)$

I'm a bit confused because of the answers in Maximum matchings in infinite graphs .
I was thinking that an independent set in a graph $G$ corresponds to a matching in the line graph $L(G)$, and vice ...

**3**

votes

**0**answers

53 views

### Nonattacking configurations of k bishops on an m by n rectangular board

The number of ways to place k bishops in a nonattacking configuration on an n by n square board is a well known result and can for example be found in ...

**3**

votes

**2**answers

63 views

### Average vertex degree in finite Delaunay triangulations in high dimensions

In $\mathbb{R}^2$ it's known that with a "random" point configuration, the average degree of a vertex in its Delaunay triangulation is 6.
Does anyone know of a similar result in higher dimension? I ...

**0**

votes

**1**answer

149 views

### Poisson approximation of random sub-graphs

I add the edges of $G(n)$ the complete graph on $n$ vertices one by one, at random and without replacement, and denote by $G(n,m)$ the resulting Erdos Renyi random graph process. At step $m$ in the ...

**0**

votes

**0**answers

35 views

### Number of faces of polytope projecting to lower dimensional polyhedron

Denote $K=\mathrm{conv}(v_1, \ldots, v_n)\subsetneq\Bbb R^m$ to be convex set spanned by vectors $v_i\in\Bbb R^m$ with $m\leq n$ then what technique could be useful to upper bound minimum number of ...

**36**

votes

**0**answers

850 views

### Intersecting Family of Triangulations

Let $\cal T_n$ be the family of all triangulations on an $n$-gon using $(n-3)$ non-intersecting diagonals. The number of triangulations in $\cal T_n$ is $C_{n-2}$ the $(n-2)$th Catalan number. Let ...

**10**

votes

**4**answers

971 views

### What are the most general classes of simplicial complexes or posets for which the Charney-Davis conjecture is known, and what is the most general setting for which it might expected to be true?

What I would like to know is exactly what the title asks:
What are the most general classes of
simplicial complexes or posets for
which the Charney-Davis conjecture is
known, and what is the ...

**1**

vote

**0**answers

168 views

### On matrix rank inequality

Let $A$ be a $\{0,1\}$ square matrix.
Let $J$ be all $1$ matrix.
Let $\bar{A}=J-A$.
Is it possible for $rk_+(A)\geq c\cdot rk_+(\bar{A})^d-1$ and $rk_+(\bar{A})\geq c\cdot rk_+({A})^d-1$ for some ...

**0**

votes

**1**answer

226 views

### Maximize combinatorial sum for boolean function

I am trying to maximize the function
$$ S(f)=\sum_{j=0}^{n-\frac{n-1}{t}}(-1)^j{n-\frac{n-1}{t}\choose{j}}\sum_{i=0}^{\frac{n-1}{t}}(-1)^{f(i-j)}(t-1)^i{\frac{n-1}{t}\choose{i}} $$
for a function ...

**2**

votes

**0**answers

69 views

### Volume of bounded regions in hyperplane arrangements

I am given a hyperplane arrangement $\mathcal{H}_0$ in $\mathbb{R}^n$ and a function $\phi \colon \mathbb{R}^n \to \mathbb{Q}.$ I choose any enumeration on the set of primitive vectors (i.e. vectors ...

**1**

vote

**0**answers

64 views

### Multiple Bipartite graphs and matchings

I've been told recently that it's better i just for help regarding my 'specific' problem rather than lots of little questions around the same topic which appear somewhat unclear. I would first like to ...