Papers

Graph theory is a powerful tool in quantum computing, with applications ranging from quantum circuit synthesis and optimization to entanglement mapping. Recent work has shown how one can use edge-colored graphs to model photonic experiments that generate GHZ and W states. However, the latter work also proved that verifying that a graph models a Dicke state experiment is coNP-complete. In this work, we provide families of graphs that generate $|D_{k}^a\rangle \otimes |0\rangle^{\otimes b }$, where $b = |a-2k|$ is the number of spectator modes. The graph setup consists of a doubled complete subgraph on $a$ vertices and a collection of auxiliary vertices. We prove that every coincidence carries exactly $k$ excitations, every weight-$k$ computational basis state on bitstrings of length $a$ is realized, and each of those bitstrings is realized exactly $(n/2)!$ times, where $n = a+b$. Since verifying the Dicke FORALL condition is coNP-complete in general, constructing explicit families that provably generate Dicke states is of interest.

We define a natural orientation on a spanning-tree-decorated planar map whereby, roughly speaking, each directed edge in the map is oriented to match the direction of the contour exploration of the spanning tree. We study directed distances (lengths of shortest directed paths) with respect to this orientation. We construct the Busemann function which measures directed distances to $\infty$ along a natural interface in the uniform infinite spanning-tree-decorated map. We show that this Busemann function, re-scaled appropriately, converges in law to a $3/2$-stable Lévy process. We also show that in a uniform spanning-tree-decorated map with $n$ edges, directed distances are typically of order $n^{1/3}$. Using a strong coupling argument, we deduce analogous statements for directed distances in other random planar maps in the $\sqrt 2$-Liouville quantum gravity (LQG) universality class, including uniform meandric systems and mated-CRT maps for $\gamma=\sqrt 2$. These results give the scaling dimension for a hypothetical directed version of the $\sqrt 2$-LQG metric. Our proof strategy is inspired by work of Borga and Gwynne (2025) on directed distances in bipolar-oriented triangulations.

Let \(\lambda\succ\gamma\succ\mu\) be equal-degree exponent partitions with at most three parts, and let \begin{equation*} P_{\lambda,\gamma,\mu} = J_\lambda+J_\mu-2J_\gamma, \end{equation*} where \(J_\nu\) denotes the symmetric monomial orbit sum associated with \(\nu\). We prove a necessary and sufficient collision criterion for the positivity of this three-point majorization difference in three variables. For nonnegative integer exponent partitions, \begin{equation*} P_{\lambda,\gamma,\mu}(x,y,z)\ge0 \qquad(x,y,z>0) \end{equation*} if and only if \begin{equation*} P_{\lambda,\gamma,\mu}(t,1,1)\ge0 \qquad(t>0). \end{equation*} Thus the positivity of a genuinely three-variable symmetric polynomial of this form is completely determined by its one-variable restriction to the locus where two variables coincide. The theorem gives a uniform and effectively checkable criterion for an infinite class of symmetric polynomial inequalities. For a fixed integer chain, the global three-variable problem is reduced to a single univariate polynomial inequality, which can often be verified exactly by factorization, Sturm's theorem, or other one-variable methods. The criterion extends well beyond the classical Schur family, produces explicit inequalities outside the Schur pattern, and yields genuine strengthenings and refinements of Schur's inequality.

We prove an exact isoperimetric inequality for cubes and tori under the $\ell_{\infty} metric. As a corollary, we recover the celebrated grid edge-isoperimetric inequality of Bollobás-Leader.

Let $\Lambda=KQ/I$ be a finite-dimensional zero-relation algebra. We encode Crawley–Boevey tree modules over $\Lambda$ by finite rooted trees labelled by arrows of $Q$ and their formal inverses, and construct a deterministic finite bottom-up tree automaton recognizing exactly these encodings. We define an accepted tree to be an automata-induced tree brick when it has no non-trivial factor–image self-overlap, and use Crawley–Boevey's graph-map basis to prove that this is equivalent to brickness of the associated tree module. We also introduce local colourings of $Q_1$ and show that the arrow alphabet can be compressed without changing the tree data, graph maps, or brick property. The optimal number of colours for such a compression is the maximum of the in-degree and out-degree of $Q$. We conclude by asking whether the tree language consisting only of bricks is regular.

