Masahiro Hachimori
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Masahiro Hachimori has a total of 12 co-authors. Here are the top co-authors by number of shared publications:
- Kenji Kashiwabara
Graduate School of Arts and Sciences, The University of Tokyo, Tokyo, Japan
3 shared publications - Jinping Fan
Univ Tsukuba, Grad Sch Syst & Informat Engn, Tsukuba, Ibaraki 3058573, Japan
2 shared publications - Ying Miao
University of Tsukuba
2 shared publications - Yujie Gu
Graduate School/Faculty of Information Science and Electrical Engineering, Kyushu University, Fukuoka, Japan
2 shared publications - Hikoe Enomoto
Department of Mathematics, Keio University, Yokohama, 223‐8522 Japan
1 shared publication Kenji Kashiwabara
Institute of Systems and Information Engineering Graduate School of Arts and Sciences University of Tsukuba The University of Tokyo
1 shared publication
Latest Publications
- Open Access
Average-Rare Order Ideals in Functional Preorders
We prove that for the preorder induced by a function f: V -> V, the family of all order ideals is average-rare, that is, its normalized degree sum (nds) is nonpositive. As a base case in our reduction, we establish the same result for functional partial orders (or rooted forests). We also propose a conjecture related to Frankl's Conjecture. All proofs have been formally verified in the proof assistant Lean 4.
Open AccessAverage-Rare Order Ideals in Functional Preorders
We prove that for the preorder induced by a function f: V -> V, the family of all order ideals is average-rare, that is, its normalized degree sum (nds) is nonpositive. As a base case in our reduction, we establish the same result for functional partial orders (or rooted forests). We also propose a conjecture related to Frankl's Conjecture. All proofs have been formally verified in the proof assistant Lean 4.
- 4 July 2025
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 377, 74-86
The average expected value of a rooted graph, Monte Carlo calculation, and a power index for the voting game
- 4 July 2025
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 377, 74-86
The average expected value of a rooted graph, Monte Carlo calculation, and a power index for the voting game
- 20 November 2024
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 40 (6) , 1-19
Several Minimality Concepts Related to Frankl’s Conjecture
- 20 November 2024
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 40 (6) , 1-19
Several Minimality Concepts Related to Frankl’s Conjecture
- 14 June 2021
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 37 (5) , 1891-1904
Sequential Partitions of Nonpure Simplicial Complexes
- 14 June 2021
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 37 (5) , 1891-1904
Sequential Partitions of Nonpure Simplicial Complexes
- Open Access
Signature codes for weighted binary adder channel and multimedia fingerprinting
In this paper, we study the signature codes for weighted binary adder channel (WbAC) and collusion-resistant multimedia fingerprinting. Let $A(n,t)$ denote the maximum cardinality of a $t$-signature code of length $n$, and $A(n,w,t)$ denote the maximum cardinality of a $t$-signature code of length $n$ and constant weight $w$. First, we derive asymptotic and general upper bounds of $A(n,t)$ by relating signature codes to $B_t$ codes and bipartite graphs with large girth respectively, and also show the upper bounds are tight for certain cases. Second, we determine the exact values of $A(n,2,2)$ and $A(n,3,2)$ for infinitely many $n$ by connecting signature codes with $C_4$-free graphs and union-free families, respectively. Third, we provide two explicit constructions for $t$-signature codes which have efficient decoding algorithms and applications to two-level signature codes. Furthermore, we show from the geometric viewpoint that there does not exist any binary code with complete traceability for noisy WbAC and multimedia fingerprinting. A new type of signature codes with a weaker requirement than complete traceability is introduced for the noisy scenario.Open AccessSignature codes for weighted binary adder channel and multimedia fingerprinting
In this paper, we study the signature codes for weighted binary adder channel (WbAC) and collusion-resistant multimedia fingerprinting. Let $A(n,t)$ denote the maximum cardinality of a $t$-signature code of length $n$, and $A(n,w,t)$ denote the maximum cardinality of a $t$-signature code of length $n$ and constant weight $w$. First, we derive asymptotic and general upper bounds of $A(n,t)$ by relating signature codes to $B_t$ codes and bipartite graphs with large girth respectively, and also show the upper bounds are tight for certain cases. Second, we determine the exact values of $A(n,2,2)$ and $A(n,3,2)$ for infinitely many $n$ by connecting signature codes with $C_4$-free graphs and union-free families, respectively. Third, we provide two explicit constructions for $t$-signature codes which have efficient decoding algorithms and applications to two-level signature codes. Furthermore, we show from the geometric viewpoint that there does not exist any binary code with complete traceability for noisy WbAC and multimedia fingerprinting. A new type of signature codes with a weaker requirement than complete traceability is introduced for the noisy scenario. - 23 October 2020
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 67 (1) , 200-216
Signature Codes for Weighted Binary Adder Channel and Multimedia Fingerprinting
In this paper, we study binary signature codes for the weighted binary adder channel (WbAC) and collusion-resistant multimedia fingerprinting. Let A(n,t) denote the maximum size of a t-signature code of length n, and A(n,w,t) denote the maximum size of a t-signature code of length n and constant-weight w. First, we derive asymptotic and general upper bounds on A(n,t) by relating signature codes to Bt codes and bipartite graphs with large girth respectively, and also show the upper bounds are tight for certain cases. Second, we determine the exact values of A(n,2,2) and A(n,3,2) for infinitely many n by connecting signature codes with C4-free graphs and union-free families, respectively. Third, we provide two explicit constructions for t-signature codes which have efficient decoding algorithms and applications to two-level signature codes. Furthermore, we show from a geometric viewpoint that there does not exist any binary code with complete traceability for noisy WbAC and multimedia fingerprinting. A new type of signature codes with a weaker requirement than complete traceability is introduced for the noisy scenario.
- 23 October 2020
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 67 (1) , 200-216
Signature Codes for Weighted Binary Adder Channel and Multimedia Fingerprinting
In this paper, we study binary signature codes for the weighted binary adder channel (WbAC) and collusion-resistant multimedia fingerprinting. Let A(n,t) denote the maximum size of a t-signature code of length n, and A(n,w,t) denote the maximum size of a t-signature code of length n and constant-weight w. First, we derive asymptotic and general upper bounds on A(n,t) by relating signature codes to Bt codes and bipartite graphs with large girth respectively, and also show the upper bounds are tight for certain cases. Second, we determine the exact values of A(n,2,2) and A(n,3,2) for infinitely many n by connecting signature codes with C4-free graphs and union-free families, respectively. Third, we provide two explicit constructions for t-signature codes which have efficient decoding algorithms and applications to two-level signature codes. Furthermore, we show from a geometric viewpoint that there does not exist any binary code with complete traceability for noisy WbAC and multimedia fingerprinting. A new type of signature codes with a weaker requirement than complete traceability is introduced for the noisy scenario.
- 28 November 2018
- Published by Springer Nature
- p. 49-66
Optimization Problems on Acyclic Orientations of Graphs, Shellability of Simplicial Complexes, and Acyclic Partitions
- 28 November 2018
- Published by Springer Nature
- p. 49-66
Optimization Problems on Acyclic Orientations of Graphs, Shellability of Simplicial Complexes, and Acyclic Partitions
- 1 July 2018
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 244, 1-19
Pure-strategy Nash equilibria on competitive diffusion games
- 1 July 2018
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 244, 1-19
Pure-strategy Nash equilibria on competitive diffusion games
- 1 July 2011
- Published by Elsevier in Journal of Combinatorial Theory, Series A
- Vol. 118 (5) , 1608-1623
Obstructions to shellability, partitionability, and sequential Cohen–Macaulayness
- 1 July 2011
- Published by Elsevier in Journal of Combinatorial Theory, Series A
- Vol. 118 (5) , 1608-1623
Obstructions to shellability, partitionability, and sequential Cohen–Macaulayness
- Open Access
Obstructions to shellability, partitionability, and sequential Cohen-Macaulayness
For a property $\cal P$ of simplicial complexes, a simplicial complex $\Gamma$ is an obstruction to $\cal P$ if $\Gamma$ itself does not satisfy $\cal P$ but all of its proper restrictions satisfy $\cal P$. In this paper, we determine all obstructions to shellability of dimension $\le 2$, refining the previous work by Wachs. As a consequence we obtain that the set of obstructions to shellability, that to partitionability and that to sequential Cohen-Macaulayness all coincide for dimensions $\le 2$. We also show that these three sets of obstructions coincide in the class of flag complexes. These results show that the three properties, hereditary-shellability, hereditary-partitionability, and hereditary-sequential Cohen-Macaulayness are equivalent for these classes.Open AccessObstructions to shellability, partitionability, and sequential Cohen-Macaulayness
For a property $\cal P$ of simplicial complexes, a simplicial complex $\Gamma$ is an obstruction to $\cal P$ if $\Gamma$ itself does not satisfy $\cal P$ but all of its proper restrictions satisfy $\cal P$. In this paper, we determine all obstructions to shellability of dimension $\le 2$, refining the previous work by Wachs. As a consequence we obtain that the set of obstructions to shellability, that to partitionability and that to sequential Cohen-Macaulayness all coincide for dimensions $\le 2$. We also show that these three sets of obstructions coincide in the class of flag complexes. These results show that the three properties, hereditary-shellability, hereditary-partitionability, and hereditary-sequential Cohen-Macaulayness are equivalent for these classes.