Source author record

Amin Bahmanian

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics

Catalog footprint

Research overview

9works

2topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Embedding Irregular Colorings into Connected Factorizations

For $r:=(r_1,\dots,r_k)$ , an $r$ -factorization of the complete $λ$ -fold $h$ -uniform $n$ -vertex hypergraph $λK_n^h$ is a partition of (the edges of) $λK_n^h$ into $F_1,\dots, F_k$ such that for $i=1,\dots,k$ , $F_i$ is $r_i$ -regular and spanning. Suppose that $n \geq (h-1)(2m-1)$ . Given a partial $r$ -factorization of $λK_m^h$ , that is, a coloring (i.e. partition) $P$ of the edges of $λK_m^h$ into $F_1,\dots, F_k$ such that for $i=1,\dots,k$ , $F_i$ is spanning and the degree of each vertex in $F_i$ is at most $r_i$ , we find necessary and sufficient conditions that ensure $P$ can be extended to a connected $r$ -factorization of $λK_n^h$ (i.e. an $r$ -factorization in which each factor is connected). Moreover, we prove a general result that implies the following. Given a partial $s$ -factorization $P$ of any sub-hypergraph of $λK_m^h$ , where $s:=(s_1,\dots,s_q)$ and $q$ is not too big, we find necessary and sufficient conditions under which $P$ can be embedded into a connected $r$ -factorization of $λK_n^h$ . These results can be seen as unified generalizations of various classical combinatorial results such as Cruse's theorem on embedding partial symmetric latin squares, Baranyai's theorem on factorization of hypergraphs, Hilton's theorem on extending path decompositions into Hamiltonian decompositions, Häggkvist and Hellgren's theorem on extending 1-factorizations, and Hilton, Johnson, Rodger, and Wantland's theorem on embedding connected factorizations.

preprint2022arXiv

On Factors with Prescribed Degrees in Bipartite Graphs

We establish a new criterion for a bigraph to have a subgraph with prescribed degree conditions. We show that the bigraph $G[X,Y]$ has a spanning subgraph $F$ such that $g(x)\leq deg_F(x) \leq f(x)$ for $x\in X$ and $deg_F(y) \leq f(y)$ for $y\in Y$ if and only if $\sum\nolimits_{b\in B} f(b)\geq \sum\nolimits_{a\in A} \max \big\{0, g(a) - deg_{G-B}(a)\big\}$ for $A\subseteq X, B\subseteq Y$ . Using Folkman-Fulkerson's Theorem, Cymer and Kano found a different criterion for the existence of such a subgraph (Graphs Combin. 32 (2016), 2315--2322). Our proof is self-contained and relies on alternating path technique. As an application, we prove the following extension of Hall's theorem. A bigraph $G[X,Y]$ in which each edge has multiplcity at least $m$ has a subgraph $F$ with $g(x)\leq deg_F(x)\leq f(x)\leq deg(x)$ for $x\in X$ , $deg_F(y)\leq m$ for $y\in Y$ if and only if $\sum_{y\in N_G(S)}f(y)\geq \sum_{x\in S}g(x)$ for $S\subseteq X$ .

preprint2022arXiv

On Layer-Rainbow Latin Cubes Containing Layer-Rainbow Latin Cubes

Despite the fact that latin cubes have been studied since in the 1940's, there are only a few results on embedding partial latin cubes, and all these results are far from being optimal with respect to the size of the containing cube. For example, the bound of the 1970's result of Cruse that a partial latin cube of order $n$ can be embedded into a latin cube of order $16n^4$ , was only improved very recently by Potapov to $n^3$ . In this note, we prove the first such optimal result by showing that a layer-rainbow latin cube of order $m$ can be embedded into a layer-rainbow latin cube of order $n$ if and only if $n\geq 2m$ . A layer-rainbow latin cube $L$ of order $n$ is an $n\times n\times n$ array filled with $n^2$ symbols such that each layer parallel to each face (obtained by fixing one coordinate) contains every symbol exactly once.

preprint2022arXiv

Ryser's Theorem for $ρ$ -latin Rectangles

Let $L$ be an $n\times n$ array whose top left $r\times s$ subarray is filled with $k$ different symbols, each occurring at most once in each row and at most once in each column. We find necessary and sufficient conditions that ensure the remaining cells of $L$ can be filled such that each symbol occurs at most once in each row and at most once in each column, and each symbol occurs a prescribed number of times in $L$ . The case where the prescribed number of times each symbol occurs is $n$ was solved by Ryser (Proc. Amer. Math. Soc. 2 (1951), 550--552), and the case $s=n$ was settled by Goldwasser et al. (J. Combin. Theory Ser. A 130 (2015), 26--41). Our technique leads to a very short proof of the latter.

preprint2022arXiv

Symmetric Layer-Rainbow Colorations of Cubes

Can we color the $n^3$ cells of an $n\times n\times n$ cube $L$ with $n^2$ colors in such a way that each layer parallel to each face contains each color exactly once and that the coloring is symmetric so that $L_{ij\ell}=L_{j\ell i}=L_{\ell ij}$ for distinct $i,j,\ell \in \{1,\dots,n\}$ , and $L_{iij}=L_{jj i}, L_{iji}=L_{jij}, L_{ij j}=L_{jii}$ for $i,j\in \{1,\dots,n\}$ ? Using transportation networks, we show that such a coloring is possible if and only if $n\equiv 0,2 \mod 3$ (with two exceptions, $n=1$ and $n\neq 3$ ). Motivated by the designs of experiments, the study of these objects (without symmetry) was initiated by Kishen and Fisher in the 1940's. These objects are also closely related to orthogonal arrays whose existence has been extensively investigated, and they are natural three-dimensional analogues of symmetric latin squares.