Choose uniformly among the combinatorial types of convex three-dimensional polyhedra with a fixed admissible number $e$ of edges, and let $V_e$ be the number of vertices. This resolves a fixed-edge limit-distribution question posed by Rüdinger: if $\beta_e=V_e/(e+2)$, then $\sqrt e(\beta_e-1/2)\Rightarrow N(0,1/32)$, equivalently $\operatorname{Var}(V_e)\sim e/32$. Using the classical rooted enumeration and asymmetry results of Bender and Wormald, we derive a relative lattice local limit theorem on every $o(e^{3/4})$ window, a quartic correction from the rate function on every $o(e^{5/6})$ window, precise moderate-tail constants, a quadratic moderate-deviation principle for every $a_e\to\infty$ with $a_e=o(\sqrt e)$, and a full speed-$e$ large-deviation principle with an explicit good rate function. All fixed standardised moments converge. When $e=3m$, the two extremal vertex counts have equal probability asymptotic to $\frac{6561}{32\sqrt2}(4/27)^m$. Rooted and unrooted fixed-edge laws are also uniformly exponentially close, with relative discrepancy $O(\rho^e)$.

An APN mapping $F:\mathbb{F}_{2^n}\to \mathbb{F}_{2^n}$ is a polynomial characterized by the non-vanishing property on 2-flats. In this work, we analyze notions that are closely related to this property. To understand which $k$-flats of $\mathbb{F}_{2^n}$ remain flats under $F$, we study the $k$-breaking. The function $x^{-1}$ has been studied in the past in this context—we extend this study to general mappings and characterize the 2-breaking of APN functions. Recently, two generalizations of the APN property have been introduced: $k$-strongly non-normality and $k$-th-order sum-freedom. Sum-freedom generalizes the non-vanishing property of APN functions to higher dimensional flats. We provide in-depth observations of the relations between the breaking property, strongly non-normality and sum-freedom. We introduce a fourth concept called $k$-strongly breaking, which implies the breaking property. We derive several structural results for both notions and give a characterization of a subclass of APN functions in terms of the 2-strongly breaking property. We propose a different perspective of the non-vanishing property via a natural character transformation, which is closely related to the sum-of-square indicator of the components of $F$. We derive a precise value for the total sum of the sum-of-square indicators of $F$. With this approach, we provide a simple answer to Open Problem 4 in IEEE Trans. Inf. Theory 52(9): 4160-4170, 2006. Moreover, it allows us to explore balancedness properties of polynomials, one of which characterizes component-wise APNness, for odd $n$, and provides a natural extension to any dimension. We show that Dillon's APN permutation and the Gold functions satisfy a related property, termed $k$-balanced, which is presented under our framework.

Let $r,t\ge 3$ be integers and $L=\{\ell_1,\ell_2,\ldots,\ell_s\}\subseteq [0,r-1]$ a fixed set of integers with $|L|\neq r$ and $\ell_1<\ell_2<\cdots<\ell_s$. For each integer $n$, let $\Psi_{r}(n,L,t)$ be the maximum number of $r$-cliques in an $n$-vertex graph whose $r$-cliques, viewed as a family of $r$-subsets of the vertex set, form a $t$-wise $L$-intersecting family. In this paper, we prove that $\Psi_{r}(n,L,t)=o(n^{|L|})$ when the sequence $\ell_1,\ell_2,\ldots,\ell_s,r$ does not form an arithmetic progression, and we give an asymptotic formula for $\Psi_{r}(n,L,t)$ when this sequence does form an arithmetic progression. When $t=2$, our results are exactly Helliar and Liu's results.

