ON A VARIANT OF FLORY MODEL TOMISLAV DO SLIC MATE PULJIZ STJEPAN SEBEK AND JOSIP ZUBRINI C Abstract. We consider a one-dimensional variant of a recently introduced set-

2025-05-02 0 0 521.08KB 37 页 10玖币
侵权投诉
ON A VARIANT OF FLORY MODEL
TOMISLAV DOˇ
SLI´
C, MATE PULJIZ, STJEPAN ˇ
SEBEK, AND JOSIP ˇ
ZUBRINI´
C
Abstract. We consider a one-dimensional variant of a recently introduced set-
tlement planning problem in which houses can be built on finite portions of the
rectangular integer lattice subject to certain requirements on the amount of inso-
lation they receive. In our model, each house occupies a unit square on a 1 ×n
strip, with the restriction that at least one of the neighboring squares must be free.
We are interested mostly in situations in which no further building is possible, i.e.
in maximal configurations of houses in the strip. We reinterpret the problem as
a problem of restricted packing of vertices in a path graph and then apply the
transfer matrix method in order to compute the bivariate generating functions
for the sequences enumerating all maximal configurations of a given length with
respect to the number of houses. This allows us to determine the asymptotic be-
havior of the enumerating sequences and to compute some interesting statistics.
Along the way, we establish close connections between our maximal configurations
and several other types of combinatorial objects, including restricted permutations
and walks on certain small oriented graphs. In all cases we provide combinatorial
proofs. We then generalize our results in several directions by considering multi-
story houses, by varying the insolation restrictions, and, finally, by considering
strips of width 2 and 3. At the end we comment on several possible directions of
future research.
1. Introduction
Many problems of practical importance can be formulated in terms of packings.
Intuitively, a packing is any arrangement of non-overlapping copies from a (usually
finite) collection of objects Pwithin a prescribed part of a large(r) set E. It often
happens that both the large set and the objects being packed can be naturally
endowed with the same type of discrete structure. In such cases, general packings can
be successfully modeled by packings of graphs. If, for example, Ecan be represented
by a graph Gand elements of Pby graphs H1, . . . , Hk, then a P-packing of Gis a
collection of vertex-disjoint subgraphs of Gsuch that each of them is isomorphic to
some Hi,i= 1, . . . , k. When Pconsists of a single element H, one simply speaks of
H-packings of G.
Clearly, one would expect that the difficulty of packing problems increases with
the increase of the complexity of H. Indeed, the simplest non-trivial case, H=K2,
is well researched, while the results on larger Hare much less abundant. This does
not prevent graph packings from being a very versatile tool; even the simplest case of
packing dimers (H=K2) into a larger graph is one of most commonly used models
in several areas of physics and chemistry. It suffices to mention the Ising model
of magnetic materials and the concept of the topological resonant energy, crucial
for stability of conjugated molecules. Both models employ perfect matchings, i.e.
packings of dimers covering all vertices of the underlying graph. For a very brief
2020 Mathematics Subject Classification. 05B40, 05A15, 05A16, 05A19, 00A67.
Key words and phrases. Maximal packing, generating functions, bijective proof, settlement model.
1
arXiv:2210.12411v1 [math.CO] 22 Oct 2022
2 T. DOˇ
SLI ´
C, M. PULJIZ, S. ˇ
SEBEK, AND J. ˇ
ZUBRINI ´
C
introduction to both topics we refer the reader to [17,§8.7] and references therein.
For some recent results on packing larger Hsee, for example, [5,6].
In this paper we look at a problem which can be modeled by packing even simpler
graphs, the copies of K1, into finite portions of regular rectangular lattice. Without
further restrictions this problem would be trivial, but our problem imposes restric-
tions that arise quite naturally in the context of settlement growth and planning.
It turns out that with those restrictions even packing the simplest possible graphs,
K1, into finite pieces of the square lattice gives rise to very interesting behavior and
exhibits often surprising relations with several other classes of combinatorial objects.
(Another non-trivial problem which can be reduced to restricted packings of trivial
graph K1is the problem of finding a large independent set in a given graph.)
All the aforementioned packing problems can be studied in a static or a dynamic
variant. In the present work we focus only on the static models with the aim
to enumerate all configurations that arise in such models and that satisfy certain
additional requirements. The study of the dynamic variant of the same models
aims to find the distribution of configurations constructed by a random process in
which the pieces from Parrive sequentially and are placed randomly onto available
locations in Euntil saturation. These kinds of models that evolve over time are
extensively studied, see [14,§7] for introduction, and [10–13] for some recent results
in this direction. The efforts to extend our results in this direction are currently
underway.
In [20] three of the present authors introduced the following settlement model. A
rectangular m×ntract of land, with sides oriented north-south and east-west, is
divided into mn unit squares, see Figure 1. Each square lot can be either occupied
(by a house) or left vacant. An arrangement of houses on such a tract of land is
called a configuration and can be encoded as an m×nmatrix C, where ci,j = 1 if
the lot (i, j) is occupied, and ci,j = 0 otherwise.
North
Figure 1. An example of a tract of land (m= 5, n= 7).
A configuration Cis permissible if no occupied lot (i, j) borders simultaneously
with three other occupied lots to its east, south and west — in other words — the
house on the position (i, j) receives the sunlight during at least one part of the day
(be it in the morning from the east, or during the midday from the south, or in the
evening from the west).
As is the case with other packings, one is, naturally, interested in large permissible
configurations, since the small ones tend to be trivial and easy to construct. One
way of being large is to have the largest possible number of occupied lots, hence the
largest possible size. We call such configurations maximum configurations (in [20,21]
these were called efficient). Another, more interesting, way of being large is in the
sense of set inclusion. A permissible configuration Cis maximal if no additional
houses can be added to the configuration without rendering it impermissible, see
ON A VARIANT OF FLORY MODEL 3
x
x
(a) Impermissible (b) Permissible (c) Maximal
Figure 2. Examples of impermissible, permissible and maximal con-
figuration on a 5 ×4 tract of land. ‘x’ marks a house blocked from the
sunlight.
Figure 2. Unlike the maximum configurations, the maximal ones usually come in a
range of different sizes, and it is of interest to know the exact distribution of sizes.
Moreover, here also the smallest such configurations are interesting (in [20,21] these
were called inefficient), as they describe either the worst possible outcome if we are
interested in packing as many elements as possible, or the best possible outcome
if we are trying to satisfy certain needs by the smallest possible number of packed
objects.
The authors in [20] found maximal configurations with the lowest occupancy (the
number of houses in a configuration) among all the maximal configurations on an
m×ngrid. They also obtained bounds on the highest occupancy possible. A natural
next step would be to find the total number of all maximal configurations for a given
grid and to refine the enumeration by the number of occupied lots. The problem
seems to be too hard in the general m×ncase. Hence, in this paper we consider
its restriction to the one-dimensional case 1 ×nto which we can apply the transfer
matrix method. This method allows us to obtain a complete solution of the one-
dimensional case by computing and analyzing the bivariate generating functions
for the corresponding enumerating sequences. Our results could be, in principle,
generalized to larger grids; indeed, for grids of size 2 ×nand 3 ×nwe derive
(bivariate) generating functions counting the number of maximal configurations by
the same transfer matrix method used in the 1 ×ncase. However, the calculations
get increasingly infeasible for larger strips and we decided not to pursue it beyond
m= 3.
The transfer matrix method, see [24,§4.7] or [7,§V], and also [16,§2–4], is a
well known method for counting words of a regular language. Applicability of this
method to our setting relies on the fact that permissibility as well as maximality
of a configuration can be verified by inspecting only finite size patches of a given
configuration. The limitation, however, is that the method deals with, essentially,
one dimensional objects, so we first consider a modification of the settlement model
on the 1 ×ngrid. This modification, defined later in text, we call the Riviera
model. It turns out that the Riviera model can be seen as a variant of Flory polymer
model [8] which is in turn related to Page-R´enyi parking process [9,19].
Surprisingly, the maximal configurations of the Riviera model turn out to be
related to a certain kind of restricted permutations introduced in [1]. We were able
to construct an explicit bijection translating between the two. Also, we construct
another bijection connecting the Riviera model with the closed walks on P3graph
with an added loop.
4 T. DOˇ
SLI ´
C, M. PULJIZ, S. ˇ
SEBEK, AND J. ˇ
ZUBRINI ´
C
The paper is organized as follows. In Section 2we introduce the Riviera model.
We find the bivariate generating function counting the number of maximal configu-
rations of length nwith precisely khouses (n, k ∈N). Furthermore, we relate the
Riviera model with some other combinatorial objects that were already studied in
the literature. In Section 3we generalize the Riviera model introduced in Section
2in the sense that we allow houses to have multiple stories. Additionally, we com-
ment on the close relation between the Riviera model and the famous Flory model.
In Section 4we deal with configurations on m×ngrids with m= 2 and m= 3.
Finally, in Section 5we recapitulate our findings and indicate several possible direc-
tions of future research. Some lengthy formulas are relegated to Appendix in order
to improve legibility.
A note on notation: Whenever a non-integer decimal is encountered in the text,
its value should be interpreted as an approximation of the true value rounded to six
decimal places. By an∼bn(as n→ ∞) we mean limn→∞ an
bn= 1. In several places
in the text we use the same name for different functions. Most prominently, the
generating function for almost every model is denoted as F(x), F(x, y), or F(x, y, z).
This should not lead to any confusion, as it is always clear from the context to which
function the text refers.
2. Riviera model
We introduce a 1D-modification of the above settlement planning model which
ignores the possibility of obtaining sunlight from the south, but instead retains only
the constraints pertaining to the east and west directions. As this is a model on
a strip of land, it resembles a Mediterranean settlement along the coast (riviera),
hence the name. The configuration of built houses is represented with a row vector1
C= (ck), where ck= 1 if the lot kis occupied and ck= 0 otherwise. Similarly as
before, a configuration is said to be permissible if every occupied lot has at least
one neighboring lot unoccupied (except maybe for the first and the last lot which
receive sunlight from the boundary) so that it is not blocked from the sunlight.
Among permissible configurations, we are interested in the maximal ones, namely
configurations such that any addition of a house on an unoccupied lot would result
in an impermissible configuration.
The properties of maximality and permissibility are locally verifiable in a sense
that, if one wants to check whether a state of a certain lot (occupied or unoccupied)
has caused the configuration to be impermissible or not maximal, one only needs to
check the situation on the lots in a certain finite radius of the observed lot, where
that radius is uniform for each lot on the tract of land.
More precisely, to verify that a configuration is permissible, one needs to check
that no occupied lot has both of its neighboring lots occupied as well. This can be
done by inspecting all the length 3 substrings of a configuration. And to verify that
a configuration is maximal, one needs to check, additionally, that no unoccupied
lots can be built on. This can be done by observing the eastern two and western
two lots around the unoccupied lot, i.e. by inspecting all the length 5 substrings of
a padded (see Remark 2.2) configuration.
1We write configurations as strings of 0’s and 1’s, and we refer to any consecutive sequence of
letters in a configuration as a substring or a (sub)word in that configuration.
ON A VARIANT OF FLORY MODEL 5
This property of local verifiability of a constraint which describes the model is a
recurring motif throughout our analysis of related models in this paper.
Lemma 2.1. Let n∈N. A configuration C∈ {0,1}nin the Riviera model is
maximal if and only if, when padded with zeros, it does not contain any of the
following (decorated) substrings:
(2.1) 111,000,0100,0010.
Remark 2.2. Throughout the paper, unless stated otherwise, we assume that the
lots on the boundary can get sunlight from the boundary side, i.e. we assume that
our configurations are padded with zeros. When inspecting whether a configuration
c1. . . cncontains a decorated word d1. . . dk. . . dl, we check against a padded word
. . . 000c1. . . cn000 . . . but with the underlined letter of the decorated word aligned
with cifor i= 1, . . . , n. This is necessary as e.g. the configuration 10011 would
otherwise be considered allowed (not containing any of the forbidden substrings),
although it is not maximal.
Proof of Lemma 2.1.A configuration Cis maximal if and only if it is permissible
and for each k= 1, . . . , n one has
ck= 0 =⇒(ck−1= 1 and ck+1 = 1) or (ck−1= 1 and ck−2= 1)
or (ck+1 = 1 and ck+2 = 1).
The contrapositive of the above implication reads
(2.2) (ck−1= 0 or ck+1 = 0) and (ck−1= 0 or ck−2= 0)
and (ck+1 = 0 or ck+2 = 0) =⇒ck= 1.
This illustrates the fact that, if there is no danger of losing permissibility by setting
ck= 1, then one should put ck= 1 (with the agenda of obtaining maximality).
By using the distributive property and after removing redundant terms the left
hand side of (2.2) can be rewritten as
(2.3) (ck−1= 0 and ck+1 = 0) or (ck−1= 0 and ck+2 = 0)
or (ck+1 = 0 and ck−2= 0) =⇒ck= 1.
From here we can compile the list of forbidden words. We include 111 to ensure
permissibility, and (2.3) gives us five more words 000, 00∗0, 0∗00 where ∗stands for
any symbol. As the words 0000 and 0000 are already excluded by 000, the set of
forbidden (decorated) words is
{111,000,0010,0100}.
Remark 2.3. An alternative approach for constructing the set of forbidden words,
once we know that it suffices checking substrings of length 5, is to consider all 25
binary words of length 5 and, out of those, take words that do not appear in any
finite maximal configuration to be the forbidden set of words. This approach is more
amenable for use in a computer algorithm and we will make use of it later on.
Using this approach one would come up with the set of forbidden length 5 words
{∗111∗,∗000∗,01000,01001,00010,10010},
which again can be reduced to {111,000,0010,0100}. As before, ∗stands for any
symbol, and e.g. the string ∗111∗actually accounts for 4 different (decorated) words.
摘要：

ONAVARIANTOFFLORYMODELTOMISLAVDOSLIC,MATEPULJIZ,STJEPANSEBEK,ANDJOSIPZUBRINICAbstract.Weconsideraone-dimensionalvariantofarecentlyintroducedset-tlementplanningprobleminwhichhousescanbebuilton niteportionsoftherectangularintegerlatticesubjecttocertainrequirementsontheamountofinso-lationtheyrecei...

展开>> 收起<<
ON A VARIANT OF FLORY MODEL TOMISLAV DO SLIC MATE PULJIZ STJEPAN SEBEK AND JOSIP ZUBRINI C Abstract. We consider a one-dimensional variant of a recently introduced set-.pdf

共37页,预览5页

还剩页未读， 继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

相关推荐

更多
立即下载
分类：图书资源 价格：10玖币 属性：37 页 大小：521.08KB 格式：PDF 时间：2025-05-02

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

热门标签

人际关系 动力学连接体 力的合成 配电装置 高考理综 全宋诗作者索引 公务员考试
/ 37
评分 收藏
分享
立即下载
客服
关注