Search results for "Mathematics - Combinatorics"
showing 7 items of 67 documents
The smallest singular value of a shifted $d$-regular random square matrix
2017
We derive a lower bound on the smallest singular value of a random d-regular matrix, that is, the adjacency matrix of a random d-regular directed graph. Specifically, let $$C_1<d< c n/\log ^2 n$$ and let $$\mathcal {M}_{n,d}$$ be the set of all $$n\times n$$ square matrices with 0 / 1 entries, such that each row and each column of every matrix in $$\mathcal {M}_{n,d}$$ has exactly d ones. Let M be a random matrix uniformly distributed on $$\mathcal {M}_{n,d}$$ . Then the smallest singular value $$s_{n} (M)$$ of M is greater than $$n^{-6}$$ with probability at least $$1-C_2\log ^2 d/\sqrt{d}$$ , where c, $$C_1$$ , and $$C_2$$ are absolute positive constants independent of any other parameter…
THE HOMOLOGY OF DIGRAPHS AS A GENERALIZATION OF HOCHSCHILD HOMOLOGY
2010
J. Przytycki has established a connection between the Hochschild homology of an algebra $A$ and the chromatic graph homology of a polygon graph with coefficients in $A$. In general the chromatic graph homology is not defined in the case where the coefficient ring is a non-commutative algebra. In this paper we define a new homology theory for directed graphs which takes coefficients in an arbitrary $A-A$ bimodule, for $A$ possibly non-commutative, which on polygons agrees with Hochschild homology through a range of dimensions.
On List Coloring with Separation of the Complete Graph and Set System Intersections
2022
We consider the following list coloring with separation problem: Given a graph $G$ and integers $a,b$, find the largest integer $c$ such that for any list assignment $L$ of $G$ with $|L(v)|= a$ for any vertex $v$ and $|L(u)\cap L(v)|\le c$ for any edge $uv$ of $G$, there exists an assignment $\varphi$ of sets of integers to the vertices of $G$ such that $\varphi(u)\subset L(u)$ and $|\varphi(v)|=b$ for any vertex $u$ and $\varphi(u)\cap \varphi(v)=\emptyset$ for any edge $uv$. Such a value of $c$ is called the separation number of $(G,a,b)$. Using a special partition of a set of lists for which we obtain an improved version of Poincar\'e's crible, we determine the separation number of the c…
Asymptotic bit frequency in Fibonacci words
2021
It is known that binary words containing no $k$ consecutive 1s are enumerated by $k$-step Fibonacci numbers. In this note we discuss the expected value of a random bit in a random word of length $n$ having this property.
On the tensor degree of finite groups
2013
We study the number of elements $x$ and $y$ of a finite group $G$ such that $x \otimes y= 1_{_{G \otimes G}}$ in the nonabelian tensor square $G \otimes G$ of $G$. This number, divided by $|G|^2$, is called the tensor degree of $G$ and has connection with the exterior degree, introduced few years ago in [P. Niroomand and R. Rezaei, On the exterior degree of finite groups, Comm. Algebra 39 (2011), 335--343]. The analysis of upper and lower bounds of the tensor degree allows us to find interesting structural restrictions for the whole group.
On several notions of complexity of polynomial progressions
2021
For a polynomial progression $$(x,\; x+P_1(y),\; \ldots,\; x+P_{t}(y)),$$ we define four notions of complexity: Host-Kra complexity, Weyl complexity, true complexity and algebraic complexity. The first two describe the smallest characteristic factor of the progression, the third one refers to the smallest-degree Gowers norm controlling the progression, and the fourth one concerns algebraic relations between terms of the progressions. We conjecture that these four notions are equivalent, which would give a purely algebraic criterion for determining the smallest Host-Kra factor or the smallest Gowers norm controlling a given progression. We prove this conjecture for all progressions whose ter…
On arithmetic sums of Ahlfors-regular sets
2021
Let $A,B \subset \mathbb{R}$ be closed Ahlfors-regular sets with dimensions $\dim_{\mathrm{H}} A =: \alpha$ and $\dim_{\mathrm{H}} B =: \beta$. I prove that $$\dim_{\mathrm{H}} [A + \theta B] \geq \alpha + \beta \cdot \tfrac{1 - \alpha}{2 - \alpha}$$ for all $\theta \in \mathbb{R} \, \setminus \, E$, where $\dim_{\mathrm{H}} E = 0$.