Let $z(n)$ be the maximum number of edges in a tripartite $3$-uniform hypergraph with $n$ vertices in each part and no copy of $K_{2,2,2}^{(3)}$ (a “box”). Erdős (1964) proved that $z(n) = O(n^{11/4})$, whereas the best previous lower bound, due to Katz, Krop, and Maggioni (2002), was $\Omega(n^{8/3})$. For each $q = 2^m$, we construct a box-free hypergraph with $q^4$ vertices in each part and $q^{11}$ edges, showing that $z(n) = \Theta(n^{11/4})$. The construction uses the power map $\tau(s) = s^{q^2-q+1}$ on $\F_{q^3}$, which sends the fibers of $s \mapsto \tau(s+1) + \tau(s)$ to pairwise skew affine lines over $\F_q$.

We introduce a transformation on partially ordered sets, termed the stellahedral transform, with notable features. It preserves the properties of being Eulerian, Cohen–Macaulay, and of being the face poset of a polytope. Furthermore, it admits an explicit geometric realization for convex polytopes and specializes to the construction that takes a simplex to the stellahedron. One motivation for this definition comes from the theory of toric $h$-polynomials and (augmented) Chow polynomials of Eulerian posets. We show that the right augmented Chow polynomial of an Eulerian poset $P$ agrees with the toric $h$-polynomial of the stellahedral transform of $P$. We use this perspective, together with $\mathbf{cd}$-index results due to Ehrenborg (2005) and Karu (2006), to prove two positivity results for augmented Chow polynomials: for Gorenstein* posets they are unimodal, and for face posets of polytopes they are $\gamma$-positive. Along the way we provide negative answers to two open questions concerning Eulerian and Gorenstein* posets. First, the question on the nonnegativity of Eulerian Chow polynomials, posed by Ferroni, Matherne, and Vecchi (2024). Second, the question posed by Athanasiadis and Kalampogia-Evangelinou (2023) on the real-rootedness of chain and Chow polynomials of Gorenstein* posets: these examples provide a novel application of a technique introduced by Murai and Nevo (2014).

