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

learn more… | top users | synonyms (1)

1
vote
1answer
180 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 ...
3
votes
0answers
76 views

Number of linearly independent subsets in arbitrary set

Consider $n$-dimensional vector space $\mathbb{F}_p^n$ over finite field $\mathbb{F}_p$ and a function $a: \mathbb{F}_p^n\rightarrow\mathbb{C}$. Let $$ F(a) = \sum_{\substack{S\subset \mathbb{F}_p^n ...
7
votes
1answer
276 views

Unique factorization of posets

Given two finite posets $P$ and $Q$, we can form the direct product poset $P \times Q$ whose elements are pairs $(p,q) \in P \times Q$ with $(p,q) \leq (p',q')$ if $p \leq p'$ and $q \leq q'$. Let us ...
3
votes
1answer
185 views

Self-containing trees

Suppose that $r^2-r-1=0$ and that $T$ is the tree with root $1$ such that the children of each node $x$ are $rx$ and $x+1$. Remove all duplicates as they occur, and let $T(r)$ denote the remaining ...
-3
votes
2answers
154 views

What is the number of self-inverse permutations on a set of cardinality $N$?

Given a function (aka 'permutation') $f:A \rightarrow A$, where $A$ is a finite set such that $|A| = N$, we call it a self-inverse if $f(f(x)) = x$. The sequence of how many such functions exist for ...
2
votes
0answers
28 views

Ordered cross ratios for the uniform matroid

At the moment I am studying a proof by Gel'fand, Rybnikov and Stone (Theorem 4 in the paper "Projective Orientations of Matroids"). To be more precise, I am try ing to describe a new presentation by ...
1
vote
1answer
71 views

Reference for a local density theorem for binary vectors

I have the following theorem written on my whiteboard, but have misplaced the reference. I believe the probabilistic method may be involved in the proof. Any pointers appreciated. Theorem Let ...
2
votes
0answers
83 views

Maximum number of $4$-cycles

Suppose we have a balanced bipartite planar maximum degree $k$ graph. How many such graphs on $2n$ vertices have at most $f(n)$ maximum number of $4$ cycles for a given function $f:\Bbb ...
1
vote
1answer
171 views

Applications of topology to discrete dynamical systems?

I'd like to know some of the applications of topology to discrete dynamics. By discrete dynamics I loosely mean studying maps between discrete sets. I mean cases where adding a topology to the sets ...
12
votes
2answers
508 views

Lattice n-gons with ordered side lengths 1,2,3,…,n

Consider the octagon in the Cartesian plane with vertices at (0,0), (1,0), (1,2), (4,2), (4,6), (7,2), (7,8), and (0,8). Are there other (infinitely many) polygons, such as this, lying entirely in ...
1
vote
0answers
76 views

maximal sets of vertices that avoids a clique

I am looking for some known algorithm that finds, for a given graph, all the maximal sets of vertices that avoid a clique of some given size $k$. I'd prefer one written in MATLAB, but other languages ...
3
votes
1answer
106 views

chromatic polynomial of G - Join graph

Given a connected graph $G$ with $n$ vertices and given set of $\{m_1,m_2,...,m_n\}$ $n$ integers, we form a new graph $G^{\wedge} $ by considering the complete graph $K_{m_i}$ for each vertex i and ...
1
vote
1answer
56 views

linear recurrence inequality of positive terms

This is a follow up on my previous linear recurrence inequality question. I have some matrices which satisfy a linear recurrence formula of the form $$ A_{n+1} = \alpha A_{n} + \beta A_{n-1},\qquad ...
2
votes
1answer
65 views

linear recurrence inequality

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 ...
1
vote
1answer
70 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$.
4
votes
2answers
181 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 ...
9
votes
0answers
237 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 ...
4
votes
1answer
111 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 ...
6
votes
2answers
187 views

“Diagonalizing” Littlewood-Richardson coefficients

Let's consider the Littlewood-Richardson coefficients $c^{\lambda}_{\mu \nu}$ so that \begin{equation} V_\mu \otimes V_\nu = \bigoplus_\lambda V_\lambda^{\oplus c^{\lambda}_{\mu \nu}} \end{equation} ...
6
votes
0answers
106 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). ...
1
vote
1answer
145 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 ...
2
votes
2answers
938 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 ...
1
vote
0answers
57 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 ...
4
votes
2answers
245 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 ...
7
votes
0answers
130 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 ...
2
votes
0answers
77 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 ...
0
votes
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 ...
1
vote
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?
2
votes
0answers
149 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 ...
3
votes
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 ...
5
votes
1answer
246 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 ...
3
votes
1answer
166 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‎. ...
2
votes
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 ...
4
votes
0answers
93 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 ...
5
votes
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 ...
3
votes
1answer
88 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 ...
5
votes
2answers
126 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 ...
4
votes
3answers
175 views

Relation between diametral path and regularity of a graph

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: ...
13
votes
0answers
381 views

Chasing a 1950s thesis from the University of Dhaka on block designs

On behalf of a friend I am searching for a thesis on block designs from the 1950s. The details are below. Author: Qazi Motahar Husein (Sometimes Husain or Hussein). Title of the Thesis: Symmetrical ...
3
votes
0answers
36 views

Weighted matching and spanning set in $2$-polymatroids

A $2$-polymatroid $P$ is a pair $(S, f)$, where $S$ is a finite set and $f: 2^{S} \rightarrow \mathbb{Z}$ is a function satisfying the following: $f(\varnothing) = 0$; $f(X) \leq f(Y)$, for any $X ...
8
votes
3answers
567 views

What is the optimal size in the finite axiom of symmetry?

Freiling's axiom of symmetry states that if you assign to each real number $x$ a countable set $A_x\subset\mathbb{R}$, then there should be two reals $x,y$ for which $x\notin A_y$ and $y\notin A_x$. ...
1
vote
0answers
48 views

How to count the number of shortest paths in a 2x2 grid? [closed]

Say that we have a 2x2 regular grid or network. We label the nodes 0 to 3 row-wise. Then, for each node, we want to compute the number of shortest paths that pass through them. I have a Python code ...
4
votes
0answers
45 views

Looking for a Collection of Examples and Counter Examples for Assumptions about the Properties of Planar Euclidean TSP Instances?

Where can I find example and counter examples to seemingly plausible assumption about the properties of optimal solutions of planar euclidean TSP instances? The reason for asking is that the ...
1
vote
0answers
69 views

An optimal lower bound related to generators in a boolean interval of finite groups

Let $[H,G]$ be a rank $n$ boolean interval of finite groups (i.e. $[H,G] \simeq B_n$ as lattice). Let the set $E = \{ g \in G \ | \ \langle H,g \rangle = G \}$ Remark: If $g \in E$ then $Hg ...
11
votes
2answers
279 views

Tableaux with limited rows and complementary skew shapes

Given a partition $\mu=(\mu_1,\mu_2...,\mu_d)$, define $\bar\mu=(\mu_1-\mu_d,\mu_1-\mu_{d-1},...,\mu_1-\mu_2,0)$, the complementary shape in the $d\times \mu_1$ rectangle. Then the number of skew ...
5
votes
0answers
157 views

A question on symmetric functions

Let $0 \leq m \leq n$ be integers. The group $S_n$ of permutations acts on the ring $\mathbb{Z}[X_1,\dots,X_n]$ by permuting the coordinates, with fixed subring $\mathbb{Z}[\sigma_1,\dots,\sigma_n]$, ...
12
votes
0answers
170 views

Reference request: exponential growth rates of subword-closed languages are integers

For a language $L$ over the finite alphabet $\Sigma$, let $L_n$ denote the set of words in $L$ of length $n$. The word $u$ is a subword of $w$ if $u$ can be obtained from $w$ by deleting letters. The ...
2
votes
0answers
87 views

Growth of inner products between two random vectors on the sparse hypercube

We define the $s$-sparse hypercube in $\mathbb{R}^d$ as \begin{align} \mathbb{H}_s = \bigl \{ {\bf{v}} \in \{ -1, 0 , 1\}^d \colon \| {\bf{v}} \|_0 = s \bigr\}, \end{align} where $ \| {\bf v} \|_0 $ ...
12
votes
2answers
206 views

Permutation search problems with no known $o(n!)$ algorithms

I am looking for problems for whose solution no known subfactorial algorithms are known. I am particularly interested in questions of isomorphism; that is, is there a permutation that converts one ...
2
votes
0answers
53 views

What do you call the collection of all sets shattered by $F$?

The proof of Pajor's lemma uses the collection of all sets $S\subseteq X$ shattered by some $F\subseteq 2^X$. Is there a standard term for the former object? I've been privately referring to it as the ...