# Tagged Questions

Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.

63 views

### Lower bound the ratio of the combinatorial quantities

Suppose $p < q$, $s = p^{d}$ for some fixed $d \in (0,1)$, let $p$ goes to infinity, define the following quantity, \begin{aligned} \quad f(j) = \sum_{i = 0}^{\min(j,s)}{s \choose i}{p-s \choose i}{...
218 views

### sum over all integer partitions, of the product of the factorials of the terms

I'm looking for something making tractable the sum, over all partitions into k terms of an integer n, of the product of the factorials of all the terms. Thanks,
70 views

### connectedness of semi algebraic sets

We know the inequalities $x_ix_j >\theta_{ij}$ or $x_ix_j<\theta_{ij}$ for some $\theta_{ij}$>0, some $i,j\in\{1,\cdots,n\}$, $i\neq j$ defines the easiest semi algebraic set in $R^n_{\geq 0}$, ...
115 views

### Average minimum number of random k-sparse vectors in GF(2) to span the whole space?

What is the average minimum required number of independent $k$-sparse (having at most $k$ non-zero elements) random vectors belonging to $\mathbb{F}_2^n$ to span the whole space of $\mathbb{F}_2^n$? ...
107 views

### What is the densest bipartite graph with unique Hamiltonian cycle?

In a prior post regarding perfect matching, it was stated that the densest graph with a unique perfect matching cannot have more than $n^2$ edges, if graph has $2n$ vertices. Analogously, what is the ...
136 views

### Upper Bound for the Difference of Even Probability and Odd Probability in Hypergeometric Distribution

Let $X$ be a random variable following the hypergeometric distribution with parameters $N,K,n$, where $$Pr(X=k) = \frac{\binom{K}{k}\binom{N-K}{n-k}}{\binom{N}{n}}.$$ To ...
180 views

### First to note/document the relation between permutohedra and multiplicative inversion

The relation between the refined face numbers of the permutohedra and the formal series expansion of the reciprocal of a function (exponential generating function, formal Taylor series) is given in ...
133 views

### Number of eigenvalues of a Cayley graph

Let $G=Z_2^n$ and $S\subset G$. Is there any relation for number of distinct eigenvalues of $\Gamma=Cayley(G,S)$ graph depending on $n$ and $|S|$, or at least diameter of $\Gamma$? If you have any ...
133 views

### “Small” simplicial complex with torsion trees

I am giving an expository talk soon about Duval-Klivans-Martin's paper Simplicial Matrix Tree Theorems, and I've been struggling to find a good example to do at the board. An important aspect of the ...
132 views

### Alternative parallel paths

There are $n$ non-intersecting strings (with ends $x_1,\dots, x_n$ and $y_1,\dots, y_n$). An additional string intersects the first $n$ strings somehow. All the intersections are simple (vertices of ...
285 views

### Choosing two-colorable subgraph in a triangulation

Consider a planar graph $G$ which is a triangulation. Is it possible to find a two-colorable subgraph $H$ of $G$ which has a common edge with every face of $G$? It is known that it is not always ...
187 views

### Non-regular languages fulfilling the Pumping Lemma

Some non-regular languages don't yield to the Pumping Lemma ($L_1=a^nb^mc^m$ should work). But now consider the set of non-regular languages L only over the alphabet {a}. (Like $L_2=a^{n^2}$ or ...
79 views

66 views

Given two real analytic functions, $g(x)$ and $f(x)$, on an open interval $I\subset \mathbb{R}$, it is obvious that $g(x) \leq f(x)$ does not imply $g_n \leq f_n$ (here $g_n = [x^n] g(x)$ denotes the $... 1answer 104 views ### Counting bounded genus non-isomorphic graphs What is the number of non-isomorphic$2n$vertex balanced bipartite graphs of degree at most$d$and genus$g$? I am most interested in$d\leq3$and$g=0$. 2answers 187 views ### Non-Cayley expander graphs When I search about expander graphs in google I see a lot of articles about expander Cayley graphs. Now my questions are as follows: Are all expander regular graphs are Cayley, or there is a special ... 0answers 262 views ### Computing the ordinal of a rational language well-partially-ordered by the subword relation Let$\Sigma$be a finite set or "alphabet",$\Sigma^*$the free monoid on$\Sigma$or set of "words". If$w,w'\in \Sigma^*$, write$w\leq w'$when$w$is a "subword" of$w'$, i.e., can be obtained by ... 1answer 112 views ### Nearly Be Bruijn sequences constructed from De Bruijn sequences Let$w$be a De Bruijn$01$-sequence of the type$B(2,n)$; i.e., a cyclic$01$-sequence that contains every$n$-digit$01$-sequence exactly once. Let$x$be a$01$-sequence of length$n$. When and ... 2answers 193 views ### “Diagonalizing” Littlewood-Richardson coefficients Let's consider the Littlewood-Richardson coefficients$c^{\lambda}_{\mu \nu}$so that $$V_\mu \otimes V_\nu = \bigoplus_\lambda V_\lambda^{\oplus c^{\lambda}_{\mu \nu}}$$ ... 0answers 107 views ### A way to smooth out the log* function? I have seen here and there discussions about what is the "correct" way of extending the Ackermann function to the reals (the same way the Gamma function extends the factorial function to the reals). ... 1answer 149 views ### Powers of two with coefficients {1,−1} Given a vector$(n_0, n_1, \dots, n_l)$where$n_i \in \{-1, 1\}$,$i = \overline{0, l-1}, n_l = 1$and$l \in \mathbb{N}$. Prove that for all$a$such that $$0 < a \leq 2^0\cdot n_0 + 2^1 \cdot ... 2answers 948 views ### Encoding vectors of size n in matrices which less than 2n rows [closed] I have a set of vectors and each has n nonnegative entries. Moreover, each entry of a vector has a quality: (1) or (2). It makes 2^n different possible patterns. For example, let's take two ... 0answers 62 views ### Björner-Wachs theorem for posets admitting an EL-labeling In the survey paper Poset Topology: Tools and Applications by Michelle Wachs, there is the following theorem on p46: Theorem 3.2.4 (Björner and Wachs [40]). Suppose P is a poset for which \... 2answers 251 views ### Are all numbers from 1 to n! the number of perfect matchings of some bipartite graph? Let f(G) give the number of perfect matchings of a graph G. Consider set \mathcal N_{2n}=\{0,1,2,\dots,n!-1,n!\}. Consider collection of all 2n vertex balanced bipartite graph to be \... 0answers 132 views ### More about self-complementary block designs For what odd integers n \geq 3 does there exist a self-complementary (2n,8n−4,4n−2,n,2n−2) balanced incomplete block design? By "self-complementary" I mean that the complement of each block is a ... 0answers 80 views ### Regularity for a bipartite graph Let G be a bipartite graph with 2^n left vertices and 2^n right vertices such that: 1) degree of every vertex is not greater then 2^t 2) number of all edges is greater than 2^{n +t - O(\log ... 1answer 55 views ### Long term behavior of a certain discrete time dynamical system on graphs Consider the graph (V,E) with vertex set V=\{v_1,...,v_n\} and edge set E\subset V\times V. Further, assume that \forall v_i\in V, (v_i,v_i)\in E. Assume that each vertex has an \textit{... 0answers 44 views ### Largest number of perfect matchings in bounded genus graphs What is the largest number of perfect matchings a genus g bipartite graph on n+m vertices have? 0answers 150 views ### the root lattice, reflections, and a coxeter element Question: Is is possible to realise the positive root lattice \Phi_{\Delta}^{>0} (viewed as an abstract poset) of a root system \Phi_\Delta associated to a Dynkin or affine Dynkin diagram \... 0answers 63 views ### Fraction of graphs with bound on number of perfect matchings Asymptotically what is the fraction of balanced bipartite graph on 2n vertices with at most cn^{\beta} edges having at most n^\alpha perfect matchings for any fixed c,\alpha>0 and fixed \... 1answer 247 views ### When does there exist a convex polyhedron with given edge lengths? Let n be a positive integer, and let n = \ell_1 + \dots + \ell_k be a partition of n. Then there exists a convex polygon with side lengths \ell_1, \dots, \ell_k if and only if all of the \... 1answer 170 views ### Is there a characterization of CI-groups of order less than 100? We know some benefit criterion in articles such as: C‎. ‎H‎. ‎Li‎, ‎On isomorphisms of finite Cayley graphs-a survey‎, ‎Discrete Math.‎, ‎256 (2002) 301-334‎. C‎. ‎H‎. ‎Li‎, ‎Z‎. ‎P‎. ‎Lu‎, ‎P‎. ‎P‎.... 1answer 114 views ### Bases of the special form Let R = \mathrm{GF}(q), S = \mathrm{GF}(q^n), \ n\geq 2 be extension of R, h be a primitive element of S. I want to count or estimate the number N of bases of the following form. Let$$\... 0answers 94 views ### Examples of combinatorial bijections found by considering functors Let us assume that I have two sets of combinatorial objects,$A$and$B$, and I am looking for a bijection (in particular a map)$\psi:A \to B$between these sets, usually required to preserve some ... 2answers 134 views ### Are the Gessel sequence integers composite for all$n\ge 3$? The Gessel sequence is known for Ira Gessel's Lattice Path Conjecture of$2001$, which has been proved by Kauers, Koutschan and Zeilberger in$2009$with the aid of a computer. Later there were found ... 1answer 89 views ### A modified bipartite assignment problem Consider the following optimization problem. I have$n$advisors and$dn$students. I want to assign each student an advisor so that each advisor has exactly$d$students. Each advisor/student pair ... 2answers 130 views ### Finite graph colorings without symmetries Let$G$be a connected finite simple graph with vertex set$V$,$F$a finite set and let$\Delta(G)$denote the degree of$G$, i.e.$\Delta(G)= \max_{v\in V} \deg(v)$. We say that a coloring$\phi\...
Let $G(V,E)$ be a graph. A path whose length is equal to the diameter of a graph is called a diametral path. In a cycle graph every vertex has $2$ diametral paths. Now I need to prove that this: ...