| 1. |
- Aas, Erik, et al.
(författare)
-
Limiting directions for random walks in classical affine Weyl groups
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- Let be a finite Weyl group and the corresponding affine Weyl group. A random element of can be obtained as a reduced random walk on the alcoves of . By a theorem of Lam (Ann. Probab. 2015), such a walk almost surely approaches one of many directions. We compute these directions when is , and and the random walk is weighted by Kac and dual Kac labels. This settles Lam's questions for types and in the affirmative and for type in the negative. The main tool is a combinatorial two row model for a totally asymmetric simple exclusion process called the -TASEP, with four parameters. By specializing the parameters in different ways, we obtain TASEPs for each of the Weyl groups mentioned above. Computing certain correlations in these TASEPs gives the desired limiting directions.
|
|
| 2. |
|
|
| 3. |
|
|
| 4. |
- Danielsson, Joel, et al.
(författare)
-
Polarised random k-SAT
- 2022
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- In this paper we study a variation of the random k-SAT problem, called polarized random k-SAT. In this model there is a polarization parameter p, and in half of the clauses each variable occurs negated with probability p and pure otherwise, while in the other half the probabilities are interchanged. For p=1/2 we get the classical random k-SAT model, and at the other extreme we have the fully polarized model where p=0, or 1. Here there are only two types of clauses: clauses where all k variables occur pure, and clauses where all k variables occur negated. That is, for p=0 we get an instance of random monotone k-SAT. We show that the threshold of satisfiability does not decrease as p moves away from 1/2 and thus that the satisfiability threshold for polarized random k-SAT is an upper bound on the threshold for random k-SAT. In fact, we conjecture that asymptotically the two thresholds coincide.
|
|
| 5. |
- Dodunekova, Rossitza, 1948, et al.
(författare)
-
Error Detection with a Class of Cyclic Codes
- 2005
-
Ingår i: Proc. 4th International Workshop on Optimal Codes and Related topics, 2005, Pamporovo, Bulgarian. ; , s. 127-132
-
Annan publikation (övrigt vetenskapligt/konstnärligt)
|
|
| 6. |
- Federico, Lorenzo, et al.
(författare)
-
Minimal H-factors and covers
- 2023
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- Given a fixed small graph H and a larger graph G, an H-factor is a collection of vertex-disjoint subgraphs H′⊂G, each isomorphic to H, that cover the vertices of G. If G is the complete graph Kn equipped with independent U(0,1) edge weights, what is the lowest total weight of an H-factor? This problem has previously been considered for e.g. H=K2. We show that if H contains a cycle, then the minimum weight is sharply concentrated around some Ln=Θ(n^(1−1/d∗)) (where d∗ is the maximum 1-density of any subgraph of H). Some of our results also hold for H-covers, where the copies of H are not required to be vertex-disjoint.
|
|
| 7. |
- Hegarty, Peter, 1971, et al.
(författare)
-
A variant of the multi-agent rendezvous problem
- 2013
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- The classical multi-agent rendezvous problem asks for a deterministic algorithm by which $n$ points scattered in a plane can move about at constant speed and merge at a single point, assuming each point can use only the locations of the others it sees when making decisions and that the visibility graph as a whole is connected. In time complexity analyses of such algorithms, only the number of rounds of computation required are usually considered, not the amount of computation done per round. In this paper, we consider $\Omega(n^2 \log n)$ points distributed independently and uniformly at random in a disc of radius $n$ and, assuming each point can not only see but also, in principle, communicate with others within unit distance, seek a randomised merging algorithm which asymptotically almost surely (a.a.s.) runs in time $O(n)$, in other words in time linear in the radius of the disc rather than in the number of points. Under a precise set of assumptions concerning the communication capabilities of neighboring points, we describe an algorithm which a.a.s. runs in time $O(n)$ provided the number of points is $o(n^3)$. Several questions are posed for future work.
|
|
| 8. |
- Hegarty, Peter, 1971
(författare)
-
On the notion of balance in social network analysis
- 2012
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- The notion of ``balance'' is fundamental for sociologists who study social networks. In formal mathematical terms, it concerns the distribution of triad configurations in actual networks compared to random networks of the same edge density. On reading Charles Kadushin's recent book ``Understanding Social Networks'', we were struck by the amount of confusion in the presentation of this concept in the early sections of the book. This confusion seems to lie behind his flawed analysis of a classical empirical data set, namely the karate club graph of Zachary. Our goal here is twofold. Firstly, we present the notion of balance in terms which are logically consistent, but also consistent with the way sociologists use the term. The main message is that the notion can only be meaningfully applied to undirected graphs. Secondly, we correct the analysis of triads in the karate club graph. This results in the interesting observation that the graph is, in a precise sense, quite ``unbalanced''. We show that this lack of balance is characteristic of a wide class of starlike-graphs, and discuss possible sociological interpretations of this fact, which may be useful in many other situations.
|
|
| 9. |
- Linusson, Svante, et al.
(författare)
-
On random shifted standard Young tableaux and 132-avoiding sorting networks
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- We study shifted standard Young tableaux (SYT). The limiting surface of uniformly random shifted SYT of staircase shape is determined, with the integers in the SYT as heights. This implies via properties of the Edelman-Greene bijection results about random 132-avoiding sorting networks, including limit shapes for trajectories and intermediate permutations. Moreover, the expected number of adjacencies in SYT is considered. It is shown that on average each row and each column of a shifted SYT of staircase shape contains precisely one adjacency.
|
|
| 10. |
- Olsson, Christoffer, et al.
(författare)
-
Additive functionals of subcritical graphs
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- We extend the definition of an additive functional of rooted trees to the setting of rooted subcritical graphs by viewing them as decorated trees. We then prove a central limit theorem for a general class of additive functionals of labeled subcritical graphs by building on top of known results for Galton-Watson trees. Some examples that we can treat are those of subgraph counts as well as the logarithm of the size of the automorphism group, and we also show how to translate the results to the unrooted setting. Additionally, we study the expectation of some additive functionals of unlabeled subcritical graphs. As the proofs are formulated in the language of decorated trees they also cover other examples of such structures.
|
|