preprint2021arXiv

Extending Edge-colorings of Complete Hypergraphs into Regular Colorings

Let $\binom{X}{h}$ be the collection of all $h$ -subsets of an $n$ -set $X\supseteq Y$ . Given a coloring (partition) of a set $S\subseteq \binom{X}{h}$ , we are interested in finding conditions under which this coloring is extendible to a coloring of $\binom{X}{h}$ so that the number of times each element of $X$ appears in each color class (all sets of the same color) is the same number $r$ . The case $S=\varnothing, r=1$ was studied by Sylvester in the 18th century, and remained open until the 1970s. The case $h=2,r=1$ is extensively studied in the literature and is closely related to completing partial symmetric Latin squares. For $S=\binom{Y}{h}$ , we settle the cases $h=4, |X|\geq 4.847323|Y|$ , and $h=5, |X|\geq 6.285214|Y|$ completely. Moreover, we make partial progress toward solving the case where $S=\binom{X}{h}\backslash \binom{Y}{h}$ . These results can be seen as extensions of the famous Baranyai's theorem, and make progress toward settling a 40-year-old problem posed by Cameron.

preprint2021arXiv

Factorizations of Complete Multipartite Hypergraphs

In a mathematics workshop with $mn$ mathematicians from $n$ different areas, each area consisting of $m$ mathematicians, we want to create a collaboration network. For this purpose, we would like to schedule daily meetings between groups of size three, so that (i) two people of the same area meet one person of another area, (ii) each person has exactly $r$ meeting(s) each day, and (iii) each pair of people of the same area have exactly $λ$ meeting(s) with each person of another area by the end of the workshop. Using hypergraph amalgamation-detachment, we prove a more general theorem. In particular we show that above meetings can be scheduled if: $3 \ | \ rm$ , $2 \ | \ rnm$ and $r \ | \ 3λ(n-1)\binom{m}{2}$ . This result can be viewed as an analogue of Baranyai's theorem on factorizations of complete multipartite hypergraphs.

preprint2020arXiv

Connected Fair Detachments of Hypergraphs

Let $\mathcal G$ be a hypergraph whose edges are colored. An {\it $(α,n)$ -detachment} of $\mathcal G$ is a hypergraph obtained by splitting a vertex $α$ into $n$ vertices, say $α_1,\dots,α_n$ , and sharing the incident hinges and edges among the subvertices. A detachment is {\it fair} if the degree of vertices and multiplicity of edges are shared as evenly as possible among the subvertices within the whole hypergraph as well as within each color class. In this paper we solve an open problem from 70s by finding necessary and sufficient conditions under which a $k$ -edge-colored hypergraph $\mathcal G$ has a fair detachment in which each color class is connected. Previously, this was not even known for the case when $\mathcal G$ is an arbitrary graph (i.e. 2-uniform hypergraph). We exhibit the usefulness of our theorem by proving a variety of new results on hypergraph decompositions, and completing partial regular combinatorial structures.

preprint2020arXiv

On Regular Set Systems Containing Regular Subsystems

Let $X,Y$ be finite sets, $r,s,h, λ\in \mathbb{N}$ with $s\geq r, X\subsetneq Y$ . By $λ\binom{X}{h}$ we mean the collection of all $h$ -subsets of $X$ where each subset occurs $λ$ times. A coloring of $λ\binom{X}{h}$ is {\it $r$ -regular} if in every color class each element of $X$ occurs $r$ times. A one-regular color class is a {\it perfect matching}. We are interested in the necessary and sufficient conditions under which an $r$ -regular coloring of $λ\binom{X}{h}$ can be embedded into an $s$ -regular coloring of $λ\binom{Y}{h}$ . Using algebraic techniques involving glueing together orbits of a suitably chosen cyclic group, the first author and Newman (Combinatorica 38 (2018), no. 6, 1309--1335) solved the case when $λ=1,r=s, \gcd (|X|,|Y|,h)=\gcd(|Y|,h)$ . Using purely combinatorial techniques, we nearly settle the case $h=4$ . Two major challenges include finding all the necessary conditions, and obtaining the exact bound for $|Y|$ . It is worth noting that completing partial symmetric latin squares is closely related to the case $λ=r=s=1, h=2$ which was solved by Cruse (J. Comb. Theory Ser. A 16 (1974), 18--22).

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Amin Bahmanian

Research overview

Is this your work?

9 publications

Embedding Irregular Colorings into Connected Factorizations

On Factors with Prescribed Degrees in Bipartite Graphs

On Layer-Rainbow Latin Cubes Containing Layer-Rainbow Latin Cubes

Ryser's Theorem for $ρ$ -latin Rectangles

Symmetric Layer-Rainbow Colorations of Cubes

Extending Edge-colorings of Complete Hypergraphs into Regular Colorings

Factorizations of Complete Multipartite Hypergraphs

Connected Fair Detachments of Hypergraphs

On Regular Set Systems Containing Regular Subsystems

See the researcher in context

Building this map preview

Amin Bahmanian

Research overview

Is this your work?

9 publications

Embedding Irregular Colorings into Connected Factorizations

On Factors with Prescribed Degrees in Bipartite Graphs

On Layer-Rainbow Latin Cubes Containing Layer-Rainbow Latin Cubes

Ryser's Theorem for ρρρ-latin Rectangles

Symmetric Layer-Rainbow Colorations of Cubes

Extending Edge-colorings of Complete Hypergraphs into Regular Colorings

Factorizations of Complete Multipartite Hypergraphs

Connected Fair Detachments of Hypergraphs

On Regular Set Systems Containing Regular Subsystems

See the researcher in context

Building this map preview

Ryser's Theorem for $ρ$ -latin Rectangles