Amorphic association schemes from bent partitions

Bent partitions are partitions of an elementary abelian group, which have similarities to partitions from spreads. In fact, a spread partition is a special case of a bent partition. In particular, bent partitions give rise to a large number of (vectorial) bent functions. Examples of bent partitions, which generalize the Desarguesian spread, have been presented by Anbar, Meidl and Pirsic, 2021, 2022. Bent partitions, which generalize some other classes of (pre)semifield spreads, have been presented by Anbar, Kalaycı, Meidl 2023. In this article, it is shown that these bent partitions induce $(p^k+1)$-class amorphic associations schemes on ${\mathbb{F}}_{p^m}\times {\mathbb{F}}_{p^m}$, where k is a divisor of m with special properties. This implies a construction of amorphic association schemes from some classes of (pre)semifields.     

Note on the Monotonicity of Coefficients for Some q-Series Arising from Ramanujan's Lost Notebook

In this note, we shall give a partition-theoretic interpretation which explains the non-negativity of the coefficients of some q-series arising from Ramanujan's Lost Notebook and prove the almost-increasingness of the coefficients via a vector partition generating function.     

On the shape of decomposable trees

A n-vertex graph is said to be decomposable if, for any partition (λ₁,…,λ_p) of the integer n, there exists a sequence (V₁,…,V_p) of connected vertex-disjoint subgraphs with |V_i|=λ_i. The aim of the paper is to study the homeomorphism classes of decomposable trees. More precisely, we show that homeomorphism classes containing decomposable trees with an arbitrarily large minimal distance between all pairs of distinct vertices of degree different from 2, is exactly the set of combs.     

A poset structure on quasifibonacci partitions

In this paper, we study partitions of positive integers into distinct quasifibonacci numbers. A digraph and poset structure is constructed on the set of such partitions. Furthermore, we discuss the symmetric and recursive relations between these posets. Finally, we prove a strong generalization of Robbins' result on the coefficients of a quasifibonacci power series.     

On an extension of a combinatorial identity

Using Frobenius partitions we extend the main results of [4]. This leads to an infinite family of 4-way combinatorial identities. In some particular cases we get even 5-way combinatorial identities which give us four new combinatorial versions of Göllnitz-Gordon identities.     

Instanton partition functions and M-theory

We discuss instanton partition functions in various spacetime dimensions. These partition functions capture some information about the spectrum of the supersymmetric gauge theories and their low-energy dynamics. Some of these theories can be defined microscopically only through string theory. Remarkably, they even know about the M-theory. Our conjectures include the identities between the generalization of the MacMahon formula and the character of M-theory, compactified down to 0 + 1 dimension. This article is based on the 5th Takagi Lectures that the author delivered at the University of Tokyo on October 4 and 5, 2008.     

Brick partitions of graphs

For each rational number q=b/c where b≥c are positive integers, we define a q-brick of G to be a maximal subgraph H of G such that cH has b edge-disjoint spanning trees, and a q-superbrick of G to be a maximal subgraph H of G such that cH−e has b edge-disjoint spanning trees for all edges e of cH, where cH denotes the graph obtained from H by replacing each edge by c parallel edges. We show that the vertex sets of the q-bricks of G partition the vertex set of G, and that the vertex sets of the q-superbricks of G form a refinement of this partition. The special cases when q=1 are the partitions given by the connected components and the 2-edge-connected components of G, respectively. We obtain structural results on these partitions and describe their relationship to the principal partitions of a matroid.     

Polychromatic colorings of arbitrary rectangular partitions

A general (rectangular) partition is a partition of a rectangle into an arbitrary number of non-overlapping subrectangles. This paper examines vertex 4-colorings of general partitions where every subrectangle is required to have all four colors appear on its boundary. It is shown that there exist general partitions that do not admit such a coloring. This answers a question of Dimitrov et al. [D. Dimitrov, E. Horev, R. Krakovski, Polychromatic colorings of rectangular partitions, Discrete Mathematics 309 (2009) 2957-2960]. It is also shown that the problem to determine if a given general partition has such a 4-coloring is NP-Complete. Some generalizations and related questions are also treated.     

点染色3-边划分图的最小度(英文)

Addrio-Berry L[1]已经证明了最小度至少为1000的图可以点染色3-边划分,在本文中,我们将其结果改进到了最小度至少为662.     

Acyclic dominating partitions

Given a graph G=(V, E), let ${\mathcal{P}}$ be a partition of V. We say that ${\mathcal{P}}$ is dominating if, for each part P of ${\mathcal{P}}$, the set V\P is a dominating set in G (equivalently, if every vertex has a neighbor of a different part from its own). We say that ${\mathcal{P}}$ is acyclic if for any parts P, P′ of ${\mathcal{P}}$, the bipartite subgraph G[P, P′] consisting of the edges between P and P′ in ${\mathcal{P}}$ contains no cycles. The acyclic dominating number ad(G) of G is the least number of parts in any partition of V that is both acyclic and dominating; and we shall denote by ad(d) the maximum over all graphs G of maximum degree at most d of ad(G). In this article, we prove that ad(3)=2, which establishes a conjecture of P. Boiron, É. Sopena, and L. Vignal, DIMACS/DIMATIA Conference “Contemporary Trends in Discrete Mathematics”, 1997, pp. 1–10. For general d, we prove the upper bound ad(d)=O(dlnd) and a lower bound of ad(d)=Ω(d). © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 292–311, 2010