Cellular embeddings of graphs in surfaces have well-defined duality and minor (edge contraction and deletion) operations that interact in a natural way. A pseudosurface is obtained from a surface (compact 2-manifold) by a finite number of identifications of finite sets of points. Points that are created by the identifications do not have a neighborhood homeomorphic to an open disk and are known as pinchpoints. Embeddings of graphs in pseudosurfaces have been considered, both implicitly and explicitly, since the 1960s. Usually the condition that all pinchpoints correspond to vertices of the graph is imposed. However, this makes it difficult to define duality and minors for pseudosurface embeddings and have these operations interact in the expected way. We define the class of pseudocellular embeddings of graphs in pseudosurfaces, which allow pinchpoints at places other than vertices, in particular in the middle of faces or edges. A subclass known as quasicellular embeddings corresponds to previous embedding models due to Deneen, Shute, and Thomborson and to Huggett and Moffatt. Pseudocellular embeddings also generalize other structures, including the edge-point ribbon graphs of Ellis-Monaghan, Kauffman, and Moffatt, and cyclically ordered graphs or cogs (also known as rigid-vertex graphs). Duality and minor operations for pseudocellular embeddings have very simple and straightforward definitions using topological quotient operations. Pseudocellular embeddings of edgeless graphs have nontrivial structure, and we define some minor operations for those that are related to `t-minor' operations on bipartite graphs. We develop a family of polynomial invariants for pseudocellular embeddings and discuss connections to other polynomial invariants.

B{\i}y{\i}ko{\u g}lu, Hordijk, Leydold, Pisanski, and Stadler conjectured that, for every $n\geq3$ and $1\leq i\leq n-2$, the hypercube $Q_n$ admits a Laplacian eigenfunction with eigenvalue $2i$ and exactly two strong nodal domains. In this paper, we confirm this conjecture.

We prove a colorful quantitative Steinitz theorem in which the color classes may have different centers. If the convex hull of each of $2d$ sets in $\R^d$ contains a translate of the Euclidean unit ball, then a rainbow convex hull contains a ball of radius $(3d)^{-2d^2}$ whose center belongs to the convex hull of the given centers. The main ingredient is an exact result for translates of a segment, proved by a lifting and a topological colorful Helly theorem. The same idea also yields a sharp colorful Helly theorem for translated cones: for $1 \le k \le d-1$, if every rainbow selection from $2d-k+1$ finite families of convex sets in $\mathbb{R}^d$ has a $k$-dimensional cone in its intersection, then the intersection of one of the families contains such a cone.

The elementary symmetric partition map $\pre_s$, introduced by Ballantine, Beck, and Merca, sends an integer partition to the summands in the evaluation of the $s$-th elementary symmetric polynomial at its parts. By encoding partition parts as prime-exponent valuation vectors, we connect $\pre_s$ to Leo Moser's additive Multiset Recovery Problem (1957) and prove that $\pre_s$ is unconditionally injective on partitions of length $n$ whenever $n$ lies outside the Moser root set $\mathcal{Z}_s$, with no size restrictions. Furthermore, under the equal-size constraint $|\lambda| = |\mu| = N$, we prove that $\pre_4$ is injective at the isolated singular length $n = 12$, and that every fiber of $\pre_3$ on $\Part_6(N)$ has cardinality at most $2$, completely excluding both triplets and quartets.

In the 1960s, Erdős and Hajnal conjectured that every graph with sufficiently large chromatic number contains a subgraph of large girth (size of a smallest cycle) and large chromatic number. In this paper, we prove that every tournament with sufficiently large dichromatic number contains a subdigraph of large digirth (size of a smallest directed cycle) and large dichromatic number. We investigate the same statement when replacing digirth by girth (of the underlying graph). We show that it implies the conjecture of Erdős and Hajnal, and prove it for a particular family of tournaments.

We revisit a classic topic in probabilistic combinatorics, the lower-tail large-deviation problem for triangles in the random graph $G(n,p)$. Here we aim for first-order asymptotics for the quantity $\mathbb{P}[X=k]$ with $X$ the number of triangles in $G(n,p)$ and $0 \le k \le (1-\epsilon) \mathbb{E}X$, in the sparse regime in which the logarithmic asymptotics are Poissonian. When $k=0$ (the case of triangle-freeness) and $p = p(n)$ is sufficiently small, first-order asymptotics are known via Janson's inequality and results of Stark and Wormald; when $k$ is sufficiently close to $\mathbb{E}X$, first-order asymptotics are known via local central limit theorems. Our main result gives first-order asymptotics for all $k$ in the above range when $p = o(n^{-2/3})$, improving upon the result of Frieze that required $p = o(n^{-4/5})$. We also characterize, up to vanishing total variation distance, the distribution of the $k$ triangles in the corresponding conditional distribution and give an efficient algorithm to approximately sample from this conditional distribution. Notably, when $k = \Theta(\mu)$ there is a transition at $p = \Theta(n^{-4/5})$ from an asymptotically uniform triangle distribution to a distribution asymptotically singular to uniform.

In this article, we generalize the notion of connected subgraph arrangements, established by Cuntz and Kühne by allowing edges of cardinality greater than two, with a focus on local properties. We show that the class of free connected hypersubgraph arrangements is larger than the class of free connected subgraph arrangements, but that there exists a necessary condition for freeness that refers back to the graphic case. Furthermore, we obtain a unique description of these arrangements by associating them with Boolean building sets. We study the nested complex of the building set in relation to the lattice of intersections, and characterize all simplicial arrangements within this new class.

Let $p$ be an odd prime and let $S\subseteq\mathbb{F}_p^2$ have cardinality divisible by $p$. We prove that, for all sufficiently large primes $p$, no such set has exactly four special directions, and obtain a conditional extension to larger numbers of special directions under an affine-independence assumption on the corresponding projection functions. A separate second-moment argument shows more generally that, for every fixed $k\ge4$, no subset of $\mathbb{F}_p^2$ has exactly $k$ special directions once $p$ is sufficiently large. In fact, the result holds uniformly for $k$ up to a positive constant times $\sqrt p/\log p$. In contrast, for multisets every prescribed collection of at most $p$ directions can occur as the set of special directions of a $\{0,1,2\}$-valued multiset on $\mathbb{F}_p^2$.

Phylogenetic networks provide a flexible framework for representing reticulate evolutionary processes, such as hybridization, introgression, recombination, and horizontal gene transfer. However, their combinatorial complexity makes even basic enumeration problems difficult. Building on our previous work for networks with up to three reticulations, we derive an explicit closed-form formula for the number of unrestricted rooted binary phylogenetic networks with four reticulations on \(n\) labeled taxa. Our approach is based on tree-component graphs. We classify the 79 possible component graphs corresponding to networks with four reticulations into ten groups. We then enumerate the networks associated with each group by combining known counts of one-component networks, forests, and networks with fewer reticulations. Summing these contributions yields the desired formula. This result extends the exact enumeration of unrestricted binary phylogenetic networks to four reticulations and further demonstrates the effectiveness of component graphs for systematically organizing and counting increasingly complex network classes.

Let $\gamma(G)$ denote the number of cliques in a graph $G$ and let $\Gamma(n):= \{\gamma(G):|V(G)|=n\}$ be the set of values of $\gamma(G)$ that can be attained on $n$ vertices. We improve on a result by Erdős and Erné to show that $| \Gamma(n)| \geq 2^{n-4\ln(2)\log^3(n)}$ for sufficiently large $n$.

Let $G$ be a simple graph of even order at least four, and let $K_G$ denote the complete graph on $V(G)$. A perfect matching of $K_G$ is called a pairing of $G$. The graph $G$ has the Pairing-Hamiltonian property, or PH-property, if every pairing $M$ of $G$ admits a perfect matching $N\subseteq E(G)$, disjoint from $M$, such that $M\cup N$ is a Hamiltonian cycle of $K_G$. We prove that the PH-property is preserved under Cartesian products. More precisely, for graphs $G$ and $H$ of even order at least four, we show that both $G$ and $H$ are PH if and only if every pairing of $G\square H$ admits a Hamiltonian completion contained in a spanning union of vertex-disjoint prisms determined by a perfect matching of $G$ or of $H$. Without this support restriction, the converse fails: a Cartesian product may be PH even when neither of the two graphs is PH.

Symmetry in the context of equivalence or isomorphism is a fundamental and natural concept in any study of discrete structures. Symmetries are also important for non-discrete structures, but their treatment can be more challenging and is perhaps therefore often overlooked. This holds for many studies of complex Hadamard matrices, that is, matrices with unimodular complex entries satisfying the equation $HH^{\dagger} = nI$, where $H^{\dagger}$ is the conjugate transpose of $H$. In the current work, equivalence of complex Hadamard matrices is considered, and algorithms for determining equivalence of matrices and the automorphism group of a matrix are presented. The algorithms are used to establish the automorphism group of a large number of complex Hadamard matrices from the literature.

Let $\sigma\mathrm{Mex}(n)$ and $\sigma_e\mathrm{Mex}(n)$ denote the sum of minimal excludants and sum of even minimal excludants over all overpartitions, respectively. In this work, we study these two combinatorial objects from an arithmetic perspective. We prove that, for $n\geq 0$, $\sigma_e\mathrm{Mex}(n)\equiv\sigma\mathrm{Mex}(n)-\bar{p}_{\geq 2}(n)\pmod{2^2}$, where $\bar{p}_{\geq 2}(n)$ denotes the number of overpartitions of $n$ with all parts at least $2$, and obtain relation with basic hypergeometric series. Furthermore, we prove the asymptotic behavior of $\sigma\mathrm{Mex}(n)$, $\sigma_e\mathrm{Mex}(n)$, and $\bar{p}_{\geq 2}(n)$ as $n\to\infty$. In particular, we prove that $\sigma\mathrm{Mex}(n)\sim 2\,\sigma_e\mathrm{Mex}(n).$

A family of permutations in $S_n$ is called even-intersecting if every two distinct members agree in an even number of positions. Let $M(n)$ denote the maximum size of such a family. For even $n$, we prove that $$n!!\leq M(n)\leq e^{\frac{n}{2}+o(n)}n!!,$$ improving the bound obtained from a theorem of Cameron, Deza and Frankl (1987) by an exponential factor. This problem may be viewed as a permutation analogue of the classical Eventown problem for set systems. For odd $n$, we give a construction yielding $M(n)\geq n^2/4$. We further extend this construction to obtain $$ M(n)\geq\bigl(n-\sqrt{n-1}\bigr)^2 ,$$ whenever $n=(q+1)^2+1$ and $q$ is an odd prime power. The latter bound asymptotically matches the upper bound $M(n)\leq(n-1)^2+1$ obtained by Cameron, Deza and Frankl.

The notion of induced packing treewidth aims to unify classes defined by forbidden induced subgraphs or induced minors with classes defined by the existence of certain structured tree decompositions. For a graph $H$, \emph{induced $H$-packing treewidth}, denoted by $\treepi_{H}$, is a tree-decomposition-based graph parameter that, for each bag, measures the maximum number of pairwise anticomplete induced copies of $H$ intersecting that bag. This notion generalizes some previously studied parameters: when $H=P_1$, it is equivalent to tree-independence number, and when $H=P_2$, it is equivalent to induced matching treewidth. We prove the following: \begin{itemize}[itemsep=2mm,leftmargin=6mm] \item For all $a,t\in \mathbb{N}$, $K_{a,a}$-free graphs of bounded induced $P_t$-packing treewidth have bounded tree-independence number. This extends the previous result of Abrishami et al. [SIAM J. Discrete Math., 2025] for $t=2$, and a result of Hajebi and Spirkl who showed that $(P_t,K_{a,a})$-free graphs have bounded tree-independence number. \item If $H$ is any fixed path or a star, then the class of graphs of bounded induced $H$-packing treewidth is $\chi$-bounded. Again, this extends the previous result of Abrishami et al. [SIAM J. Discrete Math., 2025] for $H=P_2$. \item Finally, we study the relationship between induced packing treewidth and sim-width, a width parameter based on branch decompositions. We show that, although sim-width and induced $P_3$-packing treewidth are incomparable, graphs of bounded sim-width that exclude all \emph{$H$-obstructions}—certain graphs that force large induced $H$-packing treewidth—have bounded induced $H$-packing treewidth. This simultaneously generalizes and resolves questions posed by Abrishami et al. [SIAM J. Discrete Math., 2025] and Brettell et al. [European J. Comb., 2025]. \end{itemize}

In this paper, we construct a Gelfand model for the Okada algebra $O_n(X,Y)$ with generic parameters $X$ and $Y$, on the space of symmetric Okada arc diagrams using a conjugation-type action. The model is constructed inductively by identifying the Okada algebra as a diagram algebra and using the Jones basic construction to obtain a tower of algebras that are themselves Okada algebras at lower levels. We use the model to obtain all the irreducible representations of $O_n(X,Y)$, indexed by the elements of rank $n$ of the Young–Fibonacci lattice, and identify them with the cell modules of $O_n(X,Y)$.

Let $\mathcal A$ be a complete deterministic finite automaton on a state set $Q$ of size $n$ with $k$ letters, and for a proper nonempty subset $S$ of $Q$ let $\mathrm{minext}(S)$ be the length of a shortest word $u$ with $|Su^{-1}|>|S|$, where $Su^{-1}=\{q: q\cdot u\in S\}$. To each state $q$ attach the integer $\beta^{\ast}_q=\sum_{t=1}^{n-1}k^{\,n-1-t}(\mathrm{indeg}_t(q)-k^{t})$, where $\mathrm{indeg}_t(q)$ counts the pairs $(p,u)$ with $|u|=t$ and $p\cdot u=q$, and let $B(S)=\sum_{q\in S}\beta^{\ast}_q$. On every synchronizing automaton, $B(S)\ge0$ implies $\mathrm{minext}(S)\le n-1$, so, as $B(Q)=0$, one of $S$ and $Q\setminus S$ extends within $n-1$; when $B(S)>0$ no hypothesis is needed. Kari's Eulerian extension lemma is the case $\beta^{\ast}=0$, and $\beta^{\ast}$, like every member of the family $\sum_{t=1}^{n-1}c_t\sigma_t$, $c_t>0$, vanishes identically if and only if the automaton is Eulerian, where $\sigma_t(S)=\sum_{q\in S}(\mathrm{indeg}_t(q)-k^{t})$. On strongly connected automata $\sigma_t(S)/k^{t}$ has Cesàro limit $n\,e(S)/e(Q)-|S|$ for Friedman's weight $e$; that limit certifies singletons but no larger subset in general. The hypothesis $B(S)\ge0$ cannot be relaxed by one integer unit, nor can the constant $n-1$ be improved. A second-moment test on the sizes $|Su^{-1}|$ certifies 60 to 95 percent of the subsets with $B(S)<0$ at $n\le7$. Along non-Eulerian automata whose words of length $n-1$ merge a fraction of the state pairs bounded below, with $\max_q\mathrm{indeg}_{n-1}(q)=o(nk^{n-1})$, it certifies all but a vanishing share of them. The functional $B$ certifies half of the subsets outside $\{B=0\}$. At each subset size coprime to $n$ ($n\ge4$) some synchronizing Eulerian binary automaton attains the constant $n-1$; whether only there is open. No reset bound follows: Černý's automata have subsets not extending within $n-1$.

We prove the following inequality for Boolean functions: $2\sum_{x\in F_2^n}f(x)wt(x)\geq wt(f)(n-deg(f))$. Using this inequality, we establish the Fourier Entropy-Influence (FEI) conjecture for Boolean plateaued functions. In particular, we show that the sharp FEI constant for the class of plateaued functions is 4. We also prove the FEI conjecture for partially bent functions and show that the corresponding sharp constant is 2. Finally, we derive several estimates for the p-biased distribution on the Boolean hypercube. Keywords: Fourier entropy, total influence, average sensitivity, plateaued function, algebraic degree, Reed-Muller code, p-biased distribution.

In cryptography, critical sets of Latin squares have particularly been implemented to design secret sharing schemes. A main problem in these cryptographic protocols arises from absent holders of pieces of information that are common to different critical sets, because they become indispensable to recover the secret. This paper solves this problem by making use of the orbits of entries described by the autoparatopism group of the Latin square under consideration. To this end, we introduce the more general problem of computing critical sets of Latin squares having a given paratopism in their autoparatopism group. These critical sets depend only on the conjugacy class of the autoparatopism and the main class of the Latin square under consideration. Based on this fact, as an illustrative example, we determine the smallest and largest sizes of critical sets associated with autoparatopisms of Latin squares of order up to six. We implement this approach in the design of a new secret sharing scheme.

Let $k\ge 3$ and let $n=km$. A $K_k$-factor in an $n$-vertex graph is a collection of $m$ vertex-disjoint copies of $K_k$ that covers the entire vertex set. We determine the maximum adjacency spectral radius of an $n$-vertex graph containing no $K_k$-factor when $m\ge 2k-1$. More precisely, we prove that every such graph $G$ satisfies \[ \rho(G)\le \rho(H_{n,k}), \qquad H_{n,k}=K_{k-2}\vee\bigl(K_{n-k+1}\cup K_1\bigr), \] with equality if and only if $G\cong H_{n,k}$. Equivalently, the unique extremal graph is obtained from $K_{n-1}$ by adding one vertex adjacent to exactly $k-2$ vertices of the clique. Our proof combines a decomposition lemma for sparse complements, derived from the Hajnal–Szemerédi theorem, with the Motzkin–Straus inequality and spectral estimates based on quotient matrices and the Rayleigh quotient.